D、Vitya and Strange Lesson(字典树)
题意:
给一个长度为\(n\)的非负整数序列，\(m\)次操作,每次先全局异或\(x\)，再查询\(mex\)
\(1<=n<=3e5\)
\(0<=a_i<=3e5\)
\(0<=x<=3e5\)
思路：求\(mex\)可以通过按从高位到低位建字典树，判断左子树是否满，若未满，贪心往走，否则往右走，这样查询是\(log\)的
现在就是异或修改，考虑x的第i位，若为1,则以第i-1层结点为根的左右子树都需要交换
如果每次暴力修改所有是会超时的，使用线段树区间更新那样的技巧，要查询某段区间的时候再做更新。
所以用打标记的方法下传就好了
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define ls(i) seg[i].lc
#define rs(i) seg[i].rc
using namespace std;
void read(int &x){
char c = getchar();
x = 0;
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - '0',c = getchar();
}
const int N = 3e5 + 10;
int base[20];
struct T{
int lc,rc,cnt,col;
}seg[N * 25];
int tot,root;
void Insert(int &rt,int x,int dep){
if(!rt) rt = ++tot;
if(dep == 0){
seg[rt].cnt = 1;
return ;
}
if(x & base[dep - 1]) Insert(rs(rt),x,dep - 1);
else Insert(ls(rt),x,dep - 1);
seg[rt].cnt = seg[ls(rt)].cnt && seg[rs(rt)].cnt;
}
void pushdown(int rt,int dep){
if(dep < 0) return ;
int col = seg[rt].col;
seg[ls(rt)].col ^= col, seg[rs(rt)].col ^= col;
if(col & base[dep]) swap(seg[rt].lc,seg[rt].rc);
seg[rt].col = 0;
}
int query(int rt,int dep){
if(dep == 0) return 0;
pushdown(rt,dep - 1);
if(!seg[ls(rt)].cnt) return query(ls(rt),dep - 1);///左子树未满，高位到低位尽量往左边走
else return query(rs(rt),dep - 1) + base[dep - 1];///只能往右走
}
int main(){
int x,n,m;
read(n),read(m);
tot = root = 0;
base[0] = 1;
for(int i = 1;i <= 20;i++) base[i] = base[i-1] * 2;
for(int i = 1;i <= n;i++){
read(x);
Insert(root,x,20);
}
while(m--){
read(x);
seg[root].col ^= x;
printf("%d\n",query(root,20));
}
return 0;
}