Vitya and Strange Lesson（mex，01字典树）

题目：

给个数的序列，个操作。每次操作给一个，先使当前个数的序列一遍。然后求序列的输出。：未在序列中出现的最小非负整数。

做法：

根据的性质：序列。
于是我们不用将累计在序列中，而是可以转化为累计在中。我们将个数插入字典树。每次操作相当于：给一个，在字典树中跑一个值最小且不在树上的数。其实本质还是用字典树实现高位贪心。字典树上每个结点维护该子树的，代表下面存的数的数量。若第位值为，先要判断其子树是否满了，若未满则代表了在该子树下，第位为。递归做下去就能一位一位得到了。

代码：

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
struct Trie{
    static const int N = 5e6 + 7;
    int tot, ch[N][2], sze[N], val[N];
    void insert(int x, int dep, int rt){
        if (dep == -1){
            val[rt] = x, sze[rt] = 1; return;
        }
        int b = (x>>dep)&1;
        if (!ch[rt][b]) ch[rt][b] = ++tot;
        insert(x, dep-1, ch[rt][b]);
        sze[rt] = 0;
        if (ch[rt][0]) sze[rt] += sze[ch[rt][0]];
        if (ch[rt][1]) sze[rt] += sze[ch[rt][1]];
    }
    int ask(int x){
        int now = 0, ans = 0;
        for (int i = 20; i >= 0; --i){
            int b = (x>>i)&1;
            if (!ch[now][b]) break;
            if (ch[now][b] && sze[ch[now][b]] < (1<<i)){
                now = ch[now][b];
            }else if (!ch[now][b^1]){
                ans |= (1<<i); break;
            }else{
                now = ch[now][b^1], ans |= (1<<i);
            }
        }
        return ans;
    }
}trie;
int main(void){
    IOS;
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        int x; cin >> x; trie.insert(x, 20, 0);
    }
    int now = 0;
    while (m--){
        int x; cin >> x; now ^= x;
        cout << trie.ask(now) << endl;
    }
    return 0;
}