公式解説を一工夫することで、オンラインクエリでこの問題を解くことができます。

\(R_i\) を、現時点で \(i\) 行目が最後に置き換えられたときのクエリの行番号 \(q\) 及び \(x\) の組 \((q, x)\) とします。初め、 \(R_i=(0, 0)\) です。

また、 \(S_i\) を、クエリを \(i\) 個捌いた時点で、加算クエリによって列に加えられた値を管理する数列とします。 これは公式解説の \(S_i\) と同じ定義であり、 \(S_{k, j}\) は \(1, 2, \ldots, k\) 番目のクエリで \(j\) 列目に加算される値を足し合わせたものとなります。初め、 \(S_0=(0,\ldots,0)\) とします。

各クエリに対して、以下の操作が十分に高速に計算できるのならば、この問題をオンラインクエリで解くことができます。

• クエリ1
  \(S_q \leftarrow S_{q-1}+(\underbrace{0,\ldots,0}_{l-1個},\underbrace{x,\ldots,x}_{r-l+1個},\underbrace{0,\ldots,0}_{M-r個})\)
• クエリ2
  \(S_q \leftarrow S_{q-1}\)
  \(R_i \leftarrow (q, x)\)
• クエリ3
  \(S_q \leftarrow S_{q-1}\)
  \((t, v) = R_i\)
  \(v + S_{q, j} - S_{t, j}\) を出力

\(R_i\) は配列で実装すれば \(O(1)\) 時間なので、 \(S_i\) が高速に動けば良いことが分かります。 ここで \(S_i\) に永続双対セグメント木を用いれば、区間加算及び一点取得がどちらも \(O(\log M)\) 時間であることから、全体 \(O(N+M+Q\log M)\) 時間で解けることが分かります。平衡二分探索木などを用いて \(O(Q(\log N + \log M))\) 時間で解くこともできます。

なお、 \(+\) は逆元を持つことから、双対セグメント木を差分を持ったセグメント木で代替するテクニックが使えます。公式解説でフェニック木を用いているのはこの手法によるものです。