Fallen Leaves

解説

累積和を用いて高速に解答することができます。
$1$ 番から $i$ 番までのタイル上にある落ち葉の枚数の総和を $S_i$ とします。
また、便宜上 $S_0=0$ とします。
はじめの状態での各 $S_i$ の値は、$S_i = S_{i-1}+A_i$ により $O(N)$ で全て求まります。

以上の事前処理のもと、各クエリを $O(1)$ で処理できます。

落ち葉の移動について、移動元と移動先をいずれも含まないような $S$ の値は変化しません。
また、移動元と移動先を両方含むような $S$ の値も変化しません。
よって、タイプ $1$ のクエリで変化するのは $S_i$ だけで、$S_i\gets S_{i-1}$ とすればよいです。
同様に、タイプ $2$ のクエリで変化するのは $S_{i-1}$ だけで、$S_{i-1}\gets S_i$ とすればよいです。

タイプ $3$ のクエリは、通常の累積和の処理同様 $S_R-S_{L-1}$ を出力すればよいです。

以上により、計算量 $O(N+Q)$ で解答できます。

Fenwick 木や segment 木を用いて解答することもできる制約にしてありますが、計算量が $O((N+Q)\log N)$ であり、累積和解法より劣っています。