Vitya and Strange Lesson

Vitya and Strange Lesson

题意

n个数，m个操作，对于每一个操作

1. 首先给出一个数 x , 每一个 a [ i ] 更新为与 x 按位异或的结果
2. 求出这 n 个数的 Mex

分析

1. 首先这 m 个操作的 x 是可以重合在一起的，也就是说，并不用每输入一次 x 就将数组更新
2. 求Mex：这个Mex是在数组中最小的没有出现过的数，联想我们已经建立的trie树，如果没有异或操作，只询问 Mex那其实就是在 trie 上找最靠左的一个空位。那这个呢？不就是带了个x呗。尽量走一条与x按位异或结果相同的道路。很明显，因为这个数要不存在，说明节点下方的子节点不能将空位全部占满，否则只能走另一条路。

代码

#include<bits/stdc++.h>

using namespace std;

const int N=3e5+10;

int n,m,tot=1;
int tr[2][N*10],siz[N*10];

inline void ins(int x,int i,int &rt)
{
    if(i==-1)
    {
        siz[rt]=1;
        return ;
    }//计算有多少个叶子节点 

    bool c=((x>>i)&1);
    if(!tr[c][rt]) tr[c][rt]=++tot;
    ins(x,i-1,tr[c][rt]);

    siz[rt]=siz[tr[0][rt]]+siz[tr[1][rt]];
}

inline int find(int now)
{
    int ans=0,rt=1;
    for (int i=18;i>=0;i--)
    {
        bool c=((now>>i)&1);
        if(!rt) return ans;
        if(siz[tr[c][rt]]==(1<<i))
            ans+=(1<<i),rt=tr[c^1][rt];
        else rt=tr[c][rt];
    }

    return ans;
}

int main()
{
    memset(tr,0,sizeof(tr));

    scanf("%d%d",&n,&m);
    for (int i=1,x,rt;i<=n;i++)
    {
        scanf("%d",&x);
        rt=1;ins(x,18,rt);
    }
    //应该有多少节点
    int x,now=-1;
    while(m--)
    {
        scanf("%d",&x);
        if(now==-1) now=x;else now^=x;
        printf("%d\n",find(now));
    }

    return 0;
}