ABC 434 G — Keyboard

考察

数字+Bを削除し尽くした正規形はB^b D(数字列D、長さl、値x)となる。削除規則は、異なる削除位置が重ならないため順序に依存しない。連結前に各側を正規化しても全体の正規形は同じになる。

S=(b_s,l_s,x_s), T=(b_t,l_t,x_t)を連結する。u=min(l_s,b_t)桁をSの末尾から削除し、そのsuffix値をyとする。残るSの値はz=(x_s−y)·10^{−u} mod p。積はb=b_s+max(0,b_t−l_s), l=l_s−u+l_t, x=z·10^{l_t}+x_tとなる。10の冪と逆冪を前計算する。ただし三値だけではyを得られないので、左側Sをセグメント木の節点として保持し、その子を辿る。

節点Sが左右子L,Rからできるとき、正規形の数字列はLの末尾min(l_L,b_R)桁を削ったprefixと、Rの数字列の連結である。suffix(u)はu≤l_RならRへ降り、u>l_RならLに残るprefixの末尾u−l_R桁とRを連結する。Lに残るprefixの値は全Lの値から削除suffixを引く代わりに、必要なprefix長の値を子へ降りて取得できる。prefix/suffixの任意境界では、完全に含まれる子の値をまとめ、一つの境界だけを再帰する。したがってO(log N)で必要な部分値を得る。

内部節点の再計算はこの部分値取得を使うのでO(log N)。一点更新でO(log N)祖先を更新してO(log²N)。区間照会ではcanonical nodesを右から左へ処理する。毎回、木にある節点を左側S、現在の集約を右側Tとして合成すれば、欠ける情報は常に探索可能な左節点にある。左からのfoldでは左側が木にない集約となってしまうため、この三値だけの方式には使えない。

典型の発動条件

正規形モノイド

発動条件: 局所削除規則が合流的で、連結前後の正規化が同じ結果になるとき。

数字+B の削除を尽くした正規形を区間積として扱う。

セグメント木の履歴を使う要約補完

発動条件: 定数サイズ要約同士は直接マージ不能だが、一方の元区間が木に保持され追加情報を探索できるとき。

左節点の子へ二分探索し、要約から欠けた末尾 n 桁だけを O(log N) で取り出す。

十進連結のローリング値

発動条件: 長い数字列の連結・suffix の値を法上で扱うとき。

10^k を前計算し、長さと剰余値の組で連結を計算する。

問題固有の要素

定数サイズ要約が演算に閉じなくても、セグメント木が持つ分解履歴を補助 oracle にすれば必要情報だけ復元できる。

別の問題へ持ち帰る視点: データ構造の節点値は必ずしも自己完結モノイドでなく、木上探索込みの部分演算として設計できる場合がある。

正当性

正規形B^bDを連結すると、右側の先頭Bだけが左側末尾の数字を消すため、削除数uと三値の合成式が成立する。子の数字列のうち左側はprefixだけが残り、右側は全て残る。この連結構造を使う部分値探索は、境界の子だけを再帰して求める数字列と一致する。右から左への区間合成では左引数が常に元の木の節点なので、各段で必要な部分値を取得でき、区間全体の正規形が復元される。

実装上の注意

  • canonical nodesは右から左へ合成し、左引数を木の節点に保つ。数字が全て消えたときの長さ0、Bが余る場合、10の逆冪を確認する。

復習の核

  • Data 積に本当に必要な欠落情報が左末尾だけか、末尾取得が複数節点を跨いでも O(log N) に収まるかを確認する。

計算量と制約

時間

構築O(N)、点更新・区間照会O(log²N)。高さhの節点はO(h)で再計算でき、構築の総和はΣ_h O((N/2^h)h)=O(N)。

空間

O(N)、三値summaryと子参照・10の冪。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 8 \times 10^6; 1 \leq Q \leq 2 \times 10^5; S is a string of length N consisting of 1, 2, \dots, 9, and B.; 1 \leq x \leq N; c is 1, 2, \dots, 9, or B.; 1 \leq l \leq r \leq N; N, Q, x, l, r are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Keyboard の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 区間monoid要約

主題
  • 区間monoid要約: 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 区間monoid要約

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

      学習の位置

      体系上の位置: 区間monoid要約

      • 要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題