各 \(i=1,2 \ldots N\) について、\(A_i\) を陽に持つのではなく「スナップショット配列」\(S_i\) と「更新履歴」\(H_i\) の \(2\) つを持っておくようにします。

具体的には、各 \(i\) に対してある地点における \(A_i\) の状態を \(S_i\) に、そこから先「\(A_{i,p}\) が \(x\) に更新された」という内容を示す整数ペア \((p,x)\) を更新が行われた順に配列として \(H_i\) に持っておけば、\(S_i\) と \(H_i\) の情報のみから現在の \(A_i\) を復元することが可能です。

このデータの持ち方を行った場合、タイプ \(1\) のクエリは \(H_{X_i}\) を \(H_{Y_i}\) に、\(S_{X_i}\) を \(S_{Y_i}\) に置き換えることに対応し、タイプ \(2\) のクエリは \(H_{X_i}\) の末尾に\((Y_i,Z_i)\) を追加することに対応します。

\(S_i\) と \(S_i\) の累積和が事前に保存されている場合、クエリ \(3\) で \((X_i,L_i,R_i)\) が飛んできた場合における答えの計算は \(O(|H_{X_i}|)\) 時間で行うことができます。まとめると、以上 \(3\) つのクエリは全て \(|H_i|\) に対し線形以下の計算量で行うことができます。

ここで、クエリに答えている間に次のような処理を行うことで、\(H_i\) の長さが短くなるようにします：

• \(H_i\) のサイズが \(B\) を超えた場合、 現在の \(A_i\) をスナップショット配列として保存し、変更履歴を空にする (\(H_i\) のサイズを \(0\) にする)。

この処理を行うことで、\(H_i\) のサイズは最大でも \(B\) になります。処理を行う回数は悪意のあるケースでなければ \(O(\frac{Q}{B})\) 回程度になり、処理一回当たりの計算量は \(O(M)\) になるので、\(B=\sqrt Q\) とすれば、\(O(N+(M+Q)√Q)\) 時間で答えを求めることができます。

実際の実装にて \(S_i\) と \(S_i\) の累積和を陽に持つと \(NM\) 個の整数型を持つ必要が生まれてしまいます。\(S_i\) の種類数は高々 \(O(\frac{N}{B})\) なので、メモリプールの要領で保存しておき、各 \(i\) についてインデックスを参照する形式をとるなどして、対策する必要があります。

なお、このアルゴリズムには Hack ケースが存在します。
例えば、\(|H_i| = B-1\) となっているものをクエリ \(1\) で大量にコピーし、コピーした数列それぞれに対してクエリ \(2\) で更新履歴を \(1\) つずつ増やすことで、スナップショット配列の再計算を大量に行わせることができます（実際には、実装で用いた \(B\) の具体値はテストケースが用意される際に知られることはないので落とされることはないと思います）。

この Hack を解消する方法として、更新を「\(|H_i|=B\) となったタイミング」にて行うのではなく、クエリ \(2\) が行われた際に独立に \(\frac{1}{B}\) で行うなどといった方法があります。