cf842D Vitya and Strange Lesson

题意:给你$n(n\leq 3\times 10^5)$个数,有$m(m\leq 3\times 10^5)$次询问,每次询问给一个数$x$,要你把整个序列所有数都与$x$异或,然后取$mex$值

考虑用一个$trie$维护所有的数的二进制,然后考虑$mex$操作,它是可以在$trie$上通过$\mathcal O(log_n)$求得的。即从根开始,每次尝试取$0$,如果$0$这个结点的子树大小正好是$2^{maxdep-dep}-1$的话,那就证明这个子树是满的不能取,于是这一位只能取$1$了,最后得到的最小字典序的串即为mex的值。

于是考虑处理异或操作。由于异或具有右结合的性质,每次询问等价于和原序列异或上之前所有$x$的异或和。于是这样的话为了询问出mex,考虑这个将要异或的值的每一位:这一位如果是1,那么我们优先取1,相当于这样在已进行了异或操作的序列中,这一位为0了。如果出现前所述的情况,那自然也只能取不相同的数(即mex值的这一位为1)。这样的话每次询问都能在$\mathcal O(log_n)$内完成…

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=3*100000+5;
const int max_log_n=20;
const int siz=2;
struct node{
int id,book,size;
int ch[2];
}pool[maxn*max_log_n];
int n,m,poi=0;
int inv[max_log_n];
void Insert(int x,int id){
int u=0;
for(int i=max_log_n-1;i>=0;--i){
int bt=(x>>i)&1;
if(pool[u].ch[bt]==0){
pool[u].ch[bt]=++poi;
}
u=pool[u].ch[bt];
}
pool[u].book=id;
}
int fac[max_log_n];
void pre()
{
fac[0]=1;
for(int i=1;i<20;i++) fac[i]=fac[i-1]*2;
}
int Getmex()
{
int ret=0,to=0;
int u=0;
for(int i=max_log_n-1;i>=0;--i){
to=inv[i];
if(pool[pool[u].ch[to]].size==fac[i+1]-1){
to^=1;
ret|=(1<<i);
}
u=pool[u].ch[to];
}
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
pre();
int x;
for(int i=1;i<=n;++i){
scanf("%d",&x);
Insert(x,i);
}
for(int i=poi;i>=0;--i){
pool[i].size=1;
if(pool[i].ch[0]!=0) pool[i].size+=pool[pool[i].ch[0]].size;
if(pool[i].ch[1]!=0) pool[i].size+=pool[pool[i].ch[1]].size;
}
for(int i=0;i<m;++i){
scanf("%d",&x);
for(int j=max_log_n-1;j>=0;j--){
inv[j]^=(x>>j)&1;
}
printf("%d\n",Getmex());
}
return 0;
}