CF817E Choosing The Commander

此题其实为 \(01Trie\) 模板题。

看到加入、删除、求异或值， 我们不禁也必须想到 \(01Trie\) 树。（未学过的童鞋们除外）

1、什么是 \(01Trie\) ?

首先我们要先知道什么是 \(Trie\) 树，这里推荐一篇个人认为还不错的博客。

顾名思义，所谓 \(01 Trie\), 是普通 \(Trie\) 树的一种特殊应用。与 \(Trie\) 树各个节点保存的都是字母类似，在 \(01Trie\) 上我们每个节点保存的是数字在 \(2\) 进制下的值所对应的 \(01\) 位。

比如，对于一个数 \(4\), 其二进制下表示为 \(1,0,0\)。那么，我们就可以如下建树:

1
|
0
|
0

如果，我们又有一个数 \(5\), 其二进制表示为 \(1,0,1\), 那么插入之后，\(01Trie\) 就变为：

1
|
0 
|\ 
0 1

2、怎么应用？

考虑如下问题： 给定 \(n\) 个数，求两两之间 \(xor\) 的最大值。那我们就可以对 \(n\) 个数建立一棵 \(01Trie\), 然后固定一个值，遍历一遍 \(Trie\) 树，在遍历时从高往低位贪心即可。

3、关于此题

（以下的“每一位”之类的言语均指二进制状态下）

对于前两个操作，我们可以直接模仿普通的 \(Trie\) 树，记录 \(sum\) 为当前节点经过的数字数量，同时进行加减。在此不再赘述。

对于第三个操作，如下考虑：

1. 如果第 \(i\) 位可以为答案造成贡献，那么我们的 \(l\) 这一位一定要是 \(1\)。
2. 如果 \(l\) 这一位是 \(1\), 那我们肯定优先往 \(x\) 的 \(xor\) 值那边跑，因为这样可以使得值更小。然后加上对应的值即可。
3. 如果 \(l\) 的这一位是 \(0\) 呢？ 那我们这一位肯定也只能是 \(0\)。所以 选择相等的那一边跑，一直到可以再次变小为止。

上代码：

#include 
using namespace std;
#define N 1000010
#define ll long long

template 
inline void read(T& a){
	T x = 0, s = 1;
	char c = getchar();
	while(!isdigit(c)){ if(c == '-') s = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + (c ^ '0'); c = getchar(); }
	a = x * s;
	return ;
}

struct tree{
	int ch[2]; 
	int sum;    // 经过这个节点的数的数量 
	
	tree(){
		for(int i = 0; i < 2; i++)
			ch[i] = 0;
		return ; 
	}
} t[N * 5];

int cnt = 1; 

void build(int now, int x){
	for(int i = (1 << 30); i; i >>= 1){
		bool c = i&x;   // 获取第 i 位 0, 1 
		t[now].sum++; 
		if(!t[now].ch[c]) t[now].ch[c] = ++cnt; 
		now = t[now].ch[c];
	}
	t[now].sum++; 
	return ; 
}

void del(int now, int x){
	for(int i = (1 << 30); i; i >>= 1){
		bool c = i&x;   // 获取第 i 位 0, 1 
		t[now].sum--; 
		if(!t[now].ch[c]) t[now].ch[c] = ++cnt; 
		now = t[now].ch[c]; 
	}
	t[now].sum--;
	return ;  
}

int query(int now, int x, int k){
	bool c1, c2; 
	int ans = 0;
	for(int i = 1 << 30; i; i >>= 1){
		c1 = x&i, c2 = k&i; 
		if(c1 < c2)
			ans += t[t[now].ch[0]].sum; 
		if(c1 && c2)
			ans += t[t[now].ch[1]].sum; 
		if(!c2)
			now = t[now].ch[c1];
		else now = t[now].ch[c1 ^ 1]; 
	}
	return ans; 
}

int main(){
	int q; read(q);
	while(q--){
		int opt, x, k;
		read(opt), read(x); 
		if(opt == 1){
			build(1, x); 
		}
		else if(opt == 2){
			del(1, x); 
		}
		else{
			read(k); 
			printf("%d\n", query(1, x, k)); 
		}
	}
	return 0; 
}