CF842D Vitya and Strange Lesson

01trie真是个可爱的算法呢！

传送门

差不多是01trie的模板吧。

所谓01trie，就是把我们平时处理字符串的普通trie树边的信息改为一个数字二进制下这一位是0还是1。

这样就可以将一个数字变成一个01串存下来，做一些ans,or,xor之类的二进制操作。

本题要求序列在xor一个数下的mex，正常求mex的方法是在值域上建树，如果左子树不满就走向左子树，否则走向右子树。

同理，在trie里计一下数的个数就好了。

一些细节：不用把满二叉树建出来，找到一个不存在的节点直接默认我们之后的位上全是0，return好了。

我的代码有一些奇怪的小优化，可能不太好懂。

#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int t[6000005][2],k,n,maxn,num;
int c[300005],sum[600005][2],m;
inline void insert(int x){
    int u=1;
    for (int i=maxn; i>=0; i--){
        int a=((x&(1<<i))!=0);
        if (!t[u][a]) t[u][a]=++num;
        sum[u][a]++;u=t[u][a];
    }
}
inline int query(){
    int u=1,ans=0;
    for (int i=maxn; i>=0; i--){
        int a=((k&(1<<i))!=0);
        if (sum[u][a]<(1<<i)){
            u=t[u][a]; if (!u) return ans;
        }
        else{
            u=t[u][a^1];
            ans|=(1<<i); if (!u) return ans;
        }
    }
    return ans;
}
int main(){
    int x;
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; i++) scanf("%d",&c[i]);
    sort(c+1,c+n+1);
    maxn=min((int)log2(c[n])+1,20);
    if (c[n]==0) maxn=1;
    num=1; c[0]=-1;
    for (int i=1; i<=n; i++)
        if (c[i]!=c[i-1]) insert(c[i]);
    while (m--){
        scanf("%d",&x);
        k^=x; printf("%d\n",query());
    }
    return 0;
}