ABC 332 F — Random Update Query

考察

操作区間の各位置pは、長さλのうち1/λでXへ置換され、残り(λ-1)/λで以前の値を保つ。期待値の線形性により位置間の依存を追わず、各E_pを同じaffine写像へ更新できる。

queryは区間一様な変換E←aE+bであり、affine写像同士は合成してもaffine写像のままなので遅延伝搬できる。

採用する候補: 区間affine作用を持つlazy segment treeで期待値列を更新する

棄却する候補: 乱択結果の分布や位置間の相関まで状態に持つ

求めるのは各位置の期待値だけで、線形性により周辺期待値の更新が閉じるため過剰な状態である。

棄却する候補: 各queryで区間内の期待値を直接更新する

全区間queryが続けばΘ(NM)となり、N,M≤2×10^5に間に合わない。

期待値配列をAで初期化し、各queryのλ=R-L+1と逆元を求め、区間[L,R]へf(x)=((λ-1)/λ)x+X/λをlazy適用する。全操作後に各点を取得しmod 998244353で出力する。

典型の発動条件

期待値の線形性による周辺量の更新

発動条件: 相関する乱択操作でも、要求が各成分の一次量だけであるとき。

位置ごとの置換確率から期待値の閉じた漸化式を作る。

range affine lazy propagation

発動条件: 区間全要素へx←ax+bを時系列で適用するとき。

affine作用を合成してlazy tagとし、区間更新を対数時間化する。

問題固有の要素

同じ操作内では「どれか一位置だけ」が更新されるという負の相関があるが、各最終A_iの期待値には影響せず周辺期待値だけで完結する。

別の問題へ持ち帰る視点: 確率過程でjoint distributionを持つ前に、求める統計量が線形性で閉じるかを確認する。

正当性

区間の一箇所だけが変わる操作でも、任意の固定位置から見た置換確率は1/λなので、全位置へ同じ期待値変換を同時に適用してよい。 既存作用f(x)=ax+bの後にg(x)=cx+dを行う合成はg∘f(x)=ca x+(cb+d)で、queryの時間順を逆にしない。 各操作をa=(λ-1)/λ,b=X/λとして区間へ作用させ、M回のrange updateと最終値取得をO((N+M)log N)で処理できる。

実装上の注意

  • affine tagのcomposition順序をqueryの適用順に合わせ、λ=1ではa=0,b=Xとなることを確認する。indexの半開区間変換も統一する。

復習の核

  • N=1、λ=1、同一区間への連続更新を手計算し、二つのaffine作用の順序を逆にした実装との差が出るcaseで検証する。

計算量と制約

時間

逆元を長さ別に前計算してO(N+M log N)、最終展開O(N)。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: All input values are integers.; 1 \leq N, M \leq 2 \times 10^5; 0 \leq A_i \leq 10^9; 1 \leq L_i \leq R_i \leq N; 0 \leq X_i \leq 10^9

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 区間更新を要約へ作用させる

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 遅延評価する区間作用

    補助タグ: 法上の四則演算・高速累乗・逆元

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

    学習の位置

    体系上の位置: 区間更新を要約へ作用させる

    • 更新作用の合成順と要約への適用を定義し、遅延評価で保てる。

    先に読む単元:

    • 法上の四則演算・高速累乗・逆元 — 剰余を正規化して加減乗算し、二分累乗と逆元の存在条件を使って法上の除算や確率を計算する。
    • 区間monoid要約 — queryに十分な値と結合順・単位元を定義し、Segment Treeまたはprefix foldで動的区間要約を保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    この解説で扱わないこと:

    • 過去の版の保存・rollback・構造共有。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題