区間等差数列加算

全てのクエリについて、 $s=0$ であると仮定します。

このとき、 $D_i=A_i-A_{i-1}$ を考えると、 クエリ l r t は、 「$i=l+1,l+2,...,r-1$ について $D_i$ に $t$ を、 $D_r$ に $-(r-l-1)\times t$ を加算する」と解釈することができます。 これは imos 法を用いることによって高速に処理できます。

続いて、 $s\neq 0, t=0$ の場合を考えます。

このときクエリ l r s は、 「$i=l,l+1,...,r-1$ について $A_i$ に $s$ を加算する」と解釈することができます。 これも同様に imos 法を用いて高速に処理できます。

$s\neq 0, t\neq 0$ の場合、 クエリ l r s t は クエリ l r s 0 と l r 0 t の 2 種類に分解でき、それぞれ先述のケースに帰着できます。

よって全体 $O(N+Q)$ でこの問題を解くことができました。

実装例