Codeforces 842 D. Vitya and Strange Lesson （trie）

Codeforces 842 D. Vitya and Strange Lesson （trie）

Description

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.

Input

First line contains two integer numbers n and m (1 ≤ n, m ≤ 3·10^5) — number of elements in array and number of queries.Next line contains n integer numbers ai (0 ≤ ai ≤ 3·10^5) — elements of then array.Each of next m lines contains query — one integer number x (0 ≤ x ≤ 3·10^5).

Output

For each query print the answer on a separate line.

Sample Input

5 40 1 5 6 71145

Sample Output

2202

题意

给出长度为 n 的非负整数序列，求该序列异或 x 以后的 mex 值。

思路

将所有的数字以二进制的方式插入到 trie 树中，然后我们便可以很方便的求出一个序列的 mex 值。

假如要全局异或一个数 x ，且 x 的二进制从高到低第 i 位是 1 ，则 trie 树中的第 i 层所有节点都要翻转左右孩子。

AC 代码

#include using namespace std;const int maxn = 1e7+10;const int maxm = 20;int n,m,tot;int a[maxn];struct node{ int cnt,res; node *next[2];} pn[maxn],*root;void insert(int x) //trie树构建{ node *p=root; p->cnt++; for(int i=maxm; ~i; i--) { int k=(x>>i)&1; if(!p->next[k])p->next[k]=&pn[tot++]; p=p->next[k]; p->cnt++; }}void push_down(node *p,int d) //异或时反转左右孩子{ for(int i=0; i<2; i++) if(p->next[i]) p->next[i]->res^=p->res; if((p->res>>d)&1) swap(p->next[0],p->next[1]); p->res=0;}void solve(){ int ans=0; node *p=root; for(int i=maxm; ~i; i--) { push_down(p,i); if((p->next[0]?p->next[0]->cnt:0)!=(1<next[0]; else p=p->next[1],ans|=1<>n>>m; for(int i=0; i>a[i]; sort(a,a+n); n = unique(a,a+n)-a; root = &pn[tot++]; for(int i=0; i>x; root->res^=x; solve(); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。