此题其实为 (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) 为当前节点经过的数字数量，同时进行加减。在此不再赘述。
对于第三个操作，如下考虑：
- 如果第 (i) 位可以为答案造成贡献，那么我们的 (l) 这一位一定要是 (1)。
- 如果 (l) 这一位是 (1), 那我们肯定优先往 (x) 的 (xor) 值那边跑，因为这样可以使得值更小。然后加上对应的值即可。
- 如果 (l) 的这一位是 (0) 呢？ 那我们这一位肯定也只能是 (0)。所以 选择相等的那一边跑，一直到可以再次变小为止。
上代码：
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define ll long long
template <class T>
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
", query(1, x, k));
}
}
return 0;
}