ABC 253 F — Operations on a Matrix

考察

行への代入が消すのは、その行にそれまで蓄積した値である。最後の行代入を境界にして、それ以後に対象列へ加わった量だけを足せば、巨大な行列を保存せずに各成分を求められる。

公式制約は行数・列数ともに N,M≤2×105N,M\leq 2\times 10^5 であり、全成分を持つと最大 4×10104\times 10^{10} 個になる。行列を直接保存して行代入・列区間加算を行う方法では間に合わない。一方、行 ii の成分を取得するとき、過去の行代入はその時点で最新の一つだけが効いている。

クエリを1始まりの時刻で番号付けし、時刻 tt までの列区間加算だけを累積した量を St[j]S_t[j] とする。行代入はこの累積量には反映しない。時刻 tt の点取得 (i,j)(i,j) に対して、直前の行代入が時刻 ss、代入値が xx なら、答えは

x+St[j]−Ss[j]x+S_t[j]-S_s[j]

となる。取得時の St[j]S_t[j] が Snow[j]S_{\mathrm{now}}[j]、代入時の Ss[j]S_s[j] が Sset[j]S_{\mathrm{set}}[j] に当たる。例えば、ある成分に5を加え、その行へ7を代入し、その成分に2を加えると、成分は 0→5→7→90\to 5\to 7\to 9 と変わる。列加算だけの累積量は7だが、そのうち代入前の5は既に上書きされている。従って 7+(5+2)−5=97+(5+2)-5=9 と、古い加算を引く必要がある。

行代入を一度も受けていない行は、時刻0に0を代入したものとみなす。S0[j]=0S_0[j]=0 なので、同じ式が 0+St[j]−00+S_t[j]-0 となり、初期値0からの全加算を数えられる。

問題は、過去の代入時点の Ss[j]S_s[j] をどう取得するかである。代入のたびに全列を保存すると、再び行数と列数の積に比例する仕事が生じる。先に全クエリを読めることを使い、実際に将来取得される列だけを、その代入時点で記録する。

  1. 一度目の走査では、長さ NN の配列 last を全て0にし、各行の直前代入時刻を保つ。行代入のたびに該当行の last を更新する。点取得では、その取得の識別番号と列 jj を、last[i] が示す代入に紐付ける。
  2. 二度目の走査では、列加算の累積量を Fenwick Tree で保つ。時刻 ss に値 xx を行代入するとき、そこに紐付く各点取得の列 jj について Ss[j]S_s[j] を読み、その取得の補正値として x−Ss[j]x-S_s[j] を保存する。時刻0に紐付く取得は、走査開始前に補正値を0とする。
  3. 点取得の時刻 tt に到達したら、保存した補正値に現在の St[j]S_t[j] を加え、元のクエリ順に出力する。

列区間加算は、列方向の差分列を Fenwick Tree に載せて処理する。列 l,…,rl,\ldots,r に aa を加えるとき、差分の位置 ll に aa、位置 r+1r+1 に −a-a を加える。列 jj の累積量 St[j]S_t[j] は、その時点の差分の1列目から jj 列目までの和で得られる。番兵の位置 M+1M+1 まで用意すれば、右端が MM の加算も同じ形で扱える。

一つの代入に多くの取得が紐付いても、各点取得が紐付く代入は一つだけである。代入時点で記録する列の延べ個数は高々 QQ なので、全列のスナップショットは不要になる。

典型の発動条件

オフライン依存先の付け替え

答えが「過去の最後の上書き一つ」と「その後の変化」で決まり、全問い合わせを先に読めるときに使う。最初の走査で依存する更新を特定すれば、二度目の走査で必要な過去の値だけを記録できる。

range-add point-query BIT

区間へ一様に加算し、特定位置の値だけを読みたいとき、差分列への2点更新と接頭辞和へ変換できる。この問題では、列方向の差分で加算を管理したうえで、時刻方向の二つの累積量の差から上書き以後の寄与を取り出す。

問題固有の要素

行代入は、その行が受けた列ごとに異なる過去の加算を打ち消す。代入値だけを行ごとに保存しても、どの加算を取り消すかが分からない。そこで、点取得ごとに直前の行代入と列を組にして記録する。巨大な二次元状態を、行の上書き境界と列の加算履歴へ分解できることが核心である。

正当性

点取得 (i,j)(i,j) の直前の行代入が時刻 ss に値 xx を書いたとする。その代入によって時刻 ss 以前の寄与は全て消え、それ以後、取得時刻 tt までには同じ行への代入はない。従って、成分の値は xx と、その間に列 jj へ加えた量 St[j]−Ss[j]S_t[j]-S_s[j] の和である。代入がない場合も、時刻0の仮想代入 x=0x=0 と S0[j]=0S_0[j]=0 によって同じ式が成り立つ。

一度目の走査の last[i] は、各点取得が依存するこの時刻 ss を正しく特定する。二度目の走査では、差分列の2点更新と接頭辞和により各時点の St[j]S_t[j] を正しく得られる。紐付け先の代入時に保存した補正値 x−Ss[j]x-S_s[j] に、取得時の St[j]S_t[j] を加えるので、各答えは求める成分に一致する。記録する列を将来の点取得が使うものに限定しても、各点取得に必要な二時点の値は全て得られる。

実装上の注意

  • 時刻0の紐付けも保持し、その補正値を0で初期化する。実際の代入がない行の取得を落とさない。
  • 二度目の走査で行代入そのものを Fenwick Tree へ反映しない。木が管理するのは、行によらず共通する列加算の累積量だけである。
  • 同じ代入に同じ列の取得が複数紐付いても、それぞれの取得番号へ補正値を保存すればよい。クエリは入力順に処理する。
  • 列加算の総和と補正値は64ビット符号付き整数で持つ。補正値は負になることがある。

復習の核

  • 上書きと加算が混ざるときは、最後の上書き以前と以後を分ける。累積加算から上書き時点の累積量を引けば、それ以後だけを残せる。
  • 過去の全状態を保存する前に、将来の問い合わせが必要とする位置だけを更新時点へ紐付けられないか考える。
  • 時刻0の仮想代入を置くと、上書きが一度もない行も同じ式で扱える。

計算量と制約

時間

行の last 配列の初期化に O(N)O(N)、長さ M+1M+1 の差分 Fenwick Tree のゼロ初期化に O(M)O(M)、クエリの保持・紐付けに O(Q)O(Q) かかる。各列加算は2回の点更新、各点取得は高々1回の代入時の読み取りと1回の取得時の読み取りであり、紐付け先のリストを巡る総数も O(Q)O(Q)。全体で O(N+M+Qlog⁡(M+1))O(N+M+Q\log(M+1)) となる。M=1M=1 でも木の操作とクエリ走査の定数時間を含む。

空間

行の last 配列に O(N)O(N)、差分 Fenwick Tree に O(M)O(M)、クエリ・紐付けリスト・取得ごとの補正値に O(Q)O(Q) を使うので、全体で O(N+M+Q)O(N+M+Q)。

制約との対応

公式制約は 1≤N,M,Q≤2×1051\leq N,M,Q\leq 2\times 10^5、加算値・代入値は1以上 10910^9 以下。行列全体を作らず、行・列・クエリ数の和に比例する記憶量で処理する。成分の値は高々 (Q+1)×109(Q+1)\times 10^9 程度なので64ビット整数で足りる。代入なし、同じ行への連続代入、M=1M=1 も、直前代入への紐付けと時刻0の基底を変えずに扱える。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Operations on a Matrix の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 時間を逆向きにして未来依存を消す

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

    主タグ: 逆向きのオフライン処理

    補助タグ: Fenwick Tree・反転数・重み付き接頭辞統計 累積和・差分配列

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

    学習の位置

    体系上の位置: 時間を逆向きにして未来依存を消す

    • 時間依存を逆走査・逆操作・last-write時刻で単調または静的にし、元の時点へ答えを戻せる。

    先に読む単元:

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

    • 値順eventを前から処理するsweep、時刻を反転せずに行う通常のonline更新、および答えの局所寄与だけを集計する順序交換。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題