题意：给你一个数组，m次操作，每次操作给你个x，把所有数亦或x，每次操作后输出数组的mex值，mex值表示第一个未出现的自然数。
思路：
1.
异或的效果是可以累加的,所以每次操作的x亦或可以叠加起来成X，这样每次操作就是对原数组亦或X。
我们一开始把原数组不存在的数插入到01Trie，现在对原数组进行一次异或操作,则异或之后的a数组的mex值就是 插入
的数组（未出现的值）xor x之后的最小值。找这个最小值很简单，尽量往与x二进制相同方向走即可。
结论的证明见：点击打开链接
2.
一开始把原数组插入到01Trie，用一个num数组记录每个分支中的个数，查询时沿着x的二进制走，因为要找最小的未
出现的，所以尽量走与x二进制相同的，如果要走的子树是满的，则他全部能出现，所以需要换另一颗子树，每次换
子树该层二进制会对结果有贡献。点击打开链接
1代码:
#include<bits/stdc++.h> using namespace std; const int maxn = 3e5+5; const int maxnode = maxn*20; bool vis[(1<<20)+5]; int sz, ch[maxnode][2], val[maxnode]; void init() { sz = 1; memset(ch[0], 0, sizeof(ch[0])); } void Insert(int x) { int u = 0; for(int i = 20; i >= 0; i--) { int idx = (x>>i)&1; if(!ch[u][idx]) { memset(ch[sz], 0, sizeof(ch[sz])); val[sz] = 0; ch[u][idx] = sz++; } u = ch[u][idx]; } val[u] = x; } int Match(int x) { int ans = 0, u = 0; for(int i = 20; i >= 0; i--) { int idx = (x>>i)&1; if(ch[u][idx]) u = ch[u][idx]; else u = ch[u][idx^1]; } return val[u]; } int main(void) { int n, m; while(cin >> n >> m) { init(); memset(vis, 0, sizeof(vis)); for(int i = 1; i <= n; i++) { int tmp; scanf("%d", &tmp); vis[tmp] = 1; } for(int i = 0; i < (1<<20); i++) if(!vis[i]) Insert(i); int cur = 0; while(m--) { int tmp; scanf("%d", &tmp); cur ^= tmp; // cout << cur << ' ' << Match(cur) << endl; printf("%d\n", cur^Match(cur)); } } return 0; }
2代码：
#include<bits/stdc++.h> using namespace std; const int maxn = 3e5+5; const int maxnode = maxn*20; int sz, ch[maxnode][2], val[maxnode], num[maxnode][2]; bool vis[maxn]; void init() { sz = 1; memset(num, 0, sizeof(num)); memset(ch[0], 0, sizeof(ch[0])); } void Insert(int x) { int u = 0; for(int i = 20; i >= 0; i--) { int idx = (x>>i)&1; if(!ch[u][idx]) { memset(ch[sz], 0, sizeof(ch[sz])); val[sz] = 0; ch[u][idx] = sz++; } num[u][idx]++; u = ch[u][idx]; } val[u] = x; } int Match(int x) { int ans = 0, u = 0; for(int i = 20; i >= 0; i--) { int idx = (x>>i)&1; if(num[u][idx] >= (1<<i)) { ans += 1<<i; u = ch[u][1-idx]; } else u = ch[u][idx]; if(!u) break; } return ans; } int main(void) { int n, m; while(cin >> n >> m) { init(); memset(vis, 0, sizeof(vis)); for(int i = 1; i <= n; i++) { int tmp; scanf("%d", &tmp); if(vis[tmp]) continue; //要计数，所以需要去重 vis[tmp] = 1; Insert(tmp); } int cur = 0; while(m--) { int tmp; scanf("%d", &tmp); cur ^= tmp; printf("%d\n", Match(cur)); } } return 0; }
