ordered interval partition・ODT
互いに素な同値区間を左端順setで持ち、境界split・局所merge・range eraseでrun構造を動的管理する。
この典型を扱う単元: 端点更新型のrun分割管理
検索別名: ODT、ordered disjoint tree、区間set
未知問からこの典型を見つける手掛かり
- 扱う対象
- run
- 互いに素な区間
- 境界
- 使う手掛かり
- 区間をsplit
- 同値runをmerge
- 保つ不変量
- 最大run
- 隣接merge
- 非交差
- 求めるもの
- range代入
- 動的区間管理
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 更新可能な最小十分要約
関連する典型
- ordered set・multisetの動的順序管理: 区間端点をordered setで管理し、split・mergeする区間族を動的に保つときに併用する。
学習成果と学習単位
互いに素な同値区間を左端順setで持ち、境界split・局所merge・range eraseでrun構造を動的管理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
端点更新型のrun分割管理で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC255 Ex「Range Harvest Query」 公式問題主題: 端点更新型のrun分割管理 / 主タグ
- ABC380 E「1D Bucket Tool」 公式問題主題: 端点更新型のrun分割管理 / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC251 Ex「Fill Triangle」 公式問題主題: 標数pのFrobenius恒等式による反復高速化 / 補助タグ
技能・出典
主タグ: 標数pのFrobenius恒等式による反復高速化 / 補助タグ: 組合せ係数・数え上げ、ordered interval partition・ODT
- ABC255 Ex「Range Harvest Query」 公式問題主題: 端点更新型のrun分割管理 / 主タグ
- ABC256 Ex「I like Query Problem」 公式問題主題: 単調進行による償却解析 / 補助タグ
- ABC380 E「1D Bucket Tool」 公式問題主題: 端点更新型のrun分割管理 / 主タグ
- ABC435 E「Cover query」 公式問題主題: 端点更新型のrun分割管理 / 主タグ
- ABC465 G「Sum of Mex of Mod of Linear」 公式問題主題: 端点更新型のrun分割管理 / 主タグ