写的 Splay，已经一下午了 5555

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#define MAXN 1100001

int n, m, last, ans;

namespace Splay {
	int root, fa[MAXN], size[MAXN], son[MAXN][2];
	int num, val[MAXN], cnt[MAXN];
	int which(int x) { return son[fa[x]][1] == x ? 1 : 0; }
	void update(int x) { size[x] = cnt[x] + size[son[x][0]] + size[son[x][1]]; }
	void clear(int x) { fa[x] = son[x][0] = son[x][1] = size[x] = cnt[x] = val[x] = 0; }
	void rotate(int x) {
		int father = fa[x], grandpa = fa[father];
		int flag1 = which(x), flag2 = which(father);
		fa[x] = grandpa;
		if (grandpa) son[grandpa][flag2] = x;
		fa[son[x][flag1 ^ 1]] = father;
		son[father][flag1] = son[x][flag1 ^ 1];
		son[x][flag1 ^ 1] = father;
		fa[father] = x;
		update(x), update(father);
	}
	void splay(int x) {
		for (int f = fa[x]; f = fa[x], f; rotate(x)) {
			if (fa[f]) rotate(which(x) == which(f) ? f : x);
		}
		root = x;
	}
	void ins(int k) {
		if (!root) {
			val[++num] = k;
			++cnt[num];
			root = num;
			update(root);
			return;
		}
		int now = root, f = 0;
		while (1) {
			if (val[now] == k) {
				++cnt[now];
				update(now), update(f);
				splay(now);
				break;
			}
			f = now, now = son[now][val[now] < k];
			if (!now) {
				val[++num] = k;
				++cnt[num];
				fa[num] = f;
				son[f][val[f] < k] = num;
				update(num), update(f);
				splay(num);
				break;
			}
		}
	}
	int pre() {
		int now = son[root][0];
		while (son[now][1]) now = son[now][1];
		splay(now); return now;
	}
	int nxt() {
		int now = son[root][1];
		while (son[now][0]) now = son[now][0];
		splay(now); return now;
	}
	int qrank(int k) {
		int ans = 0, now = root;
		while (1) {
			if (k < val[now]) now = son[now][0];
			else {
				ans += size[son[now][0]];
				if (val[now] == k) {
					splay(now);
					return ans + 1;
				}
				ans += cnt[now];
				now = son[now][1];
			}
		}
	}
	int qkth(int k) {
		int now = root;
		while (1) {
			if (son[now][0] && k <= size[son[now][0]]) now = son[now][0];
			else {
				k -= size[son[now][0]] + cnt[now];
				if (k <= 0) {
					splay(now);
					return val[now];
				}
				now = son[now][1];
			}
		}
	}
	void del(int k) {
		qrank(k);
		if (cnt[root] > 1) {
			--cnt[root];
			update(root);
			return;
		}
		if (!son[root][0] && !son[root][1]) {
			clear(root);
			root = 0;
			return;
		}
		if (!son[root][0]) {
			int now = root;
			root = son[root][1];
			fa[root] = 0;
			clear(now);
			return;
		}
		if (!son[root][1]) {
			int now = root;
			root = son[root][0];
			fa[root] = 0;
			clear(now);
			return;
		}
		int now = root, x = pre();
		fa[son[now][1]] = x;
		son[x][1] = son[now][1];
		clear(now);
		update(root);
	}
}

int main() {
	read(n), read(m);
	for (int i = 1, x; i <= n; ++i) {
		read(x);
		Splay::ins(x);
	}
	for (int i = 1, opt, x; i <= m; ++i) {
		read(opt), read(x);
		x ^= last;
		if (opt == 1) Splay::ins(x);
		else if (opt == 2) Splay::del(x);
		else if (opt == 3) {
			Splay::ins(x);
			last = Splay::qrank(x); 
			ans ^= last;
			Splay::del(x);
		}
		else if (opt == 4) {
			last = Splay::qkth(x);
			ans ^= last;
		}
		else if (opt == 5) {
			Splay::ins(x);
			last = Splay::val[Splay::pre()];
			ans ^= last;
			Splay::del(x);
		}
		else if (opt == 6) {
			Splay::ins(x);
			int last = Splay::val[Splay::nxt()];
			ans ^= last;
			Splay::del(x);
		}
	}
	std::cout << ans << '\n';
	return 0;
}