OI-wiki 上写的是两倍空间。但是题解区 BFqwq 的题解开了八倍。而且讨论区有不止一个（两个）说 $n\log n$。

我自己按 oi-wiki 写的 WBLT 需要开四倍空间。

这是为什么呀？

code:

#include<bits/stdc++.h>
#define inf 2000000000
#define ls(x) tr[x].ls
#define rs(x) tr[x].rs
#define For(i,a,b) for(i=a;i<=b;i++)
#define FOR(i,a,b) for(i=a;i>=b;i--)
#define o1 cout<<"YES\n"
#define o0 cout<<"NO\n"
using namespace std;
const int N = 4e6 + 10;
struct node {
	int ls, rs, key, sz;
};
struct WBLT {
	node tr[N];
	int root, idx;
	stack<int> q;
	void copy(int p, int q) {
		tr[p] = tr[q];
		tr[q] = {0, 0, 0, 0};
		this->q.push(q);
	}
	int make_node(int ls, int rs, int key, int sz) {
		int id = q.top();
		q.pop();
		tr[id] = {ls, rs, key, sz};
		return id;
	}
	void init() {
		root = 1;
		tr[++idx] = {2, 3, inf, 2};
		tr[++idx] = {0, 0, -inf, 1};
		tr[++idx] = {0, 0, inf, 1};
		int i;
		For(i, 4, N - 1) q.push(i);
	}
	int merge(int p, int q) {
		return make_node(p, q, tr[q].key, tr[p].sz + tr[q].sz);
	}
	void push_up(int p) {
		if (!ls(p)) {
			tr[p].sz = 1;
			return ;
		}
		tr[p].sz = tr[ls(p)].sz + tr[rs(p)].sz;
		tr[p].key = tr[rs(p)].key;
	}
	void rotate(int p, bool flag) {
		if (!flag) {
			rs(p) = merge(rs(ls(p)), rs(p));
			ls(p) = ls(ls(p));
		}
		else {
			ls(p) = merge(ls(p), ls(rs(p)));
			rs(p) = rs(rs(p));
		}
	}
	void maintain(int p) {
		if (tr[ls(p)].sz > tr[rs(p)].sz * 3) {
			if (tr[rs(ls(p))].sz > tr[ls(ls(p))].sz * 2) {
				rotate(ls(p), 1);
			}
			rotate(p, 0);
		}
		else if (tr[rs(p)].sz > tr[ls(p)].sz * 3) {
			if (tr[ls(rs(p))].sz > tr[rs(rs(p))].sz * 2) {
				rotate(rs(p), 0);
			}
			rotate(p, 1);
		}
	}
	void insert(int p, int key) {
		if (!ls(p)) {
			ls(p) = make_node(0, 0, min(key, tr[p].key), 1);
			rs(p) = make_node(0, 0, max(key, tr[p].key), 1);
		}
		else if (key <= tr[ls(p)].key) {
			insert(ls(p), key);
		}
		else {
			insert(rs(p), key);
		}
		push_up(p);
		maintain(p);
	}
	void remove(int p, int key, int fa) {
		if (!ls(p)) {
			if (key == tr[ls(fa)].key) {
				tr[ls(fa)] = {0, 0, 0, 0};
				q.push(ls(fa));
				copy(fa, rs(fa));
			}
			else if (key == tr[rs(fa)].key) {
				tr[rs(fa)] = {0, 0, 0, 0};
				q.push(rs(fa));
				copy(fa, ls(fa));
			}
			return ;
		}
		if (key <= tr[ls(p)].key) {
			remove(ls(p), key, p);
		}
		else {
			remove(rs(p), key, p);
		}
		push_up(p);
		maintain(p);
	}
	int get_rank_by_key(int p, int key) {
		if (tr[p].sz == 1) return (tr[p].key < key);
		if (tr[ls(p)].key >= key) return get_rank_by_key(ls(p), key);
		return get_rank_by_key(rs(p), key) + tr[ls(p)].sz;
	}
	int get_key_by_rank(int p, int rank) {
		if (tr[p].sz == rank) {
			return tr[p].key;
		}
		if (tr[ls(p)].sz >= rank) return get_key_by_rank(ls(p), rank);
		return get_key_by_rank(rs(p), rank - tr[ls(p)].sz);
	}
	int get_pre(int p, int key) {
		if (tr[p].sz == 1) {
			if (tr[p].key < key)
				return tr[p].key;
			return -inf;
		}
		if (tr[ls(p)].key >= key) return get_pre(ls(p), key);
		return max(tr[ls(p)].key, get_pre(rs(p), key));
	}
	int get_suf(int p, int key) {
		if (tr[p].sz == 1) {
			if (tr[p].key > key)
				return tr[p].key;
			return inf;
		}
		if (tr[ls(p)].key <= key) return get_suf(rs(p), key);
		return min(tr[rs(p)].key, get_suf(ls(p), key));
	}
} tree;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	tree.init();
	int n, m;
	cin >> n >> m;
	while (n--) {
		int x;
		cin >> x;
		tree.insert(tree.root, x);
	}
	int ans = 0, lastans = 0;
	while (m--) {
		int op, x;
		cin >> op >> x;
		x ^= lastans;
		if (op == 1) {
			tree.insert(tree.root, x);
		}
		if (op == 2) {
			tree.remove(tree.root, x, -1);
		}
		if (op == 3) {
			lastans = tree.get_rank_by_key(tree.root, x);
			ans ^= lastans;
		}
		if (op == 4) {
			lastans = tree.get_key_by_rank(tree.root, x + 1);
			ans ^= lastans;
		}
		if (op == 5) {
			lastans = tree.get_pre(tree.root, x);
			ans ^= lastans;
		}
		if (op == 6) {
			lastans = tree.get_suf(tree.root, x);
			ans ^= lastans;
		}
	}
	cout << ans << '\n';
	return 0;
}