题意:
每次询问一个x,问数组中的数与x异或后,不存在的最小的数。
分析:
01字典树上贪心选择一下,选择的时候判断左孩子和右孩子满不满。每次询问的亦或值x只要一直累?就行
#include<bits/stdc++.h>
using namespace std;
#define N 300005
#define H 19
bool vis[N];
struct node
{node *nxt[2];int sz;node(){sz=0;nxt[0]=nxt[1]=NULL;}
};
void Insert(node *rt, int x)
{for(int i=H; i>=0; i--){int id=(x>>i)&1;if(rt->nxt[id]==NULL) rt->nxt[id]=new node();rt=rt->nxt[id];rt->sz++;}
}
int getsz(node *p)
{if(p==NULL) return 0;return p->sz;
}
int query(node *rt, int X, int h)
{if(rt==NULL) return 0;if((X>>h)&1){if(getsz(rt->nxt[1])!=(1<<h)) return query(rt->nxt[1], X, h-1);else return query(rt->nxt[0], X, h-1)+(1<<h);}else{if(getsz(rt->nxt[0])!=(1<<h)) return query(rt->nxt[0], X, h-1);else return query(rt->nxt[1], X, h-1)+(1<<h);}
}void solve()
{node *rt=new node();int n, m, X=0;cin>>n>>m;for(int i=1; i<=n; i++){int x;cin>>x;if(!vis[x]) Insert(rt, x), vis[x]=1;}while(m--){int x;cin>>x;X^=x;cout << query(rt, X, H) << endl;}
}
int main()
{solve();return 0;
}