题目地址：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;
}

题目地址：Codeforces：Problem – 714C – Codeforces、vjudge：Sonya and Queries – CodeForces 714C – Virtual Judge

题目描述

Today Sonya learned about long integers and invited all her friends to share the fun. Sonya has an initially empty multiset with integers. Friends give her t queries, each of one of the following type:

1. + ai — add non-negative integer ai to the multiset. Note, that she has a multiset, thus there may be many occurrences of the same integer.
2. - ai — delete a single occurrence of non-negative integer ai from the multiset. It’s guaranteed, that there is at least one ai in the multiset.
3. ? s — count the number of integers in the multiset (with repetitions) that match some pattern s consisting of 0 and 1. In the pattern, 0 stands for the even digits, while 1 stands for the odd. Integer x matches the pattern s, if the parity of the i-th from the right digit in decimal notation matches the i-th from the right digit of the pattern. If the pattern is shorter than this integer, it’s supplemented with 0-s from the left. Similarly, if the integer is shorter than the pattern its decimal notation is supplemented with the 0-s from the left.

For example, if the pattern is s = 010, than integers 92, 2212, 50 and 414 match the pattern, while integers 3, 110, 25 and 1030 do not.
用0代替十进制数中的偶数数码，1代替奇数数码，有三种操作：插入，插入一个十进制数；删除，删除一个已经插入的十进制数；查询，查询符合给定01串的数的个数，符合定义为从右往左与给定串的01数码相同，如果长度不一在左边补0。

输入输出格式

输入格式：
The first line of the input contains an integer t (1 ≤ t ≤ 100 000) — the number of operation Sonya has to perform.
Next t lines provide the descriptions of the queries in order they appear in the input file. The i-th row starts with a character ci — the type of the corresponding operation. If ci is equal to + or - then it’s followed by a space and an integer ai (0 ≤ ai < 10^{18}) given without leading zeroes (unless it’s 0). If ci equals ‘?’ then it’s followed by a space and a sequence of zeroes and onse, giving the pattern of length no more than 18.
It’s guaranteed that there will be at least one query of type ?.
It’s guaranteed that any time some integer is removed from the multiset, there will be at least one occurrence of this integer in it.
输出格式：
For each query of the third type print the number of integers matching the given pattern. Each integer is counted as many times, as it appears in the multiset at this moment of time.

输入输出样例

样例输入1：

12
+ 1
+ 241
? 1
+ 361
- 241
? 0101
+ 101
? 101
- 101
? 101
+ 4000
? 0

样例输出1：

2
1
2
1
1

样例输入2：

4
+ 200
+ 200
- 200
? 0

样例输出2：

1

说明

样例1说明：
Consider the integers matching the patterns from the queries of the third type. Queries are numbered in the order they appear in the input.

1. 1 and 241.
2. 361.
3. 101 and 361.
4. 361.
5. 4000.

题解

这个题乍看一下很有意思。分析一下三种操作，我们发现如果长度不一且长的那个多出来的部分里有1就不能加入答案，于是我们思考能不能把左边的前导0全删去，再反着插入Trie树，这样构建的01Trie直接查询就可以了。对于输入的每个字符串都如此操作，插入删除以及查找都是常规操作。

代码

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

const int tab[10] = {0, 1, 0, 1, 0, 1, 0, 1, 0, 1}; 

int trie[1800005][2], wrd[1800005], siz = 1;

inline bool isop(char c) {
    return c == '+' || c == '-' || c == '?';
}

inline void insert(char* str, int l, int r) {
    int t = 1;
    for(int i = r; i >= l; i--) {
        if(!trie[t][str[i] - '0']) {
            t = trie[t][str[i] - '0'] = ++siz;
        } else {
            t = trie[t][str[i] - '0'];
        }
    }
    wrd[t]++;
}

inline int search(char* str, int l, int r) {
    int t = 1;
    for(int i = r; i >= l; i--) {
        if(!trie[t][str[i] - '0']) {
            return 0;
        } else {
            t = trie[t][str[i] - '0'];
        }
    }
    return wrd[t];
}

inline void delet(char* str, int l, int r) {
    int t = 1;
    for(int i = r; i >= l; i--) {
        if(!trie[t][str[i] - '0']) {
            return;
        } else {
            t = trie[t][str[i] - '0'];
        }
    }
    wrd[t]--;
}

inline int proc(char* str) {
    int len = strlen(str), res = len - 1;
    for(int i = 0; i < len; i++) {
        str[i] = tab[str[i] - '0'] + '0';
        if(str[i] == '1' && res == len - 1) res = i;
    } 
    return res;
}

int t;
char op, str[20];

int main() {
    scanf("%d", &t);
    for(int i = 0; i < t; i++) {
        while(!isop(op = getchar()));
        scanf("%s", str);
        if(op == '+') {
            insert(str, proc(str), strlen(str) - 1);
        } else if(op == '-') {
            delet(str, proc(str), strlen(str) - 1);
        } else {
            printf("%d\n", search(str, proc(str), strlen(str) - 1));
        }
    }
    return 0;
}