TLE on #5, 6

如之奈何？

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2000010, INF = (1 << 30) + 1;


struct Node {
	int ch[2];
	int size;
	int p, v;
	int cnt;
}tr[N];

int root, idx;

void pushup(int u) {
	tr[u].size = tr[tr[u].ch[0]].size + tr[tr[u].ch[1]].size + tr[u].cnt;
}

void rotate(int x) {
	int y = tr[x].p;
	int z = tr[y].p;
	int k = tr[y].ch[1] == x;
	
	tr[z].ch[tr[z].ch[1] == y] = x, tr[x].p = z;
	tr[y].ch[k] = tr[x].ch[k ^ 1], tr[tr[x].ch[k ^ 1]].p = y;
	tr[x].ch[k ^ 1] = y, tr[y].p = x;
	
	pushup(y);
	pushup(x);
}

void splay(int x, int k) {
	while (tr[x].p != k) {
		int y = tr[x].p;
		int z = tr[y].p;
		
		if (z != k) {
			if ((tr[z].ch[1] == y) ^ (tr[y].ch[1] == x)) rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
	if (!k) root = x;
}

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

int get_pre(int x) {
	find(x);
	if (tr[root].v < x) return root;
	int u = tr[root].ch[0];
	while (tr[u].ch[1]) u = tr[u].ch[1];
	return u;
}

int get_suc(int x) {
	find(x);
	if (tr[root].v > x) return root;
	int u = tr[root].ch[1];
	while (tr[u].ch[0]) u = tr[u].ch[0];
	return u;
}

void insert(int x) {
	int p = 0, u = root;
	while (u && tr[u].v != x)
		p = u, u = tr[u].ch[x > tr[u].v];
	if (u) tr[u].cnt++;
	else {
		u = ++idx;
		if (p) tr[p].ch[x > tr[p].v] = u;
		tr[u].p = p;
		tr[u].size = tr[u].cnt = 1;
		tr[u].v = x;
	}
	splay(u, 0);
}

void del(int x) {
	int pre = get_pre(x);
	int suc = get_suc(x);
	splay(pre, 0);
	splay(suc, pre);
	int del_v = tr[suc].ch[0];
	if (tr[del_v].cnt > 1) tr[del_v].cnt--, splay(del_v, 0);
	else tr[suc].ch[0] = 0, splay(suc, 0);
}

int get_rank_by_key(int x) {
	find(x);
	if (tr[root].v == x) return tr[tr[root].ch[0]].size;
	int p = get_pre(x);
	find(tr[p].v);
	return tr[tr[root].ch[0]].size + 1;
}

int get_key_by_rank(int k) {
	int u = root;
	while (true) {
		if (k <= tr[tr[u].ch[0]].size) u = tr[u].ch[0];
		else if (k <= tr[tr[u].ch[0]].size + tr[u].cnt) break;
		else k -= tr[tr[u].ch[0]].size + tr[u].cnt, u = tr[u].ch[1];
	}
	splay(u, 0);
	return tr[u].v;
}

int n, m;

int main() {
	freopen("2.in", "r", stdin);
	freopen("2.out", "w", stdout);
	
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	insert(-INF);
	insert(INF);
	
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		insert(x);
	}
	
	int last = 0;
	int opt, x;
	int res = 0;
	
	for (int i = 1; i <= m; i++) {
		cin >> opt >> x;
		x ^= last;
		if (opt == 1) insert(x);
		else if (opt == 2) del(x);
		else if (opt == 3) insert(x), res ^= (last = get_rank_by_key(x)), del(x), cout << opt << ' ' << last << '\n';
		else if (opt == 4) res ^= (last = get_key_by_rank(x + 1)), cout << opt << ' ' << last << '\n';
		else if (opt == 5) res ^= (last = tr[get_pre(x)].v), cout << opt << ' ' << last << '\n';
		else res ^= (last = tr[get_suc(x)].v), cout << opt << ' ' << last << '\n';
	}
	
	cout << res << '\n';
	return 0;
}