Codeforces Round #430 (Div. 2)：D. Vitya and Strange Lesson（模拟建树）-白红宇

Codeforces Round #430 (Div. 2)：D. Vitya and Strange Lesson（模拟建树）

阅读量：2143 次

发布时间：2019-04-30

本文共 2361 字，大约阅读时间需要 7 分钟。

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·105) — number of elements in array and number of queries.

Next line contains n integer numbers ai (0 ≤ ai ≤ 3·105) — elements of then array.

Each of next m lines contains query — one integer number x (0 ≤ x ≤ 3·105).

Output

For each query print the answer on a separate line.

     Examples 
       input 
2 21 313
       output 
10
       input 
4 30 1 5 6124
       output 
200

题意：

定义mex(S)为集合S中最小的没出现过的非负整数，例如mex({4,33,0,1,1,5})=2。集合A有n个数，m次操作，每次操作将这n个数全部异或x，然后询问当前mex(A)的值

模拟建树：

①将所有数转换成2进制，因为每个数的最高位不会超过19位，所以将每个数的第20位置为1

例如：5->10000000000000000101 12512->10000011000011100000

②p[x]=1表示所有二进制前缀为x的数全部都出现过

例如：p[131073]=1即p["100000000000000001"]=1意味着"4,5,6,7"这四个数都出现过

③p[]数组搞定后就可以询问了，因为异或满足性质a^b^c = a^(b^c)，所以询问完之后不用更新数组，直接将所有的询问异或起来作为本次询问

④q[j]表示当前询问x（用③处理过）的第j位是1还是0

⑤之后从高位到低位依次检测p[]是否为1

例如：当前处理到第19位（最高位），并且x的第19位为1，若p["11"]=1，那么所有数异或x后满足p["10"]=1，这就说明所有小于1<<18的数都一定存在，答案一定大于1<<18（答案的第19位一定为1），然后继续处理第18位……

#include
   
    #include
    
     #include
     
      int p[1050000], q[20];void Jud(int i){    if(i<=1)		return;    if(p[i*2] && p[i*2+1] && p[i]==0)	{        p[i] = 1;        Jud(i/2);    }}int main(void){	int n, m, a, x, now, ans, i, j, k, b;	b = 1<<19;    scanf("%d%d", &n, &m);    for(i=1;i<=n;i++)	{        scanf("%d", &a);        p[a+b] = 1;        Jud((a+b)/2);    }	now = 0;    for(i=1;i<=m;i++)	{        scanf("%d", &x);        now ^= x;			//因为异或满足性质a^b^c = a^(b^c)，所以查询完之后不用更新数组，直接将所有的询问异或起来作为本次询问即可        for(j=0;j<=18;j++)		{			q[j] = 0;			if(now&(1<
      
       =0;j--)		{			k <<= 1;			if(q[j])			{				if(p[k+1])					ans |= 1<

转载地址：http://timgf.baihongyu.com/

你可能感兴趣的文章