一般异或问题都可以转换成字典树的问题，，我一开始的想法有点小问题，改一下就好了
下面的代码是逆向建树的，数据量大就不行
/*3 01字典树 根据异或性质，a1!=a2 ==> a1^x1^..^xn != a2^x1^..an 把修改转换成不同的询问 先把初始集合里没有的数建立成字典树 每次询问找的是字典树里异或x最小的值 */ #include<bits/stdc++.h> using namespace std; #define maxn 300005 int buf[maxn]; void getbuf(int a){ for(int i=1;i<=20;i++) buf[i]=a%2,a/=2; for(int i=1,j=20; i<=j; i++,j--) swap(buf[i],buf[j]); } struct Trie{ int root,L; int nxt[maxn*30][2],end[maxn*30]; int newnode(){ nxt[L][0]=nxt[L][1]=-1; return L++; } void init(){ L=0;root=newnode(); } void insert(int a){ getbuf(a); //for(int i=1;i<=20;i++)printf("%d ",buf[i]); int now=root; for(int i=1;i<=20;i++){ if(nxt[now][buf[i]]==-1) nxt[now][buf[i]]=newnode(); now=nxt[now][buf[i]]; } end[now]=a; } int query(int a){//要找和a异或最小的数，就是碰到1时就往1走，碰到0时就往0走 getbuf(a); //for(int i=1;i<=20;i++)printf("%d ",buf[i]); int now=root; for(int i=1;i<=20;i++){ if(nxt[now][buf[i]]==-1) now=nxt[now][buf[i]^1]; else now=nxt[now][buf[i]]; } return end[now]; } }tr; int n,m,flag[maxn],a,Max,x; vector<int>v; int main(){ tr.init(); cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a;flag[a]=1,Max=max(a,Max); } for(int i=0;i<=300000;i++) if(flag[i]==0)v.push_back(i); for(int i=0;i<v.size();i++) tr.insert(v[i]); m--,cin>>x; printf("%d ",tr.query(x)^x); while(m--){ cin>>a; x^=a; printf("%d ",tr.query(x)^x); } }
如果是把集合中存在的元素进行建树，就不会出现字典树大小无法确定的问题，但是每次查询要改一下，即如果第i位是1，那就往字典树的0子树找，反之往1子树找，并且如果先找的子树已经满了，即mex的结果不可能再这棵子树中找到，那么就往另一颗子树找即可
#include <stdio.h> #include <string.h> #include<iostream> #define MAX(a,b) ((a)>(b)?(a):(b)) #define NODE 3200010 #define N 300010 using namespace std; int n; int v[N]; int node; int next[NODE][2]; int end[NODE]; int num[NODE][2]; bool vis[NODE]; void add(int cur,int k) { memset(next[node],0,sizeof(next[node])); end[node]=0; next[cur][k]=node++; } int cal(int x) { int i,k,cur=0,t1; int res=0; for(i=19;i>=0;i--) { k=((1<<i)&x)?1:0; if(num[cur][k]>=1<<(i)){ res+=1<<i; cur=next[cur][1-k]; }else{ cur=next[cur][k]; } if(cur==0)break; //这里是为了当进入到一个个数为0的分支，可以直接break } //return (x^end[cur]); 如果是求最大值 return res; } int main() { int i,j,k,x,cur; int ans,m; //freopen("in.txt","r",stdin); while(~scanf("%d %d",&n,&m)) { node=1; memset(next[0],0,sizeof(next[0])); for(i=0;i<n;i++) { scanf("%d",&x); if(vis[x])continue; vis[x]=1; v[i]=x; cur=0; for(j=19;j>=0;j--) { k=((1<<j)&x)?1:0; if(next[cur][k]==0)add(cur,k); num[cur][k]++; cur=next[cur][k]; } end[cur]=x; } int t1,t2; t1=0; for(ans=i=0;i<m;i++){ //求最大值是max(ans,cal(v[i])) cin >> t2; t1^=t2; cout << cal(t1) << endl; } } return 0; }
另外这题用线段树解也可以，即建600000个结点，每个叶子结点维护的就是元素中的集合，然后每次查询还是按01字典树找最小异或值那一套方法就行了