ordered set・multisetの動的順序管理
比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。
この典型を扱う単元: ordered set・multisetの動的順序管理
検索別名: multiset、order statistics tree、ordered set、平衡二分探索木
未知問からこの典型を見つける手掛かり
- 扱う対象
- 動的集合
- 重複値
- 隣接要素
- 使う手掛かり
- insert/erase
- k-smallest
- 前後の値
- 保つ不変量
- sort順
- 集合間balance
- 求めるもの
- top-K集約
- 近傍
- 順位
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 更新可能な最小十分要約
関連する典型
- event・値順のオフライン走査: eventの追加・削除に応じてactive候補の最小値・近傍・順位を動的に保つ構成で併用する。
- ordered interval partition・ODT: 区間端点をordered setで管理し、split・mergeする区間族を動的に保つときに併用する。
学習成果と学習単位
比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
ordered set・multisetの動的順序管理で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC281 E「Least Elements」 公式問題主題: ordered set・multisetの動的順序管理 / 主タグ
- ABC306 E「Best Performances」 公式問題主題: ordered set・multisetの動的順序管理 / 主タグ
- ABC342 G「Retroactive Range Chmax」 公式問題主題: Segment Treeのcanonical区間分解 / 補助タグ
技能・出典
主題: Segment Treeのcanonical区間分解
主タグ: Segment Treeのcanonical区間分解 / 補助タグ: ordered set・multisetの動的順序管理
- ABC376 E「Max × Sum」 公式問題主題: 交換論から選択順を導く / 補助タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC218 G「Game on Tree 2」 公式問題主題: rollback・DFS入退場の状態復元 / 補助タグ
技能・出典
主タグ: rollback・DFS入退場の状態復元 / 補助タグ: 有限局面DAGのminimax、ordered set・multisetの動的順序管理
- ABC245 E「Wrapping Chocolate」 公式問題主題: 交換論から選択順を導く / 補助タグ
- ABC268 Ex「Taboo」 公式問題主題: 接尾辞の順序とLCPを索引化する / 補助タグ
技能・出典
主題: 接尾辞の順序とLCPを索引化する
主タグ: 接尾辞順序・LCP索引 / 補助タグ: event・値順のオフライン走査、貪欲法と交換論、ordered set・multisetの動的順序管理、区間monoid要約
- ABC273 Ex「Inv(0,1)ving Insert(1,0)n」 公式問題主題: Stern–Brocot木の経路と祖先 / 補助タグ
技能・出典
主タグ: Stern–Brocot木の経路と祖先 / 補助タグ: ordered set・multisetの動的順序管理、再帰分割・分割統治、small-to-large・DSU on Tree
- ABC275 Ex「Monster」 公式問題主題: slope trick / 補助タグ
技能・出典
主題: slope trick
主タグ: Cartesian treeによる区間極値分解、slope trick / 補助タグ: ordered set・multisetの動的順序管理、small-to-large・DSU on Tree
- ABC281 E「Least Elements」 公式問題主題: ordered set・multisetの動的順序管理 / 主タグ
- ABC306 E「Best Performances」 公式問題主題: ordered set・multisetの動的順序管理 / 主タグ
- ABC308 G「Minimum Xor Pair Query」 公式問題主題: ordered set・multisetの動的順序管理 / 主タグ
- ABC314 G「Amulets」 公式問題主題: ordered set・multisetの動的順序管理 / 主タグ
技能・出典
主題: ordered set・multisetの動的順序管理
主タグ: ordered set・multisetの動的順序管理 / 補助タグ: 貪欲法と交換論、尺取り法・sliding window
- ABC319 G「Counting Shortest Paths」 公式問題主題: 状態グラフのモデリングと探索 / 補助タグ
技能・出典
主題: 状態グラフのモデリングと探索
主タグ: 状態グラフのモデリングと探索 / 補助タグ: 単調進行による償却解析、DP遷移の集約・高速化、ordered set・multisetの動的順序管理
- ABC320 E「Somen Nagashi」 公式問題主題: event順にactive集合を更新する / 補助タグ
技能・出典
主タグ: event・値順のオフライン走査 / 補助タグ: ordered set・multisetの動的順序管理、priority queue・best-first列挙
- ABC324 G「Generate Arrays」 公式問題主題: small-to-large・DSU on Tree / 補助タグ
技能・出典
主題: small-to-large・DSU on Tree
主タグ: small-to-large・DSU on Tree / 補助タグ: ordered set・multisetの動的順序管理
- ABC330 E「Mex and Update」 公式問題主題: ordered set・multisetの動的順序管理 / 主タグ
- ABC342 G「Retroactive Range Chmax」 公式問題主題: Segment Treeのcanonical区間分解 / 補助タグ
技能・出典
主題: Segment Treeのcanonical区間分解
主タグ: Segment Treeのcanonical区間分解 / 補助タグ: ordered set・multisetの動的順序管理
- ABC356 F「Distance Component Size Query」 公式問題主題: ordered set・multisetの動的順序管理 / 主タグ
- ABC364 F「Range Connect MST」 公式問題主題: cut・cycle性質から最適全域木を構成する / 補助タグ
技能・出典
主タグ: 最小・最大全域木とcut・cycle性質 / 補助タグ: 単調進行による償却解析、DSUによる連結成分管理・縮約、ordered set・multisetの動的順序管理
- ABC368 G「Add and Multiply Queries」 公式問題主題: 単調進行による償却解析 / 補助タグ
- ABC376 E「Max × Sum」 公式問題主題: 交換論から選択順を導く / 補助タグ
- ABC406 G「Travelling Salesman Problem」 公式問題主題: slope trick / 補助タグ
- ABC407 F「Sums of Sliding Window Maximum」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
技能・出典
主タグ: 寄与の数え上げと順序交換 / 補助タグ: event・値順のオフライン走査、ordered set・multisetの動的順序管理、累積和・差分配列
- ABC418 F「We're teapots」 公式問題主題: 区間monoid要約 / 補助タグ
- ABC431 G「One Time Swap 2」 公式問題主題: ordered set・multisetの動的順序管理 / 主タグ
- ABC444 E「Sparse Range」 公式問題主題: 尺取り法・sliding windowで連続区間を走査する / 補助タグ