Vitya and Strange Lesson

做法：01字典树

题意：

mex 是一个序列中没有出现过的最小非负整数。

给出你一个长度为 的非负整数序列以及 个询问，每次询问先给你一个整数 ，然后：

• 把序列中所有数异或上
• 输出序列的 mex

注意，在每个询问过后序列是发生变化的。

思路：

• 1.先插入原数组中每一个数（重复的不需要再插入）
• 2.每次更新数组比较麻烦，所以可以等价与把每次异或的值异或起来，查找异或起来的值
• 3.对于异或出来的值，在01trie上贪心的找，如果能找到和他当前位相等的值时，判断一下他的子树中的数字是否满足前面所有的数都在

代码

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=3e5+10;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;

int ans,x,temp;
bool st[N];

struct Trie {
    int nex[N*32][2],cnt=0;
     int cntp[N*32];

    void insert(int x) { 
        int p = 0;//下标 
        for (int i = 30; i >= 0; i--) {
            int c = x>>i&1;
            if (!nex[p][c]) nex[p][c] = ++cnt; 
            p = nex[p][c];
            cntp[p]++; //前缀出现次数 
        }
    }
    int find(int x) {
        int p = 0,res = 0;
        for (int i = 30; i >= 0; i--) {
            int c = x>>i&1;
            if (cntp[nex[p][c]]==(1<<i)) p=nex[p][c^1],res|=(1<<i);
            else p=nex[p][c];
        }
        return res;
    }
} t;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef DEBUG
    freopen("F:/laji/1.in", "r", stdin);
//    freopen("F:/laji/2.out", "w", stdout);
#endif
    int n,m;
    cin>>n>>m;
    _for(i,n){
        cin>>x;
        if(st[x]) continue;
        else st[x]=1;
        t.insert(x);
    }
    _for(i,m){
        cin>>x;
        temp^=x;
        cout<<t.find(temp)<<"\n";
    }
    return 0;
}