ABC 255 Ex — Range Harvest Query

考察

巨大なNに対し必要なのは各木の最終収穫日。区間収穫で日付が一様に上書きされるので一定値blockをordered setへ持つ。L,R+1をsplitし、含まれるblockごとに等差数列和で収穫を計算して削除し、[L,R]を日Dで挿入する。splitによる断片も含め一質問の生成block数は定数なので全列挙をO(Q)へ償却できる。

初期状態は全木が未収穫なので、閉区間[1,N]に最終日0を持つ一blockを置く。query(D,L,R)では、Lを含むblock[l,r,d]を[l,L−1,d],[L,r,d]へ分け、次にR<NならR+1でも分ける。境界がすでにあるときは分けず、空区間は作らない。これで列挙対象は全て[L,R]の内側に入る。

各対象block[l,r,d]の今回の収穫量は(D−d)Σ_{i=l}^r i=(D−d)(l+r)(r−l+1)/2。これを法998244353で足してqueryの答えを出し、そのblockを消す。全対象を消してから[L,R,D]を一つ挿入する。指数域を巨大な配列へ展開する必要はない。法上の除算2には逆元499122177を掛け、座標は64bitのまま、各乗算前に因子を法へ落とす。

典型の発動条件

区間を一定値ブロックで持つODT

発動条件: 巨大な座標域への区間代入があり、値が区間ごとに一定となる。

区間端でブロックをsplitし、被覆ブロックを列挙・削除して一ブロックへ置換する。

償却解析

発動条件: 一操作では多数区間を消す可能性があるが、新規区間数は少ない。

各ブロックの削除をその生成へ課金し、全走査量をO(Q)と評価する。

問題固有の要素

日付Dが厳密増加するため必要な状態は各木の「最後の収穫日」だけで、区間上書きがそのまま一定値ブロック構造を作る。

別の問題へ持ち帰る視点: 巨大な添字域でも、区間代入が履歴を消し一操作の生成区間数が定数なら、区間集合の償却管理が使える。

正当性

木iの成長量は最後の収穫日dからi(D−d)であり、同日block[l,r]の量は(D−d)(l+r)(r−l+1)/2。端点でsplitすれば列挙するblockは更新区間を重複なく被覆する。その全寄与を加え値Dの一blockへ置換すると最後の収穫日という状態を保つ。split二回と代入による生成は一質問あたり定数個なので、生成総数O(Q)、削除総数もO(Q)である。

実装上の注意

  • N,D,L,Rは10^18なので添字計算のオーバーフローを避け、積は法998244353へ段階的に落とす。R=NではR+1の番兵処理を分け、分割後のiterator無効化に注意する。

復習の核

  • 小さいNの配列実装と比較し、全域更新、点更新、入れ子・交差区間、R=N、同じ境界を繰り返し分割する場合を確認する。

計算量と制約

時間

全Q質問で償却O(Q log Q)、端点分割も一回定数個。

空間

O(Q)、最終収穫日の区間集合。

制約との対応

公式制約の確認範囲: Time limit: 8 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 10^{18}; 1 \leq Q \leq 2 \times 10^5; 1 \leq D_1 \lt D_2 \lt \cdots \lt D_Q \leq 10^{18}; 1 \leq L_i \leq R_i \leq N; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

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

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

    主タグ: ordered interval partition・ODT

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

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

    学習の位置

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

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

    先に読む単元:

    • 単調進行による償却解析 — 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑える。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • ordered set・multisetの動的順序管理 — 比較順を保つ集合でpredecessor/successor・極値・重複・二集合のk-smallest aggregateを更新する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題