Vitya and Strange Lesson

要求个数和异或后,没有出现的最小数字

那么这个数异或后的值是没有用的,因为都出现过

所以我们把所有不是这个数的数插入字典树

这样这些数异或后一定是没有出现的数字

这样贪心找最小值即可

还有一个小技巧,因为

所以不需要真的改变数组的值,只需要把操作数异或起来就可以

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=6e6+10;
int n,m,zi[maxn][3],id,isok[maxn];
bool ok[maxn];
void insert(int x)
{
    int now=0;
    for(int i=30;i>=0;i--)
    {
        int w = ((x>>i)&1);
        if( !zi[now][w] )    zi[now][w]=++id;
        now = zi[now][w];
    }
    isok[now]=x;
}
int ask(int x)
{
    int ans=0,now=0;
    for(int i=30;i>=0;i--)
    {
        int w = ((x>>i)&1);
        if( zi[now][w] )    now = zi[now][w];
        else    now = zi[now][w^1],ans+=(1<<i);
    }
    return ans;
}
signed main()
{
    cin >> n >> m;
    int maxx=0;
    for(int i=1;i<=n;i++)
    {
        int x; scanf("%lld",&x);
        ok[x]=1;    maxx = max( maxx,x );
    }
    maxx = (maxx+1)*2;
    for(int i=0;i<=maxx;i++)
        if( !ok[i] )    insert(i);
    int pre=0;
    for(int i=1;i<=m;i++)
    {
        int x; scanf("%lld",&x);
        pre^=x;
        printf("%lld\n",ask(pre)); 
    }
}