ABC 380 E — 1D Bucket Tool

考察

一度の塗替えは x を含む同色連続成分全体に作用し、その後に併合し得るのは左右隣の成分だけである。各色の総セル数も成分長の移動として差分更新できる。

採用する候補: 各連続成分の左端を ordered set で持ち、左端から右端と色を特定して再着色し、同色になった左右境界を削除する。

棄却する候補: type 1 ごとに x から左右へ同色セルを走査して全要素を書き換える。

大きな成分を何度も塗り直す query 列で Θ(NQ) になり得る。

各位置を長さ1成分として境界set・左端色map・色別個数を初期化する。塗替えで旧色個数を R-L 減らし新色へ足し、右境界、次に左境界を同色なら削除する。count query は色別個数を返す。

典型の発動条件

run-length interval の動的管理

発動条件: 区間全体への操作が同値 run を作り、隣接 run だけと併合する場合。

ordered set に run 左端を持ち、境界の挿入削除で列を表す。

問題固有の要素

セル列ではなく最大同色区間を原子にすると、一操作の変更箇所が定数個の境界になる。

別の問題へ持ち帰る視点: 区間長を色別集計へ差分反映すれば global count query も同時に解ける。

正当性

境界 set で x 以下最大の左端 L と次の境界 R を取れば、x の成分は半開区間 [L,R) と一意に分かる。 再着色後に左・右と同色なら境界だけを消せばよく、内部セルを更新しなくても成分表現は正しい。 成分境界は局所的にしか変わらず、predecessor/successor と高々二回の merge で各 query を O(log N) にできる。

実装上の注意

  • 右端番兵 N+1 を置き、右 merge 後に左 predecessor を取り直す。色map を消す境界と残す左端を取り違えない。

復習の核

  • [L,R) の再着色前後を図にし、右併合と左併合でどの境界を消すかを個別に確認する。

計算量と制約

時間

O(N+Q log N)、count照会O(1)。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 5 \times 10^5; 1 \leq Q \leq 2 \times 10^5; In queries of the first type, 1 \leq x \leq N.; In queries of the first and second types, 1 \leq c \leq N.; There is at least one query of the second type.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

1D Bucket Tool の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 端点更新型のrun分割管理

主題
  • 端点更新型のrun分割管理: 互いに素な同値区間を左端順setで持ち、境界split・局所merge・range eraseでrun構造を動的管理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: ordered interval partition・ODT

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

      学習の位置

      体系上の位置: 端点更新型のrun分割管理

      • 互いに素な同値区間を左端順setで持ち、境界split・局所merge・range eraseでrun構造を動的管理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

      先に読む単元:

      • ordered set・multisetの動的順序管理 — 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題