其实a^b^c=a^(b^c),那么对于后面的q次请求,我们都可以利用一开始建立的树来进行求解。因为对一个数进行多次异或操作的值,就等于这个数异或上后面多次异或和的值。
那么原问题就转换为了在01字典树里面找到一个数异或上x最小并且没有在树当中出现过,显然是好找的,我们只需要判断走到这个节点它的0边是不是满的或者1边是不是满的来判断即可,那么我们首先对数据进行去重,然后经过某个节点我们就让这个节点计数值+1,这样如果一个数的子树是满的的话,那么它的经过的次数应该就是1<<i(i是指这个数的位数从0开始),因为假如这里是第i+1位,那么i+1位如果我选择了0,那要知道0后面的边是不是已经连满了,满了的话就有2^(i)种可能。
#include<iostream> #include<cstdio> using namespace std; const int N=3e5+10; int curcnt=1; int endge[22*N][2]; int value[22*N][2]; int data[N]; void treeinsert(int num) { int cur=0; for(int i=20;i>=0;i--) { //cout<<cur<<endl; int digit=(num>>i)&1; if(!endge[cur][digit]) { endge[cur][digit]=curcnt++; } value[cur][digit]++; cur=endge[cur][digit]; } } int findnum(int num) { int cur=0; int ans=0; for(int i=20;i>=0;i--) { //cout<<i<<' '; int digit=(num>>i)&1; if(!endge[cur][digit])//没有这条边直接起飞 { //cout<<digit<<' '<<1<<endl; return ans; } else if(endge[cur][digit]&&value[cur][digit]!=(1<<i))//有这条边但不满 { //cout<<digit<<' '<<2<<endl; cur=endge[cur][digit]; } else if(!endge[cur][digit^1]) { //cout<<(digit^1)<<' '<<3<<endl; ans+=(1<<i); return ans; } else { //cout<<i<<' '<<cur<<' '<<endge[cur][digit]<<endl; ans+=(1<<i); cur=endge[cur][digit^1]; } } //cout<<endl; return ans; } int main () { ios::sync_with_stdio(0); cin.tie(0); int n,m; int temp,x; cin>>n>>m; for(int i=1;i<=n;i++) { cin>>x; data[x]=1; } for(int i=1;i<N;i++) { if(data[i]) { treeinsert(i); } } for(int i=1;i<=m;i++) { cin>>x; if(i==1) { temp=x; cout<<findnum(x)<<endl; } else { temp=temp^x; cout<<findnum(temp)<<endl; } } return 0; }