大小関係をCartesian treeへ変換する
概要
Cartesian treeによる区間極値分解
配列順と値のheap順を同時に保つ木を構成し、区間極値を根とする再帰分割へ変換する。
考え方
配列の添字をinorder、値をheap順に持つ木を作る。単調stackで右側の祖先鎖を更新すると、区間の最小値が対応する節点へ集まり、配列の分割を木構造として扱える。
stackから親子を確定する
最小値heapを作る場合、優先keyを(value,index)として同値でも全順序を定める。空stackから添字iを昇順に読み、keyがiより大きい末尾をpopし、最後にpopした頂点をlastとする。lastがあればiの左子をlast、親[last]=iとする。pop後の末尾pがあればpの右子をi、親[i]=pとする。その後iをpushする。stackは構築済み木の右端の祖先鎖であり、keyは増加する。
popした鎖はすべてiより大きく、最後のlastがその部分木の最小keyなのでiの左へ置ける。残ったpはiより小さいためiの親になる。添字順のinorderも保つ。最後のstackの先頭が根となり、空入力なら木は空。各頂点は一回push・popされるため線形構築である。区間[l,r]の最小keyの添字はlとrのLCAになり、各部分木のinorderが連続区間であることから区間の分割へ接続できる。
成立条件と計算量
構築O(N)。同値の優先を添字などで固定しないと木が一意にならない。LCAとRMQの対応には同じtie規則を使う。木の高さは最悪Nであり、平衡木と同じ深さを仮定しない。
問題一覧
- ABC435 F「Cat exercise」 公式問題
技能・出典
主題: 大小関係をCartesian treeへ変換する(配列順とheap順を保つCartesian treeを単調stackで構成し、各部分木が表す連続区間へ問題を分解できる。)。既習技能: 根付き木DP・部分木集約(根付き木で子側の状態を合成し、部分木または木全体の値を求められる。) / 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。) / 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。主タグ: Cartesian treeによる区間極値分解 / 補助タグ: DPの最小十分状態、単調stack・queueによる支配候補の削除、根付き木DP・部分木集約
- ABC420 F「kirinuki」 公式問題
技能・出典
主題: 大小関係をCartesian treeへ変換する(配列順とheap順を保つCartesian treeを単調stackで構成し、各部分木が表す連続区間へ問題を分解できる。)。既習技能: 一次元・二次元累積和と差分で区間情報を線形化する(prefix配列またはprefix変数を置き、区間和を二つのprefix値の差で表現できる。多次元の直方体は2^D隅の包除で取得し、一括加算は端点差分へ変換できる。) / 支配関係から不要な候補を単調stack・queueで削る(候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。)。主タグ: Cartesian treeによる区間極値分解 / 補助タグ: 単調stack・queueによる支配候補の削除、累積和・差分配列
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC275 Ex「Monster」 公式問題主題: slope trick
技能・出典
主題: slope trick(区分線形凸関数を左右breakpointのheapと定数項で表し、|x-a|追加・平行移動・prefix minimumを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。追加で学ぶ技能: 大小関係をCartesian treeへ変換する(配列順とheap順を保つCartesian treeを単調stackで構成し、各部分木が表す連続区間へ問題を分解できる。)。既習技能: ordered set・multisetの動的順序管理(比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。) / small-to-large・DSU on Tree(小さいcontainerを大きいcontainerへ併合する。要素を保持する場合は所属サイズの倍増、重複を消すsetでは生存要素のサイズ増大と消滅要素への課金、分割では小さい側の半減を用いて総仕事量を証明する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: Cartesian treeによる区間極値分解、slope trick / 補助タグ: ordered set・multisetの動的順序管理、small-to-large・DSU on Tree
前提・学習成果・出典
習得対象の目安: 青色(1600–1999)。単調stackから木を構築し、区間極値と再帰分割が同じ構造になることを使う。
対象色の読み方は本書の読み方を参照してください。
概念上の親: データ構造と問い合わせ。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-cartesian-tree
習得する技能
- 配列順とheap順を保つCartesian treeを単調stackで構成し、各部分木が表す連続区間へ問題を分解できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 支配関係から不要な候補を単調stack・queueで削る。
このUnitを直接前提とする単元: なし。
単調stackの支配関係を親子関係へ持ち上げ、配列の区間極値を部分木境界として分割処理へ使う。
このUnitでは扱わないもの
- 最近傍の大小関係だけを答える単調stack、および木を構成せず冪等演算へ答えるRMQ。