【cf842D】Vitya and Strange Lesson（01字典树）

D. Vitya and Strange Lesson

题意

数列里有n个数，m次操作，每次给x，让n个数都异或上x。并输出数列的mex值。

题解

01字典树保存每个节点下面有几个数，然后当前总异或的是sw，则sw为1的位的节点左右孩子交换（不用真的交换）。左孩子的值小于左边总节点数则mex在左子树，否则在右子树。

代码

const int N=531000;//3e5<2^19<N
int sw=0;
struct Trie{
int ch[N*20][2];
int cnt[N*20];
int size;
void Build(int node, int pos){
if(pos<0)return;
rep(i,0,2){
ch[node][i]=++size;
cnt[size]=0;
Build(ch[node][i], pos-1);
}
}
void Init(){
size=0;
Build(0,19);
}
void Insert(int node, int pos, int num){
if(pos<0)cnt[node]=1;
if(pos<0) return;
Insert(ch[node][(num>>pos)&1], pos-1, num);
cnt[node]=cnt[ch[node][0]]+cnt[ch[node][1]];
}
int Query(int node, int pos, int num){
if(pos<0)
return num;
int lson=(sw&(1<<pos))?1:0;
if(cnt[ch[node][lson]]<(1<<pos)){
return Query(ch[node][lson], pos-1, num);
}
return Query(ch[node][!lson], pos-1,num+(1<<pos));
}
}trie;
int main() {
int n,m;
while(~scanf("%d%d",&n,&m)){
trie.Init();
sw=0;
rep(i,0,n){
int x;
scanf("%d",&x);
trie.Insert(0,19,x);
}
while(m--){
int x;
scanf("%d",&x);
sw^=x;
printf("%d\n",trie.Query(0,19,0));
}
puts("");
}
return 0;
}

自从用了cf上偷来的开头模板以后，感觉写代码速度也快了。但是，代码像裙子越短越性感。所以博客上就不放头文件了。

其实可以像线段树一样写，写得更短了哈哈：

const int N=531000;
int sw=0;
struct Trie{
int cnt[N*20];
void Insert(int node, int pos, int num){
if(pos<0){cnt[node]=1;return;}
Insert(node<<1|((num>>pos)&1), pos-1, num);
cnt[node]=cnt[node<<1]+cnt[node<<1|1];
}
int Query(int node, int pos, int num){
if(pos<0) return num;
int cur=(sw>>pos)&1;
cur|=node<<1;
if(cnt[cur]<(1<<pos)) return Query(cur, pos-1, num);
return Query(cur^1, pos-1,num+(1<<pos));
}
}trie;
int main() {
int n,m;
scanf("%d%d",&n,&m);
rep(i,0,n){
int x;
scanf("%d",&x);
trie.Insert(1,19,x);
}
while(m--){
int x;
scanf("%d",&x);
sw^=x;
printf("%d\n",trie.Query(1,19,0));
}
return 0;
}