ABC470 D - Inverse and Swap

逆写像と交換

考え方

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

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

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

入力を受け取る。
p[0] と inv[0] はダミーとし、p, inv を 1-indexed で扱う。

p:   {-, 2, 1, 3, 5, 4}
inv: {-, 2, 1, 3, 5, 4}

$1$ 個目のクエリは 1 2 4 である。
p[2] と p[4] を入れ替え、それに対応する inv の要素も入れ替える。

p:   {-, 2, 5, 3, 1, 4}
inv: {-, 4, 1, 3, 5, 2}

$2$ 個目のクエリは 2 である。
p とその逆置換 inv を入れ替える。

p:   {-, 4, 1, 3, 5, 2}
inv: {-, 2, 5, 3, 1, 4}

$3$ 個目のクエリは 1 2 3 である。
p[2] と p[3] を入れ替え、それに対応する inv の要素も入れ替える。

p:   {-, 4, 3, 1, 5, 2}
inv: {-, 3, 5, 2, 1, 4}

$4$ 個目のクエリは 1 3 4 である。
p[3] と p[4] を入れ替え、それに対応する inv の要素も入れ替える。

p:   {-, 4, 3, 5, 1, 2}
inv: {-, 4, 5, 2, 1, 3}

$5$ 個目のクエリは 2 なので、再び p と inv を入れ替える。

p:   {-, 4, 5, 2, 1, 3}
inv: {-, 4, 3, 5, 1, 2}

最後に p を順に出力するので、答えは次のようになる。

4 5 2 1 3

特になし。

特になし。