ABC 342 G — Retroactive Range Chmax

考察

range chmax操作は互いに可換で、現在のA_iは初期値とiを覆う未取消操作のxの最大値だけで決まる。したがって操作順を再実行する必要はなく、activeなrange値のpoint stabbing maximumを管理すればよい。

採用する候補: segment treeのcanonical nodeごとにdeletable max multisetを持つ

棄却する候補: 取消のたびに初期配列から全active操作を再適用する

一回の取消がO(NQ)級になり、Q=2×10^5では不可能である。

各segment nodeにmultiset、または追加heapと削除heapのlazy deletion pairを置く。type 1の(l,r,x)をcanonical nodesへ挿入しoperation IDに情報を保存する。type 2では同じ分解nodeからxを削除する。type 3ではA_iとleafからrootまでの各node現在maxの最大を出力する。

典型の発動条件

segment tree区間分解

発動条件: range objectをpoint queryで参照し、後から同じobjectを削除したい。

rangeをO(log N) canonical nodeに登録し、point pathだけを走査する。

deletable priority queue

発動条件: 各nodeで値の挿入・指定値削除・最大取得を行う。

multisetを使うか、追加heapと削除heapのtop一致を遅延相殺する。

問題固有の要素

chmaxの合成が単なるmaxで可換・冪等なので、retroactive cancellation後の値もactive x集合だけから復元でき、時系列情報を持たなくてよい。

別の問題へ持ち帰る視点: 可換なrange作用の取消は、作用parameterのmultisetを空間分解nodeに保持するとonline化できる。

正当性

任意区間[l,r)はsegment treeのO(log N)個のdisjoint canonical intervalに分解できる。点iを覆う更新は、その分解nodeのうちroot-to-leaf path上にあるものとしてちょうど一度現れるため、path上node最大の最大が全active xの最大になる。 range追加・取消をO(log N) nodeへの挿入削除、point取得をroot-to-leaf上の最大へ分解できる。

実装上の注意

  • type 2はquery番号で元のl,r,xを参照し、同じxが複数operationにあるため一個だけ削除する。空nodeの最大はidentityとして扱う。

復習の核

  • 同じxの重複、nested/disjoint ranges、最大操作の取消で次点が現れる、初期A_iが全active xより大きい例をnaive再計算と比較する。

計算量と制約

時間

Q操作O(Q log N log Q)、取消対応multiset版。点取得O(log N)。

空間

O(N+Q log N)、登録が置かれるcanonical node数。

制約との対応

公式制約の確認範囲: Time limit: 5 sec; Memory limit: 1024 MiB; Constraints: 1\leq N\leq2\times10^5; 1\leq A_i\leq10^9\ (1\leq i\leq N); 1\leq Q\leq2\times10^5; In a type-1 operation, 1\leq l\leq r\leq N and 1\leq x\leq10^9.; In a type-2 operation, i is not greater than the number of operations given before, and 1\leq i.; In a type-2 operation, the i-th operation is of type 1.; In type-2 operations, the same i does not appear multiple times.; In a type-3 operation, 1\leq i\leq N.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Retroactive Range Chmax の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: Segment Treeのcanonical区間分解

主題
  • Segment Treeのcanonical区間分解: 区間をO(log N)個のcanonical nodeへ分解してrange object・時間生存区間・range edgeを配置し、point queryではroot-to-leaf path上のobjectを集められる。
追加で学ぶ技能
    なし
    既習技能
    • ordered set・multisetの動的順序管理: 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    主タグ: Segment Treeのcanonical区間分解

    補助タグ: ordered set・multisetの動的順序管理

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: Segment Treeのcanonical区間分解

    • 区間をO(log N)個のcanonical nodeへ分解してrange object・時間生存区間・range edgeを配置し、point queryではroot-to-leaf path上のobjectを集められる。

    先に読む単元:

    • ordered set・multisetの動的順序管理 — 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • 区間monoid要約 — queryに十分な値と結合順・単位元を定義し、Segment Treeまたはprefix foldで動的区間要約を保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題