順列 \(P_i\) について \(P_i\leq x\) ならば \(A_i=0\) 、\(P_i\geq x+1\) ならば \(A_i=1\) とした \(01\) 列 \(A\) を用意し、これがクエリによってどう変更されるか考えます。 もし、 \(x=K-1\) としたときと \(x=K\) としたときについて、すべてのクエリを処理した後の \(01\) 列が分かれば、その差分から \(P_i=k\) である \(i\) を求めることができます。具体的には前者では \(0\) , 後者では \(1\) であるような場所が \(1\) つだけ存在し、その場所が \(P_i=k\) であるようindex \(i\) の場所です。

クエリについて、まず \(C_i=1\), すなわち昇順にソートするものを考えます。\(A_{L_i}, A_{L_i+1}, \ldots ,A_{R_i}\) に \(0\) が \(a\) 個、 \(1\) が \(b\) 個 \((a+b=R_i-L_i+1)\) 含まれていたとします。このとき \(P_j\) \((L_i\leq j\leq R_i)\) の具体的な値が何であったかに関わらず、ソート後の順列に対応する \(01\) 列のこの範囲には \(a\) 個の \(0\) と \(b\) 個の \(1\) が、この順で並びます。すなわち、 \(0,0,\ldots, (a個),\ldots,0,1,1,,\ldots, (b個),\ldots,1\) となります。これは次の操作と同値です。

• \(S=A_{L_i}+A_{L_i+1}+\cdots +A_{R_i}\) を求める。
• \(A_{L_i}, A_{L_i+1}, \ldots ,A_{R_i-S}\) の値を一括して \(0\) に変更する。
• \(A_{R_i-S+1}, A_{R_i-S+2}, \ldots ,A_{R_i}\) の値を一括して \(1\) に変更する。

同様にして、\(C_i=2\), すなわち降順にソートする操作も \(01\) 列に対しては、

• \(S=A_{L_i}+A_{L_i+1}+\cdots +A_{R_i}\) を求める。
• \(A_{L_i}, A_{L_i+1}, \ldots ,A_{L_i+S-1}\) の値を一括して \(1\) に変更する。
• \(A_{L_i+S}, A_{L_i+S+1}, \ldots ,A_{R_i}\) の値を一括して \(0\) に変更する。

という操作と同値である事が分かります。

これらの操作は遅延セグメント木によって行うことができます。 よって、初期状態の順列から \(01\) 列を構成し、遅延セグメント木の上でクエリによる更新操作を行い、最終的な \(01\) 列についてその差分を調べれば良いです。計算量は最初の構築および最後の差分検索に\(O(N)\), 更新はクエリごとに \(O(\log N)\) であるため全体で \(O(N+Q\log N)\) であり、十分高速です。よって、この問題を解く事が出来ました。

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;
}