提交记录

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 2e6;
const int INF = 0x7fffffff;

int n, m, last, ans, tot, root;
int val[N], cnt[N], size[N], fa[N], ch[N][2];

int newnode(int x) {
	val[++tot] = x;
	cnt[tot] = size[tot] = 1;
	return tot;
}

void update(int x) {
	size[x] = size[ch[x][0]] + size[ch[x][1]] + cnt[x];
}

bool id(int x) {
	return x == ch[fa[x]][1];
}

void connect(int x, int y, bool k) {
	ch[x][k] = y;
	fa[y] = x;
}

void rotate(int x) {
	int y = fa[x], z = fa[y];
	bool k = id(x);
	connect(z, x, id(y));
	connect(y, ch[x][k ^ 1], k);
	connect(x, y, k ^ 1);
	update(y);
	update(x);
}

void splay(int x, int to) {
	while (fa[x] != to) {
		int y = fa[x];
		if (fa[y] != to) id(x) ^ id(y) ? rotate(x) : rotate(y);
		rotate(x);
	}
	if (to == 0) root = x;
}

void find(int x) {
	int u = root;
	while (val[u] != x && ch[u][x > val[u]]) u = ch[u][x > val[u]];
	splay(u, 0);
}

void insert(int x) {
	if (!root) {
		root = newnode(x);
		return;
	}
	int u = root;
	while (val[u] != x && ch[u][x > val[u]]) u = ch[u][x > val[u]];
	if (val[u] == x) {
		cnt[u]++;
		splay(u, 0);
	} else {
		connect(u, newnode(x), x > val[u]);
		splay(ch[u][x > val[u]], 0);
	}
}

void erase(int x) {
	if (!root) return;
	find(x);
	if (!root || val[root] != x) return;
	if (cnt[root] > 1) {
		cnt[root]--;
		size[root]--;
		return;
	}
	int u = ch[root][0];
	if (!u) {
		root = ch[root][1];
		fa[root] = 0;
		return;
	}
	while (ch[u][1]) u = ch[u][1];
	splay(u, root);
	connect(u, ch[root][1], 1);
	root = u;
	fa[root] = 0;
	update(root);
}

int rank(int x) {
	find(x);
	int ls = size[ch[root][0]];
	return (val[root] < x ? ls + cnt[root] : ls) + 1;
}

int kth(int x) {
	int u = root;
	while (1) {
		if (x <= size[ch[u][0]]) u = ch[u][0];
		else if (x > size[ch[u][0]] + cnt[u]) {
			x -= size[ch[u][0]] + cnt[u];
			u = ch[u][1];
		} else break;
	}
	splay(u, 0);
	return val[u];
}

int pre(int x) {
	find(x);
	if (val[root] < x) return val[root];
	int u = ch[root][0];
	if (!u) return -INF;
	while (ch[u][1]) u = ch[u][1];
	splay(u, 0);
	return val[u];
}

int nxt(int x) {
	find(x);
	if (val[root] > x) return val[root];
	int u = ch[root][1];
	if (!u) return INF;
	while (ch[u][0]) u = ch[u][0];
	splay(u, 0);
	return val[u];
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1, a; i <= n; i++) {
		scanf("%d", &a);
		insert(a);
	}
	for (int i = 1, opt, x; i <= m; i++) {
		scanf("%d%d", &opt, &x);
		x ^= last;
		if (opt == 1) insert(x);
		if (opt == 2) erase(x);
		if (opt == 3) {
			last = rank(x);
			ans ^= last;
		}
		if (opt == 4) {
			last = kth(x);
			ans ^= last;
		}
		if (opt == 5) {
			last = pre(x);
			ans ^= last;
		}
		if (opt == 6) {
			last = nxt(x);
			ans ^= last;
		}
	}
	printf("%d", ans);
	return 0;
}