Vitya and Strange Lesson

题目大意

就是给定一串序列，然后有一系列全局异或操作，问你每次操作后，没有出现过的最小的非负整数

分析

考虑如何在 字典树上找到最小没有出现过的数

• 每次插入一个数的时候，对形成的路径上的每一个点权值
• 如果这个点对应的是二进制下第 位(最低位为 )，且这个点的权值为 ，那么这颗子树一定是个满二叉树，即这个点的子树中并不存在没有出现过的非负整数，所以这个点不能出现在我们的查询路径中
• 所以如果 的那棵子树满了就可以直接去到 的子树中，这样能保证至少有一棵树不是满二叉树

所以，第一个不在字典树上的数就是我们要求的的答案
然后的问题就是如何做到全局异或一个值呢？
首先来想一想，如果没有全局异或的操作，我们应该如何查询？
按照上面的方法，我们的查询应该是从零开始找，然后在从高位向低位跳的时候，如果 的那棵子树满了，就跳向 的子树，直到找到第一个不在树上的数
那如果有异或呢，我们可以很轻松的得到异或运算也是存在结合律的，所以有
所以说，对于每一次的全局异或，都是可以异或到 上，而不用对 字典树进行修改操作的
所以这道题就顺利解决了

Code

#include <cstdio>

const int maxn = 3e5 + 10;
int son[maxn * 20][2], id;
int size[maxn * 20][2], temp;
bool vis[maxn];

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

inline void insert() 
{
    int p(0), x(__read());
    if (vis[x]) return;
    vis[x] = 1;
    for (int i = 18; ~i; --i) {
        int sta = x >> i & 1;
        if (!son[p][sta]) son[p][sta] = ++id;
        size[p][sta]++;
        p = son[p][sta];
    }
}

inline int query()
{
    int p(0), res(0);
    for (int i = 18; ~i; --i) {
        int sta = temp >> i & 1;
        if (size[p][sta] == (1 << i)) p = son[p][sta ^ 1], res |= (1 << i);
        else p = son[p][sta];
        if (!p) return res;
    }
    return res;
}

int main()
{
    int n = __read(), m = __read();
    for (int i = 1; i <= n; ++i) insert();
    while (m--) {
        temp ^= __read();
        printf ("%d\n", query());
    }
}