【-72】842D.Vitya and Strange Lesson[trie]

题目描述

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.

输入输出格式

输入格式

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)$.

输出格式

For each query print the answer on a separate line.

输入输出样例

输入样例1

1
2
3
4
2 2
1 3
1
3

输出样例1

1
2
1
0

输入样例2

1
2
3
4
5
4 3
0 1 5 6
1
2
4

输出样例2

1
2
3
2
0
0

输入样例3

1
2
3
4
5
6
5 4
0 1 5 6 7
1
1
4
5

输出样例3

1
2
3
4
2
2
0
2

题解

哇这题怎么搞啊,要我搞肯定是n*m暴搞, 得部分分算了哎 显然不存在的.

“有人说这题是trie”

然后发现,可以用二进制建一颗trie(正着建),然后xor的话,如果某一位是1,那么相当于把这一层的左子树和右子树交换,然后继续往后扫.每次这样模拟

蛤可以用极端数据卡掉我的方法.

然后惊奇的发现,如果以某个点为根的树,是一个满的树(除开最底层节点所有的节点都有0子树和1子树),怎么异或也没有影响,而且mex肯定不会在里面.

然后想起 $a xor b xor c=a xor (b xorc)$

所以每次只要拿初始的trie查询就好.

如果这一位是1就往子树1扫(想一想为什么),如果子树1是满的就扫子树0,没有子树0直接输出.

0的话相反.

然后如果要异或的值是a,那么如果a没在原数组中出现过,可以直接输出0(想一想,为什么)

具体见代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<bits/stdc++.h>
using namespace std;
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(s>='0'&&s<='9'));
if(s==EOF)exit(0);
if(s=='-')base=-1,s=getchar();
while(s>='0'&&s<='9')
{
k=k*10+(s-'0');
s=getchar();
}
return k*base;
}
struct node
{
int flag;
int s;
int ch[2];//0,1
} a[1000000];
int n,m,maxx,d,now;
int D[310000];
int Q[310000];
int f[310000];
int b[23],lb;
int er[23];
void dfs(int x)//统计子节点个数
{
a[x].s=1;
if (a[x].ch[0]!=0)//有子树0
{
dfs(a[x].ch[0]);//往下扫
a[x].s+=a[a[x].ch[0]].s;//统计
}
if (a[x].ch[1]!=0)//有子树1
{
dfs(a[x].ch[1]);//往下扫
a[x].s+=a[a[x].ch[1]].s;//统计
}
}
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
n=read();
m=read();
d=1;
for (int i=1;i<=n;i++)
{
D[i]=read();
f[D[i]]++;//统计D[i]出现次数
lb=23;
memset(b,0,sizeof(b));
while (D[i])//转成二进制(正着存)
{
lb--;
b[lb]=(D[i]%2);
D[i]/=2;
}
now=1;
for (int j=1;j<=22;j++)//建一棵trie
{
if (a[now].ch[b[j]]==0)
{
d++;a[now].ch[b[j]]=d;
}
now=a[now].ch[b[j]];
}
a[now].flag=1;//显然毫无意义
}
dfs(1);
er[0]=1;
er[1]=2;
for (int i=2;i<=22;i++) er[i]=er[i-1]*2;//er[i]表示2^i
for (int i=1;i<=m;i++)
{
Q[i]=read();
Q[i]=Q[i]^Q[i-1];
if (!f[Q[i]])//如果没在原数组中出现直接输出0
{
printf("0\n");
continue;
}
lb=23;
memset(b,0,sizeof(b));
int QQ=Q[i];
while (QQ)//转成二进制
{
lb--;
b[lb]=(QQ%2);
QQ/=2;
}
now=1;
int now2=1;int s=0;
while (true)
{
if (b[now2]==0)//0:异或后子树不变
{
if (a[now].ch[0]!=0)//有0子树
{
if (a[a[now].ch[0]].s==er[23-now2]-1)//0子树满了
{
if (a[now].ch[1]!=0)//有1子树
{
s+=er[23-now2-1];//把这一位的1所对应的值加上去
now=a[now].ch[1];//往下扫
} else
{
s+=er[23-now2-1];//把这一位的1所对应的值加上去
printf("%d\n",s);//输出
break;
}
} else now=a[now].ch[0];//0子树没满就扫0子树
} else {printf("%d\n",s);break;}
}
else //异或后左子树和右子树变
{
if (a[now].ch[1]!=0)//有1子树
{
if (a[a[now].ch[1]].s==er[23-now2]-1)//1子树满了
{
if (a[now].ch[0]!=0)//有0子树
{
s+=er[23-now2-1];//加上这一位1所对应的值
now=a[now].ch[0];//往下扫
} else
{
s+=er[23-now2-1];printf("%d\n",s);//统上,输出
break;
}
} else now=a[now].ch[1];//往下扫
} else
{printf("%d\n",s);break;}
}
now2++;//深度++
if (now2==23) break;//扫完了
}
}
}