RE56pts求调

#include <iostream>
#define int long long
using namespace std;
const int N = 20000010;
int n, m, key[N], r[N], s[N], son[N][2], ans, x, op, cnt, root, ans1;
int seed = 25374643;

int rnd() {
	return seed = (seed * 2+ 23)%1000000007;
}

void pu(int i) {
	s[i] = s[son[i][0]] + s[son[i][1]] + 1;
}

void split(int x, int val, int &a, int &b) {
	if (x == 0) {
		a = b = 0;
		return;
	}

	if (key[x] < val) {
		a = x;
		split(son[x][1], val, son[x][1], b);
	} else {
		b = x;
		split(son[x][0], val, a, son[x][0]);
	}

	pu(x);
}

int merge(int a, int b) {
	if (!a || !b)
		return a ^ b;

	if (r[a] < r[b]) {
		son[a][1] = merge(son[a][1], b);
		pu(a);
		return a;
	}

	son[b][0] = merge(a,son[b][0]);
	pu(b);
	return b;
}

void ins(int a) {
	int tmp1, tmp2;
	split(root, a, tmp1, tmp2);
	key[++cnt] = a;
	r[cnt] = rnd();
	s[cnt] = 1;
	root = merge(merge(tmp1, cnt), tmp2);
}

void del(int a) {
	int tmp1, tmp2, tmp3;
	split(root, a, tmp1, tmp2);
	split(tmp2, a + 1, tmp2, tmp3);
	tmp2 = merge(son[tmp2][0], son[tmp2][1]);
	tmp2 = merge(tmp2, tmp3);
	root = merge(tmp1, tmp2);
}

void qsm(int a) {
	int tmp1, tmp2;
	split(root, a, tmp1, tmp2);
	ans = s[tmp1]+1;
	root = merge(tmp1, tmp2);
}

void qth(int x, int a) {
	if (a == s[son[x][0]] + 1) {
		ans = key[x];
		return;
	}

	if (a < s[son[x][0]] + 1)
		qth(son[x][0], a);
	else
		qth(son[x][1], a - s[son[x][0]] - 1);
}

void qbf(int a) {
	qsm(a);
	qth(root,ans-1);
}

bool qxt(int a) {
	qsm(a+1);
	qth(root,ans);
}
signed main() {
	cin >> n >> m;

	for (int i = 1; i <= n; ++i) {
		cin >> x;
		ins(x);
	}

	while (m--) {
		cin >> op >> x;
		x ^= ans;

		switch (op) {

			case 1:
				ins(x);
				break;

			case 2:
				del(x);
				break;

			case 3:
				qsm(x);
				break;

			case 4:
				qth(root, x);
				break;

			case 5:
				qbf(x);
				break;

			case 6:
				qxt(x);
				break;
        }
        if(op >= 3)ans1 ^= ans;
	}

	cout << ans1;
}