ABC 256 Ex — I like Query Problem

考察

同じ値が続く区間なら、除算の結果も同じになるので一括で代入できる。さらに、正の値は除算のたびに半分以下になり、0になった区間は以後の除算で調べなくてよい。この二つを組み合わせ、値の等しい区間を管理しながら、全質問を通した処理量を抑える。

和だけでは除算後の和を決められない

区間代入と区間和だけなら、遅延セグメント木で処理できる。ところが、区間の和と長さが同じでも、整数除算後の和は異なることがある。例えば (1,3)(1,3) と (2,2)(2,2) はともに和が4、長さが2だが、各要素を2で割って切り捨てると (0,1)(0,1) と (1,1)(1,1) になり、和は1と2に分かれる。従って、和と長さを要約とする木へ除算をそのまま載せることはできない。

そこで、除算の結果を一括で求められる単位を探す。同じ値が続く区間なら、その値を一度割れば区間全体の新しい値が分かる。この区間を列挙して、木には区間代入として伝えればよい。

ただし、一質問で多数の区間を訪れることはある。各要素を個別に追うだけでも、代入のたびに大きな値へ戻されるので、除算回数を配列全体で対数回とは言えない。以降では、区間をまとめて代入できることと、分割で増える区間が少ないことを使って総量を証明する。

正の同値区間と和を別々に持つ

添字は1始まりの閉区間とする。値が正で一定の区間を (l,r,v)(l,r,v)、つまり「区間 [l,r][l,r] の全要素が v>0v>0」という組で表し、左端 ll の順に set で管理する。区間同士は重ならず、正の要素をちょうど覆う。隣接して値も等しい区間が残っていても構わず、極大区間への統合は必須ではない。

別に、配列全体の区間代入・区間和を扱う遅延セグメント木を持つ。節点には和と長さを保存し、値 yy の代入では和を「yy × 長さ」に置き換え、遅延タグも新しい代入値で上書きする。何も代入しないタグと、0を代入するタグは区別する。初期配列から木を構築し、同じ正値が連続する部分をまとめて set に入れる。

0の区間を set に入れないのは、0を何度割っても0だからである。0まで列挙し続けると、値が減らない訪問を何度でも繰り返せてしまう。木には0も記録されており、区間和や後の代入には支障がない。

両端で分割してから更新する

更新対象を [L,R][L,R] とする。まず、位置 LL と R+1R+1 で区間を分割する。ここで split(p) は、正区間 [l,r][l,r] の内部、すなわち l<p≤rl<p\leq r に pp があるとき、同じ値の [l,p−1][l,p-1] と [p,r][p,r] に分ける操作である。set の左端順の探索と直前区間の右端確認で、その区間を見つける。既存区間の左端、0の場所、番兵位置 N+1N+1 では何もしない。

境界は二つなので、分割操作は一更新につき高々二回である。同じ元区間へ両境界が入る場合も、順に分割すれば高々三片になる。分割は表現だけの変更であり、木の値は変えない。分割後は、左端が LL 以上 RR 以下の区間だけが更新対象で、それらは全体が [L,R][L,R] に含まれる。

  • 除算 1 L R x:分割後の対象区間を左から一度ずつ訪れる。区間 (l,r,v)(l,r,v) ごとに w=⌊v/x⌋w=\lfloor v/x\rfloor を求め、木の [l,r][l,r] に ww を代入する。元のレコードを消し、w>0w>0 なら (l,r,w)(l,r,w) を残す。w=0w=0 なら set に戻さない。対象内の0の場所には操作不要である。
  • 代入 2 L R y:分割後の対象区間を全て消し、新しく (L,R,y)(L,R,y) を一つ入れる。木には [L,R][L,R] 全体への代入を一回行う。公式制約では y≥1y\geq1 なので、元が0だった場所もこの区間に含まれる。
  • 和照会 3 L R:分割も set の走査も行わず、木から [L,R][L,R] の和を取得する。

例えば、長さ6の配列が全て8のとき、set は (1,6,8)(1,6,8) 一個でよい。中央の [3,4][3,4] を2で割るには、3と5で分割してから中央だけを更新するので、表現は

(1,2,8),(3,4,4),(5,6,8)(1,2,8),\quad (3,4,4),\quad (5,6,8)

となる。続いて [2,5][2,5] へ3を代入すると、2と6で分割した上で内側の三区間を消し、結果は

(1,1,8),(2,5,3),(6,6,8)(1,1,8),\quad (2,5,3),\quad (6,6,8)

となる。この後 [2,5][2,5] を2で割れば値は1、さらに2で割れば0になり、中央のレコードが消える。そこへ再び代入すれば正区間として復活する。部分更新による分裂と、代入による復活の両方を数える必要がある。

典型の発動条件

同値区間の順序付き集合

非線形な更新でも、同じ値が続く区間なら結果を一括で計算できるときに候補となる。境界で分割すれば対象区間を過不足なく列挙できるが、それだけで高速とは限らない。訪問数や区間の生成・消滅数を別に評価する。

値減少による償却解析

一回の更新が多数の対象に触れても、各訪問が残りの処理予算を確実に減らすなら、予算の初期量と総増加量から全訪問数を抑えられる。区間が分裂したり値が復活したりする場合は、そのとき増える予算も含める。本問では「正区間の値の二進表現の桁数」を予算にする。

range assign / range sum lazy tree

一様な新値を決める処理と、区間和を維持する処理を分けられるときに使える。前者を set で行い、後者を区間代入と和の遅延セグメント木へ任せる。木へ渡す代入の回数まで数えて全体を評価する。

問題固有の要素

除数が常に2以上なので、正区間への除算は値を半分以下にする。一方で、代入は多数の要素を復活させても、作る同値区間は一つだけである。さらに部分更新の境界は二つしかない。この三つが、値の減少を区間単位の処理予算へ結び付ける。

正当性

set の互いに素な正区間は正の要素をちょうど覆い、各区間の値は遅延セグメント木が表す配列と一致する、という不変条件を保つ。初期化でこれは成立する。境界分割は同じ値の区間を分けるだけなので、配列も不変条件も変えない。

除算では、境界分割後の各対象区間は全体が更新範囲内にあり、その全要素へ同じ商を代入できる。正の要素はちょうど一回処理され、set にない0は除算でも変わらず、範囲外は更新されない。商が0のレコードを消しても、木には0が代入されるため、不変条件は保たれる。

代入では、分割後の範囲内の全レコードを消して一つの正区間に置き換え、木でも同じ範囲を同じ値にする。元が0だった場所を含めて指定どおりに更新され、範囲外には影響しない。従って全更新後も木は問題の配列を表し、木から得る区間和が答えとなる。

実装上の注意

  • split(p) は左端が pp 未満の区間も確認する。ただし、set にない0の場所で直前区間を誤って分割しないよう、その右端が pp 以上か調べる。L=1L=1、R=NR=N、L=RL=R でも同じ規則で処理できる。
  • 除算走査では、消す前に次の区間の反復子を確保し、新値の再挿入先をもう一度訪れないようにする。隣接同値区間を統合するなら対象内の除算を全て終えた後に、更新した区間とその両隣だけを調べる。統合先へ二重に除算しない。統合しなくても以下の計算量は成立する。
  • 木が0始まりの半開区間を受け取る実装なら、本文の閉区間 [l,r][l,r] を [l−1,r)[l-1,r) へ変換する。set と木で区間の意味を揃える。
  • 和は最大 5×105×105=5×10105\times10^5\times10^5=5\times10^{10} になる。和と「代入値 × 区間長」の積は64 bit整数で扱う。

復習の核

  • 一様な区間なら非線形更新も一括処理できる。値を決める構造と和を保つ構造を分担させる。
  • 半減だけでは総量証明にならない。区間の分割と値の復活が増やす予算まで数える。
  • 変わらなくなった0は走査対象から外す。正区間への各訪問が予算を減らすことが償却の根拠になる。

計算量と制約

時間

初期値と全ての代入値の上限を U=105U=10^5 とする。除算で値は増えないので、以後の正値も UU 以下である。正値 vv の処理予算を

b(v)=1+⌊log⁡2v⌋b(v)=1+\lfloor\log_2 v\rfloor

とし、0については b(0)=0b(0)=0 と定める。これは正値の二進表現の桁数に等しい。現在の正区間の集合を SS として、ポテンシャル(残り予算の合計)を

Φ=∑(l,r,v)∈Sb(v)\Phi=\sum_{(l,r,v)\in S} b(v)

と定義する。区間の長さは掛けない。一つの長い同値区間も、一度の訪問で処理できるからである。各操作による変化を確認する。

  • 初期化:区間数は高々 NN なので、Φ≤Nb(U)\Phi\leq N b(U)。
  • 境界分割:値 vv の一区間を同じ値の二区間へ分けると、予算は b(v)b(v) だけ増える。一更新で高々二回なので、増加は高々 2b(U)2b(U)。例えば全て8の一区間の予算は4で、中央を分離して三片にすると12になる。この増加8を更新の境界処理へ課金する。
  • 代入:対象内の旧区間の予算を捨て、新区間一つの b(y)≤b(U)b(y)\leq b(U) を足す。従って、分割とは別に数える増加量は高々 b(U)b(U) であり、代入範囲の長さにはよらない。
  • 正区間への除算一回:新値 w=⌊v/x⌋w=\lfloor v/x\rfloor は v/2v/2 以下。w>0w>0 なら b(w)≤b(v)−1b(w)\leq b(v)-1 であり、w=0w=0 なら正だった区間の予算が全て消える。どちらも Φ\Phi が少なくとも1減る。

例えば、先ほどの8の三片の中央を4にすると予算は 4+3+4=114+3+4=11 となり、分割直後から1減る。その後の代入では、削除する三区間の予算を捨て、値3の一区間分である2だけを足す。代入で値が増えても、その増加を新しい一区間分として数え直せる。

全除算を通した正区間の訪問数を VV とする。Φ\Phi は常に非負なので、除算で消費できる量は初期量と、その後に追加された予算の合計以下である。更新回数を保守的に QQ で抑えると、

V≤(N+3Q)b(U)=O((N+Q)log⁡(U+1))\begin{aligned} V&\leq (N+3Q)b(U)\\ &=O\bigl((N+Q)\log(U+1)\bigr) \end{aligned}

を得る。同値の隣接区間を統合する場合は、二つの b(v)b(v) が一つになるので、ポテンシャルは増えない。この証明は、元の一区間が分裂後も同一のままであることや、各配列要素が代入で復活しないことを仮定していない。

残る費用も数える。区間のレコードは、初期化で高々 NN 個、境界分割で一更新あたり高々4個、代入で一更新あたり1個、除算後の再挿入で一訪問あたり高々1個生成される。統合を行わない実装では生成総数は O(N+Q+V)O(N+Q+V) で、各レコードは一度しか消されない。従って、代入が多数の区間を消す費用も全体ではこの生成数に課金できる。任意で統合する場合も、一回で区間数が一つ減り、分割・代入による区間数の増加は合計 O(Q)O(Q) なので、統合の総回数は O(N+Q)O(N+Q) である。統合候補を調べる回数も、更新した区間数とその両隣の分を合わせて O(V+Q)O(V+Q) に収まる。

保持する区間数は、どの時点でも高々 NN。set の探索・挿入・削除を一回 O(log⁡(N+1))O(\log(N+1)) として評価できる。木の構築は O(N)O(N)、初期区間の挿入は O(Nlog⁡(N+1))O(N\log(N+1))、木への代入と和照会は合計 O(V+Q)O(V+Q) 回で各 O(log⁡(N+1))O(\log(N+1))。以上より、前処理・全更新・和照会を含む時間計算量は

O((N+Q)log⁡(U+1)log⁡(N+1))O\bigl((N+Q)\log(U+1)\log(N+1)\bigr)

となる。+1+1 は N=1N=1 や値1も含めて書くためのもので、通常の表記では O((N+Q)log⁡Ulog⁡N)O((N+Q)\log U\log N) である。

空間

遅延セグメント木と初期配列が O(N)O(N)。set の正区間は互いに素で、各区間が少なくとも一添字を占めるので高々 NN 個である。質問を一つずつ読み、消したレコードを解放すれば、全体で O(N)O(N) の追加空間となる。

制約との対応

公式制約は 1≤N≤5×1051\leq N\leq5\times10^5、1≤Q≤1051\leq Q\leq10^5、1≤L≤R≤N1\leq L\leq R\leq N、初期値と代入値が 11 以上 10510^5 以下、除数が 2≤x≤1052\leq x\leq10^5 である。時間制限は8秒、メモリ制限は1024 MiB。

U=105U=10^5 では b(U)=17b(U)=17 で、各正区間の予算は小さい。重要なのは、一質問の訪問数が少ないという保証ではなく、操作列全体の訪問数を上の式で抑えることである。除数1を許すと予算が減らず、この償却解析は使えない。

出典

分類・前提・執筆情報

掲載状態: 収録済み

I like Query Problem の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 単調進行による償却解析

主題
  • 単調進行による償却解析: 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。
追加で学ぶ技能
    なし
    既習技能
    • 区間更新を要約へ作用させる: 更新作用の合成順と要約への適用を定義し、遅延評価で保てる。
    • 端点更新型のrun分割管理: 互いに素な同値区間を左端順setで持ち、境界split・局所merge・range eraseでrun構造を動的管理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    主タグ: 単調進行による償却解析

    補助タグ: 遅延評価する区間作用 ordered interval partition・ODT

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

    学習の位置

    体系上の位置: 単調進行による償却解析

    • 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。

    先に読む単元:

    • 端点更新型のrun分割管理 — 順序付きのrun分割をdequeや連結リストで保持し、両端からの削除・分割・追加を行う。左端順setを使うODTとは区別する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • 区間更新を要約へ作用させる — 結合的な区間要約を設計した後、更新作用の合成順と要約への適用を遅延評価する。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題