実装

順列 \(P\) を置換 \(\begin{pmatrix} 1 & 2 & \dots & N \\ P_1 & P_2 & \dots & P_N \end{pmatrix}\) と同一視するとき，種類 \(2\) のクエリは \(P\) をその逆置換 \(P^{-1} = \begin{pmatrix} P_1 & P_2 & \dots & P_N \\ 1 & 2 & \dots & N \end{pmatrix}\) に置き換える操作といえます．

現在の \(P,\ P^{-1}\) の値を管理することを考えます．このとき，各クエリは以下のように処理できます．

• 種類 \(1\) のクエリにおいて，\(P\) の要素に対する変更は \(P_x, P_y\) の swap のみであり，\(P^{-1}\) の要素に対する変更は \(P^{-1}_{P_x}, P^{-1}_{P_y}\) の swap のみ．
• \((P^{-1})^{-1} = P\) より，種類 \(2\) のクエリは単に \(P,\ P^{-1}\) を swap すればよい．これは愚直に swap しなくとも，\(2\) つの順列のどちらを \(P\) として扱うかを切り替える形で実装できる．

時間計算量は前処理 \(\Theta(N)\)，クエリごとに \(\Theta(1)\)，出力に \(\Theta(N)\) です．

実装例 (C++)

#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
#include <vector>
using std::vector;
using std::pair;
#include <map>
using std::map;
#include <array>
using std::array;

using std::max;
using std::min;
using std::swap;

#ifdef DEBUG
const int debug = 1;
#else
const int debug = 0;
#endif

using ll = int64_t;
using P = pair<ll, ll>;

ll n, q;
vector<ll> a;



void solve () {
	vector<ll> pq[2];
	pq[0] = a;
	pq[1].resize(n);
	for (ll i = 0; i < n; i++) {
		pq[1][a[i]] = i;
	}
	ll pi = 0;

	for (ll qi = 0; qi < q; qi++) {
		ll qt;
		cin >> qt;
		if (qt == 1) {
			ll x, y;
			cin >> x >> y;
			--x;
			--y;

			// type 1 (swap)
			ll px = pq[pi][x];
			ll py = pq[pi][y];
			swap(pq[pi  ][x ], pq[pi  ][y ]);
			swap(pq[pi^1][px], pq[pi^1][py]);

		} else {
			// type 2 (inverse)
			pi ^= 1;

		}
	}

	for (ll i = 0; i < n; i++) {
		if (i > 0) { cout << " "; }
		cout << (pq[pi][i] + 1);
	}
	cout << "\n";
	return;
}

int main (void) {
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);

	cin >> n >> q;
	a.resize(n);
	for (ll i = 0; i < n; i++) {
		cin >> a[i];
		a[i]--;
	}
	
	solve();

	return 0;
}