公式解説のように「各 \(A_i\) が \(D_x\) \((x \ge i)\) に何回寄与するか」を求めた後は，クエリ平方分割によってもこの問題を解くことができます．

更新が \(X\) 回分溜まるまでは，更新情報を未反映としてキューなどで持っておき，溜まったら \(A, B, C, D\) をすべて最新状態に更新することにします． すると，全体の更新は高々 \(Q/X\) 回程度しか起こらず，更新のための計算時間は \(\mathrm{O}(NQ/X)\) となります．

一方，問合せが来たときには，現在の \(D_x\) の値を暫定解とし，\(D_x\) が現在の値に更新された後に来た未反映の更新情報を加味することで，問合せに正しく答えることができます． 具体的には，\(i \le x\) なる \(i\) に対して「\(A_i\) を \(v\) に変更する」という更新が未反映であれば，暫定解に

\[(v - A_i)\frac{(x - i + 1)(x - i + 2)}{2}\]

を足せばよいです． ただし，同じ \(i\) に対する更新に関しては，最新のものだけを考える必要があることに注意しましょう． 未反映の更新は高々 \(X\) 個なので，問合せに答えるための計算時間は \(\mathrm{O}(QX)\) となります．

おおよそ \(NQ/X = QX\) となるように \(X\) を選ぶことで全体の計算量を抑えられ，今回の設定では \(X = \sqrt{N}\) 程度にすることで \(\mathrm{O}(Q\sqrt{N})\) 時間でこの問題を解くことができます．

実装例 (C, 1248 ms)