ABC470 D - Inverse and Swap

考え方

クエリ2が逆写像をつくることを要求している。
しかし、これを何度も繰り返すなら、何度も作り直すより、常に本体と逆写像を両方持っておくのが早い。
C++なら、swap() を使えば $O(1)$ で配列の交換ができ、クエリ $2$ はそれでよい。

あとはクエリ $1$。
これも、元配列の $x$ と $y$ を入れ替えるなら、逆配列の対応するところも同時に入れ替えるだけ。

計算量は $O(N+Q)$ である。

入力例1での動作

入力を受け取る。
配列は 1-indexed で示す。

n: 5
q: 5
p: {2, 1, 3, 5, 4}

1 2 4
2
1 2 3
1 3 4
2

最初の逆置換は $\{2,1,3,5,4\}$ である。
各クエリ後の $P$ と逆置換は次のようになる。

クエリ 1 2 4 では $P_2$ と $P_4$ を交換する。
それまでの値は $P_2=1,\ P_4=5$ なので、逆置換側では値 $1$ と $5$ に対応する位置も交換する。

クエリ 2 では、$P$ と逆置換そのものを交換するだけでよい。

最終的な $P$ は 4 5 2 1 3 となる。

注意点

特になし。

別解

特になし。