Implementation

By identifying a permutation \(P\) with a (one-to-one) mapping \(\begin{pmatrix} 1 & 2 & \dots & N \\ P_1 & P_2 & \dots & P_N \end{pmatrix}\), a query of type \(2\) can be seen as a replacement of \(P\) into its inverse mapping \(P^{-1} = \begin{pmatrix} P_1 & P_2 & \dots & P_N \\ 1 & 2 & \dots & N \end{pmatrix}\).

Let us manage the current and \(P,\ P^{-1}\). Then each query can be processed as follows:

• Given a type-\(1\) query, the only modification on the elements of \(P\) is swapping \(P_x\) and \(P_y\), and the modification on \(P^{-1}\) is swapping \(P^{-1}_{P_x}\) and \(P^{-1}_{P_y}\).
• By \((P^{-1})^{-1} = P\), a type-\(2\) query can be simply done by swapping \(P,\ P^{-1}\). Instead of actually swapping them, one can flip the flag indicating which of the two mappings is treated as \(P\).

The time complexity is \(\Theta(N)\) for the precalculation, \(\Theta(1)\) per query, and \(\Theta(N)\) for output.

Sample code (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;
}