题意：

mex为数列中没有出现过的第一个非负整数。给出一个数列，每次询问给出一个x，问每个数异或x后数列的mex。

思路：

又是一道知道怎么做但不会写的题…

之前就知道有01字典树来处理异或的这种操作，但一直没有写过，这是第一道01字典树吧…

字典树是高位在上，以保证每次都先满足高位最大。

对于每一次异或，如果这个位是0，就不变，如果是1，就对换左右子树。

这里可以用到一个懒标记，只有用到的时候进行标记下放。

mex的查询就尽量走左子树，如果左子树为空或者被访问的次数小于2^层数的话，就可以往左子树走（注意这里的层数是标在每一层结点的中间的）。

收获是知道了这种01字典树的操作的要怎么实现吧。

代码：

bool vis[300010];
struct node
{
    node *child[2];
    int num;//有几个数经过这个结点
    int f;//懒标记
    node()
    {
        num=0;
        f=0;
        child[0]=child[1]=NULL;
    }
};
void insert(node *p,int x)
{
    p->num++;
    for(int i=20;i>=0;i--)
    {
        int id=(x>>i)&1;
        //printf("%d ",id);
        if(p->child[id]==NULL)p->child[id]=new node();
        p=p->child[id];
        p->num++;
    }
    //printf("\n");
}
void pushdown(node *p,int dep)
{
    //printf("!\n");
    for(int i=0;i<2;i++)
        if(p->child[i])
            p->child[i]->f^=p->f;
    if((p->f>>dep)&1)
        swap(p->child[0],p->child[1]);
    p->f=0;
}
int find(node *p)
{
    int ans=0;
    for(int i=20;i>=0;i--)
    {
        pushdown(p,i);
        if(p->child[0]==NULL||p->child[0]->num<(1<<i))//下面有空的结点
        {
            //if(p->child[0]!=NULL)printf("(%d,%d)",p->child[0]->num,1<<i);
            p=p->child[0];
        }
        else
        {
            //printf("[%d,%d]\n",1<<i,p->child[0]->num);
            p=p->child[1];
            ans+=1<<i;
        }
        if(p==NULL)return ans;//NULL是不能访问的，下面都为0
    }
    return ans;
}
int main()
{
    int m,n,x;
    scanf("%d%d",&n,&m);
    node *root=new node();
    while(n--)
    {
        scanf("%d",&x);
        if(!vis[x])
        {
            vis[x]=true;
            insert(root,x);
        }
    }
    //printf("[[%d]]\n",find(root));
    while(m--)
    {
        scanf("%d",&x);
        root->f^=x;
        printf("%d\n",find(root));
    }
    return 0;
}