Vitya and Strange Lesson

题意：
给定长度为的序列，次操作，每次对序列的所有数都异或上一个数，问每次异或后，没有出现在序列中的最小自然数的值。
数据范围：

考虑本问题时，当序列异或上得到序列时，初始状态中不存在于序列中的所有数一起组成的序列异或上得到序列时，和一定也是无交集的。

题解1：
所以问题转化为将所有不存在于序列中的自然数插入树中，每次查询时只需要对，找到其中与异或起来得到的值最小的数，即为答案。这里的是异或上前次询问后的值的。

代码1：

#include<bits/stdc++.h>
using namespace std;

const int N = 6e5 + 10;
int son[N * 21][2], idx;
int st[N * 21];
int n, m;

void insert(int x) {
    int p = 0;
    for(int i = 20; i >= 0; --i) {
        int u = x >> i & 1;
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
} 

int query(int x) {
    int res = 0, p = 0;
    for(int i = 20; i >= 0; --i) {
        int u = x >> i & 1;
        if(son[p][u]) res = res * 2 + u, p = son[p][u];
        else res = res * 2 + !u, p = son[p][!u];
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        st[x] = true;
    }
    //将所有初始不在a中的元素加入 
    for(int i = 0; i < N; ++i) 
        if(!st[i]) insert(i);

    //对于当前的trie树中的元素，如果其不在a中，则对应其中可以求出一个最小的 
    int ans = 0;
    for(int i = 1; i <= m; ++i) {
        int x; 
        scanf("%d", &x);
        ans ^= x;
        printf("%d\n", query(ans) ^ ans);
    }

    return 0;
}

题解2：
考虑将序列插入树，同时记录每个结点被使用的次数，考虑到一个结点被使用的次数为最多为其次。所以在查询时只要看当前优先选择的数是否被使用了次即可，如果没有则优先选择，否则被迫选择另一边。而优先选择的条件一定是与当前的值二进制相同的一边，保证异或后答案尽可能小。

代码2：

#include<bits/stdc++.h>
using namespace std;

const int N = 6e5 + 10;
int ok[N];
int son[N * 32][2], cnt[N * 32], idx;
int n, m;

void insert(int x) {
    int p = 0;
    for(int i = 20; i >= 0; --i) {
        int u = x >> i & 1;
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
        ++cnt[p];
    }
}

int query(int x) {
    int p = 0, res = 0;
    for(int i = 20; i >= 0; --i) {
        int u = x >> i & 1;
        if(cnt[son[p][u]] == (1 << i)) res = res * 2 + !u, p = son[p][!u];
        else res = res * 2 + u, p = son[p][u];
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        int x; scanf("%d", &x);
        if(ok[x]) continue;
        ok[x] = true;
        insert(x);
    }
    int ans = 0;
    while(m--) {
        int x; scanf("%d", &x);
        ans ^= x;
        printf("%d\n", query(ans) ^ ans);
    }
    return 0;
}