[CF842D]Vitya and Strange Lesson 题解
题目地址: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:
- Perform the bitwise addition operation modulo 2 (xor) of each array element with the number x.
- 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;
}