For a permutation \(P_i\), consider a \(01\)-array \(A\) such that \(A_i = 0\) if \(P_i\leq x\) and \(A_i=1\) if \(P_i\geq x+1\). How is this sequence updated by the queries? If we can obtain, for \(x=K-1\) and \(x=k\), the final \(01\)-sequence after all queries were processed, then we can find the \(i\) such that \(P_i=k\) based on the difference between them. Namely, there exists a unique position at which the first sequence is \(0\) and the second is \(1\); that is the position of index \(i\) such that \(P_i=k\).

Let’s first consider the query of \(C_i=1\), that is, the query of sorting in the ascending order. Suppose that \(A_{L_i}, A_{L_i+1}, \ldots ,A_{R_i}\) had \(a\) number of \(0\)’s and \(b\) number of \(1\)’s. Then, no matter what was the actual value of \(P_j\) \((L_i\leq j\leq R_i)\), in the \(01\)-sequence corresponding to the permutation after the sort, \(a\) number of \(0\)’s and \(b\) number of \(1\)’s comes in this range in this order; i.e. we have \(0,0,\ldots, (a\text{ times}),\ldots,0,1,1,,\ldots, (b\text{ times}),\ldots,1\). This is equivalent to the following operations.

• Find \(S=A_{L_i}+A_{L_i+1}+\cdots +A_{R_i}\).
• Update \(A_{L_i}, A_{L_i+1}, \ldots ,A_{R_i-S}\) to \(0\) at once.
• Update \(A_{R_i-S+1}, A_{R_i-S+2}, \ldots ,A_{R_i}\) to \(1\) at once.

Similarly, for the query of \(C_i=2\), we can achieve it by the following operations:

• Find \(S=A_{L_i}+A_{L_i+1}+\cdots +A_{R_i}\).
• Update \(A_{L_i}, A_{L_i+1}, \ldots ,A_{L_i+S-1}\) to \(1\) at once.
• Update \(A_{L_i+S}, A_{L_i+S+1}, \ldots ,A_{R_i}\) to \(0\) at once.

These operations can be done with lazy segment tree. Therefore, we can construct a \(01\)-sequence from the initial state, perform updates on the lazy segment tree, and find the difference of two resulting \(01\)-sequences. The time complexity is \(O(N)\) for the first construction and the last step of finding the difference, and \(O(\log N)\) for the updated for each query, for a total of \(O(\log N)\), which is fast enough. Therefore, the problem has been solved.

Sample code in c++:

#include <bits/stdc++.h>
#include <atcoder/lazysegtree>

using namespace std;
using namespace atcoder;

#define rep(i, n) for(int i = 0; i < n; ++i)

struct S { 	int sz, val; };

struct F { int k; };

S op(S l, S r) { return S{ l.sz + r.sz,l.val + r.val }; }

S e() { return S{ 0,0 }; }

S mapping(F f, S s) {
	if (f.k >= 0)return S{ s.sz,(f.k)*(s.sz) };
	else return s;
}

F composition(F l, F r) {
	if (l.k >= 0)return F{ l.k };
	else return F{ r.k };
}

F id() { return F{ -1 }; }


int main() {
	int n, q, k;
	int c, l, r;
	int x, y;
	
	cin >> n >> q >> k;
  
    vector<S> a(n), b(n);
  
	rep(i, n) {
		cin >> x;
		if (x < k)a[i] = { 1,0 };
		else a[i] = { 1,1 };
		if (x <= k)b[i] = { 1,0 };
		else b[i] = { 1,1 };
	}

	lazy_segtree<S, op, e, F, mapping, composition, id> sega(a);
	lazy_segtree<S, op, e, F, mapping, composition, id> segb(b);

	rep(i, q) {
		cin >> c >> l >> r;
		l--;
		x = sega.prod(l, r).val;
		y = segb.prod(l, r).val;
		if (c == 1) {
			sega.apply(l, r - x, F{ 0 });
			sega.apply(r - x, r, F{ 1 });
			segb.apply(l, r - y, F{ 0 });
			segb.apply(r - y, r, F{ 1 });
		}
		else {
			sega.apply(l, l + x, F{ 1 });
			sega.apply(l + x, r, F{ 0 });
			segb.apply(l, l + y, F{ 1 });
			segb.apply(l + y, r, F{ 0 });
		}
	}

	rep(i, n)if (sega.get(i).val != segb.get(i).val)cout << i + 1 << endl;

	return 0;
}