クエリをオフラインで処理する代わりに、高度なデータ構造を使わない解法を紹介します。

有向木を用意します。木の辺には、「タイプ \(2\) のクエリである数列 \(S\) の \(S_{Y_i}\) 項目を更新せよ」という命令を持っておきます。

また、頂点 \(i\) に対応する数列を、一番最初のクエリが前の各数列に、有向木の辺を使って頂点 \(0\) から頂点 \(i\) に行くときに通る辺にある命令を通る順に実行した結果の数列と定めます。

さらに、\(N\) 個の駒を用意し、\(i\) 個目の駒が置かれている頂点に対応する数列が \(A_i\) に等しいとします。

まず、クエリを先読みし、先ほど述べたような木を作成しながら駒を適切に動かします。このとき、タイプ \(1\) の操作では駒を別の駒と同じ頂点に移動する操作、タイプ \(2\) では新しい頂点を作ってそこに駒を移動させる操作を行えば良いです。クエリ \(3\) が飛んできた場合、そのクエリではどの頂点に対応する数列にクエリを飛ばしているかということを配列に記録します。

有向木を作成した後、セグメント木を管理しながらその木に対して dfs を行い、先ほどの配列を利用して各クエリに答えれば良いです。木の辺を戻る場合に少し問題が生じますが、これは更新クエリを加算クエリだと思ってしまうことで解決することができます。これでこの問題を解くことができました。