题目地址：Codeforces：Problem – 842D – Codeforces、vjudge：Vitya and Strange Lesson – CodeForces 842D – Virtual Judge

题目描述

Today at the lesson Vitya learned a very interesting function — mex. Mex of a sequence of numbers is the minimum non-negative number that is not present in the sequence as element. For example, mex([4, 33, 0, 1, 1, 5]) = 2 and mex([1, 2, 3]) = 0.
Vitya quickly understood all tasks of the teacher, but can you do the same?
You are given an array consisting of n non-negative integers, and m queries. Each query is characterized by one number x and consists of the following consecutive steps:

1. Perform the bitwise addition operation modulo 2 (xor) of each array element with the number x.
2. Find mex of the resulting array.

Note that after each query the array changes.
给一个数列，每次查询给出一个值x，先对数列中每个元素异或上x，然后查询数列的mex值（即数列中不包含的最小非负整数）。

输入输出格式

输入格式：
First line contains two integer numbers n and m (1 ≤ n, m ≤ 3 \cdot 10^5) — number of elements in array and number of queries.
Next line contains n integer numbers ai (0 ≤ ai ≤ 3 \cdot 10^5) — elements of then array.
Each of next m lines contains query — one integer number x (0 ≤ x ≤ 3 \cdot 10^5).
输出格式：
For each query print the answer on a separate line.

输入输出样例

输入样例#1：

2 2
1 3
1
3

输出样例#1：

1
0

输入样例#2：

4 3
0 1 5 6
1
2
4

输出样例#2：

2
0
0

输入样例#3：

5 4
0 1 5 6 7
1
1
4
5

输出样例#3：

2
2
0
2

题解

冷静分析一下这题，发现异或操作是对整个数列的，这个直接在外面维护标记就行了，因为异或满足结合律。找mex是一个难点，需要用01Trie处理。
先把数列元素去个重插入01Trie中，预先算好发现数据最大是大约19位二进制，那就存20位算了，插入的同时统计一下每个子树中有多少数。每次查询的时候先把查询的这一位异或上，即如果要异或的数为1，则1当0处理，0当1处理。要异或的数为0时，选择0子树肯定是比较小的，但是要看一下这个子树有没有满，满了只能向1走，否则向0走，当然如果子树为空直接返回即可。每次走的时候维护一个结果，如果向1走要在结果的这一位上设成1。这个结果就是询问的答案。

代码

// Code by KSkun, 2018/2
#include <cstdio>
#include <algorithm>

int trie[6000005][2], tot = 1, has[6000005];

inline void insert(int n) {
    int t = 1;
    for(int i = 20; i > 0; i--) {
        has[t]++;
        if(n & (1 << (i - 1))) {
            if(!trie[t][1]) trie[t][1] = ++tot;
            t = trie[t][1];
        } else {
            if(!trie[t][0]) trie[t][0] = ++tot;
            t = trie[t][0];
        }
    }
    has[t]++;
}

int dlt = 0;

inline int query() {
    int t = 1, res = 0;
    for(int i = 20; i > 0; i--) {
        if(dlt & (1 << (i - 1))) {
            if(!trie[t][1]) {
                return res;
            } else if(has[trie[t][1]] < (1 << (i - 1))) {
                t = trie[t][1];
            } else {
                t = trie[t][0];
                res += (1 << (i - 1));
            }
        } else {
            if(!trie[t][0]) {
                return res;
            } else if(has[trie[t][0]] < (1 << (i - 1))) {
                t = trie[t][0];
            } else {
                t = trie[t][1];
                res += (1 << (i - 1));
            }
        }
    }
    return res;
}

int n, m, a[300005], t;

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    std::sort(a, a + n);
    n = std::unique(a, a + n) - a;
    for(int i = 0; i < n; i++) {
        insert(a[i]);
    }
    for(int i = 0; i < m; i++) {
        scanf("%d", &t);
        dlt ^= t;
        printf("%d\n", query());
    }
    return 0;
}