考察
同じ値が続く区間なら、除算の結果も同じになるので一括で代入できる。さらに、正の値は除算のたびに半分以下になり、0になった区間は以後の除算で調べなくてよい。この二つを組み合わせ、値の等しい区間を管理しながら、全質問を通した処理量を抑える。
和だけでは除算後の和を決められない
区間代入と区間和だけなら、遅延セグメント木で処理できる。ところが、区間の和と長さが同じでも、整数除算後の和は異なることがある。例えば と はともに和が4、長さが2だが、各要素を2で割って切り捨てると と になり、和は1と2に分かれる。従って、和と長さを要約とする木へ除算をそのまま載せることはできない。
そこで、除算の結果を一括で求められる単位を探す。同じ値が続く区間なら、その値を一度割れば区間全体の新しい値が分かる。この区間を列挙して、木には区間代入として伝えればよい。
ただし、一質問で多数の区間を訪れることはある。各要素を個別に追うだけでも、代入のたびに大きな値へ戻されるので、除算回数を配列全体で対数回とは言えない。以降では、区間をまとめて代入できることと、分割で増える区間が少ないことを使って総量を証明する。
正の同値区間と和を別々に持つ
添字は1始まりの閉区間とする。値が正で一定の区間を 、つまり「区間 の全要素が 」という組で表し、左端 の順に set で管理する。区間同士は重ならず、正の要素をちょうど覆う。隣接して値も等しい区間が残っていても構わず、極大区間への統合は必須ではない。
別に、配列全体の区間代入・区間和を扱う遅延セグメント木を持つ。節点には和と長さを保存し、値 の代入では和を「 × 長さ」に置き換え、遅延タグも新しい代入値で上書きする。何も代入しないタグと、0を代入するタグは区別する。初期配列から木を構築し、同じ正値が連続する部分をまとめて set に入れる。
0の区間を set に入れないのは、0を何度割っても0だからである。0まで列挙し続けると、値が減らない訪問を何度でも繰り返せてしまう。木には0も記録されており、区間和や後の代入には支障がない。
両端で分割してから更新する
更新対象を とする。まず、位置 と で区間を分割する。ここで split(p) は、正区間 の内部、すなわち に があるとき、同じ値の と に分ける操作である。set の左端順の探索と直前区間の右端確認で、その区間を見つける。既存区間の左端、0の場所、番兵位置 では何もしない。
境界は二つなので、分割操作は一更新につき高々二回である。同じ元区間へ両境界が入る場合も、順に分割すれば高々三片になる。分割は表現だけの変更であり、木の値は変えない。分割後は、左端が 以上 以下の区間だけが更新対象で、それらは全体が に含まれる。
- 除算
1 L R x:分割後の対象区間を左から一度ずつ訪れる。区間 ごとに を求め、木の に を代入する。元のレコードを消し、 なら を残す。 なら set に戻さない。対象内の0の場所には操作不要である。
- 代入
2 L R y:分割後の対象区間を全て消し、新しく を一つ入れる。木には 全体への代入を一回行う。公式制約では なので、元が0だった場所もこの区間に含まれる。
- 和照会
3 L R:分割も set の走査も行わず、木から の和を取得する。
例えば、長さ6の配列が全て8のとき、set は 一個でよい。中央の を2で割るには、3と5で分割してから中央だけを更新するので、表現は
となる。続いて へ3を代入すると、2と6で分割した上で内側の三区間を消し、結果は
となる。この後 を2で割れば値は1、さらに2で割れば0になり、中央のレコードが消える。そこへ再び代入すれば正区間として復活する。部分更新による分裂と、代入による復活の両方を数える必要がある。
典型の発動条件
同値区間の順序付き集合
非線形な更新でも、同じ値が続く区間なら結果を一括で計算できるときに候補となる。境界で分割すれば対象区間を過不足なく列挙できるが、それだけで高速とは限らない。訪問数や区間の生成・消滅数を別に評価する。
値減少による償却解析
一回の更新が多数の対象に触れても、各訪問が残りの処理予算を確実に減らすなら、予算の初期量と総増加量から全訪問数を抑えられる。区間が分裂したり値が復活したりする場合は、そのとき増える予算も含める。本問では「正区間の値の二進表現の桁数」を予算にする。
range assign / range sum lazy tree
一様な新値を決める処理と、区間和を維持する処理を分けられるときに使える。前者を set で行い、後者を区間代入と和の遅延セグメント木へ任せる。木へ渡す代入の回数まで数えて全体を評価する。
問題固有の要素
除数が常に2以上なので、正区間への除算は値を半分以下にする。一方で、代入は多数の要素を復活させても、作る同値区間は一つだけである。さらに部分更新の境界は二つしかない。この三つが、値の減少を区間単位の処理予算へ結び付ける。
正当性
set の互いに素な正区間は正の要素をちょうど覆い、各区間の値は遅延セグメント木が表す配列と一致する、という不変条件を保つ。初期化でこれは成立する。境界分割は同じ値の区間を分けるだけなので、配列も不変条件も変えない。
除算では、境界分割後の各対象区間は全体が更新範囲内にあり、その全要素へ同じ商を代入できる。正の要素はちょうど一回処理され、set にない0は除算でも変わらず、範囲外は更新されない。商が0のレコードを消しても、木には0が代入されるため、不変条件は保たれる。
代入では、分割後の範囲内の全レコードを消して一つの正区間に置き換え、木でも同じ範囲を同じ値にする。元が0だった場所を含めて指定どおりに更新され、範囲外には影響しない。従って全更新後も木は問題の配列を表し、木から得る区間和が答えとなる。
実装上の注意
split(p) は左端が 未満の区間も確認する。ただし、set にない0の場所で直前区間を誤って分割しないよう、その右端が 以上か調べる。、、 でも同じ規則で処理できる。
- 除算走査では、消す前に次の区間の反復子を確保し、新値の再挿入先をもう一度訪れないようにする。隣接同値区間を統合するなら対象内の除算を全て終えた後に、更新した区間とその両隣だけを調べる。統合先へ二重に除算しない。統合しなくても以下の計算量は成立する。
- 木が0始まりの半開区間を受け取る実装なら、本文の閉区間 を へ変換する。
set と木で区間の意味を揃える。
- 和は最大 になる。和と「代入値 × 区間長」の積は64 bit整数で扱う。
復習の核
- 一様な区間なら非線形更新も一括処理できる。値を決める構造と和を保つ構造を分担させる。
- 半減だけでは総量証明にならない。区間の分割と値の復活が増やす予算まで数える。
- 変わらなくなった0は走査対象から外す。正区間への各訪問が予算を減らすことが償却の根拠になる。
計算量と制約
時間
初期値と全ての代入値の上限を とする。除算で値は増えないので、以後の正値も 以下である。正値 の処理予算を
とし、0については と定める。これは正値の二進表現の桁数に等しい。現在の正区間の集合を として、ポテンシャル(残り予算の合計)を
と定義する。区間の長さは掛けない。一つの長い同値区間も、一度の訪問で処理できるからである。各操作による変化を確認する。
- 初期化:区間数は高々 なので、。
- 境界分割:値 の一区間を同じ値の二区間へ分けると、予算は だけ増える。一更新で高々二回なので、増加は高々 。例えば全て8の一区間の予算は4で、中央を分離して三片にすると12になる。この増加8を更新の境界処理へ課金する。
- 代入:対象内の旧区間の予算を捨て、新区間一つの を足す。従って、分割とは別に数える増加量は高々 であり、代入範囲の長さにはよらない。
- 正区間への除算一回:新値 は 以下。 なら であり、 なら正だった区間の予算が全て消える。どちらも が少なくとも1減る。
例えば、先ほどの8の三片の中央を4にすると予算は となり、分割直後から1減る。その後の代入では、削除する三区間の予算を捨て、値3の一区間分である2だけを足す。代入で値が増えても、その増加を新しい一区間分として数え直せる。
全除算を通した正区間の訪問数を とする。 は常に非負なので、除算で消費できる量は初期量と、その後に追加された予算の合計以下である。更新回数を保守的に で抑えると、
を得る。同値の隣接区間を統合する場合は、二つの が一つになるので、ポテンシャルは増えない。この証明は、元の一区間が分裂後も同一のままであることや、各配列要素が代入で復活しないことを仮定していない。
残る費用も数える。区間のレコードは、初期化で高々 個、境界分割で一更新あたり高々4個、代入で一更新あたり1個、除算後の再挿入で一訪問あたり高々1個生成される。統合を行わない実装では生成総数は で、各レコードは一度しか消されない。従って、代入が多数の区間を消す費用も全体ではこの生成数に課金できる。任意で統合する場合も、一回で区間数が一つ減り、分割・代入による区間数の増加は合計 なので、統合の総回数は である。統合候補を調べる回数も、更新した区間数とその両隣の分を合わせて に収まる。
保持する区間数は、どの時点でも高々 。set の探索・挿入・削除を一回 として評価できる。木の構築は 、初期区間の挿入は 、木への代入と和照会は合計 回で各 。以上より、前処理・全更新・和照会を含む時間計算量は
となる。 は や値1も含めて書くためのもので、通常の表記では である。
空間
遅延セグメント木と初期配列が 。set の正区間は互いに素で、各区間が少なくとも一添字を占めるので高々 個である。質問を一つずつ読み、消したレコードを解放すれば、全体で の追加空間となる。
制約との対応
公式制約は 、、、初期値と代入値が 以上 以下、除数が である。時間制限は8秒、メモリ制限は1024 MiB。
では で、各正区間の予算は小さい。重要なのは、一質問の訪問数が少ないという保証ではなく、操作列全体の訪問数を上の式で抑えることである。除数1を許すと予算が減らず、この償却解析は使えない。
出典