普通平衡树模板题成功用01-Trie通过了且效率很高,遂尝试挑战数据加强版.不期遇RE挡我AC路,不禁发问01-Trie是否在数据加强的新形势下发挥它应有的作用? 代码如下,求调

#include <stdio.h>
int n, m;
int trie[100005 * 33][2], tot, cnt[100005 * 33], fa[100005 * 33], last, ans;
void insert(int x){
	int u = 0;
	for(int i = 31; i >= 0; i--){
		int z = (x >> i) & 1;
		if(!trie[u][z])
			trie[u][z] = ++tot, fa[tot] = u;
		u = trie[u][z];
		cnt[u]++;
	}
}
void del(int x){
	int u = 0;
	for(int i = 31; i >= 0; i--){
		int z = (x >> i) & 1;
		u = trie[u][z];
		cnt[u]--;
	}
}
int getrank(int x){
	int u = 0;
	int res = 1;
	for(int i = 31; i >= 0; i--){
		int z = (x >> i) & 1;
		if(!trie[u][z])
			trie[u][z] = ++tot, fa[tot] = u;
		if(z == 1 && cnt[trie[u][0]])
			res += cnt[trie[u][0]];
		u = trie[u][z];
	}
	return res;
}
int query(int x){
	int u = 0;
	int res = 0;
	for(int i = 31; i >= 0; i--){
		if(cnt[trie[u][0]] >= x)
			u = trie[u][0];
		else
			x -= cnt[trie[u][0]], u = trie[u][1], res += (1 << i);
	}
	return res;
}
int prev(int x){
	int u = 0, i;
	int res = x;
	for(i = 31; i >= 0; i--){
		int z = (x >> i) & 1;
		if(!trie[u][z])
			trie[u][z] = ++tot, fa[tot] = u;
		u = trie[u][z];
	}
	int mask = -1;
	while(trie[fa[u]][0] == u || !cnt[trie[fa[u]][0]]){
		u = fa[u];
		mask <<= 1;
		res &= mask;
		i++;
	}
	mask <<= 1;
	res &= mask;
	u = trie[fa[u]][0];
	for(; i >= 0; i--){
		if(cnt[trie[u][1]])
			u = trie[u][1], res += (1 << i);
		else
			u = trie[u][0];
	}
	return res;
}
int next(int x){
	int u = 0, i;
	int res = x;
	for(i = 31; i >= 0; i--){
		int z = (x >> i) & 1;
		if(!trie[u][z])
			trie[u][z] = ++tot, fa[tot] = u;
		u = trie[u][z];
	}
	int mask = -1;
	while(trie[fa[u]][1] == u || !cnt[trie[fa[u]][1]]){
		u = fa[u];
		mask <<= 1;
		res &= mask;
		i++;
	}
	mask <<= 1;
	res &= mask;
	u = trie[fa[u]][1], res += (1 << i + 1);
	for(; i >= 0; i--){
		if(cnt[trie[u][0]])
			u = trie[u][0];
		else
			u = trie[u][1], res += (1 << i);
	}
	return res;
}
int main(void){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++){
		int a;
		scanf("%d", &a);
		insert(a);
	}
	for(int i = 1; i <= m; i++){
		int opt, x;
		scanf("%d %d", &opt, &x);
		x ^= last;
		if(opt == 1)
			insert(x);
		else if(opt == 2)
			del(x);
		else if(opt == 3){
			last = getrank(x);
			ans ^= last;
		}
		else if(opt == 4){
			last = query(x);
			ans ^= last;
		}
		else if(opt == 5){
			last = prev(x);
			ans ^= last;
		}
		else{
			last = next(x);
			ans ^= last;
		}
	}
	printf("%d", ans);
	return 0;
}