Codeforces 842D Vitya and Strange Lesson

01字典树，数据结构

题意

给出长度为 n 的非负整数序列，求该序列异或 x 以后的 mex 值。

思路

求mex可以用trie来搞。把整个序列的trie建出来后，假如要全局异或一个x，若x的从高到低第i位为1，则trie的第i层的所有节点都要翻转左右儿子。 知道了这点后，我们就可以通过打标记实现翻转来快速异或一个值，而不需要实际进行异或。

因为所有数都在300000内，那么01字典树开20层就够。标记什么的类似线段树，边查询边pushdown，如果这一层对应的位是1，那么交换左右儿子。每一个节点存一个是否儿子满了的标志，查询时如果左儿子没满，mex值肯定在左子树；要是满了，就进入右子树。

代码

注意运算符优先级

#include<cstdio> #include<cstring> #include<algorithm> #define M(a,b) memset(a,b,sizeof(a)) #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; const int MAXN=300007; const int bit=20; typedef long long LL; struct Trie { int s; int ch[2]; int rev; Trie() { s=ch[0]=ch[1]=rev=0; } }trie[MAXN*bit]; int sz=0; void build() { M(trie, 0); } void pushdown(int rt, int lev) { if(lev<=0||trie[rt].rev==0) return; int tmp=trie[rt].rev;trie[rt].rev=0; int ls=trie[rt].ch[0], rs=trie[rt].ch[1]; trie[ls].rev^=tmp, trie[rs].rev^=tmp; if(tmp&(1<<(lev-1))) swap(trie[ls].ch[0], trie[ls].ch[1]), swap(trie[rs].ch[0], trie[rs].ch[1]); } void insert(int rt, int lev, int num) { if(lev==-1) { trie[rt].s=1;return; } int k=(num&(1<<lev))>>lev; if(!trie[rt].ch[k]) trie[rt].ch[k]=++sz; insert(trie[rt].ch[k], lev-1, num); trie[rt].s=trie[trie[rt].ch[0]].s&trie[trie[rt].ch[1]].s; } int query(int rt, int lev) { if(lev==-1) return 0; pushdown(rt, lev); if(!trie[trie[rt].ch[0]].s) return query(trie[rt].ch[0], lev-1); else return query(trie[rt].ch[1], lev-1)+(1<<lev); } int main() { int n, m; while(scanf("%d%d", &n, &m)==2) { sz=1;build(); for(int i=1;i<=n;i++) { int tmp;scanf("%d", &tmp); insert(1, bit, tmp); } for(int i=1;i<=m;i++) { int tmp;scanf("%d", &tmp); trie[1].rev^=tmp; if(tmp&(1<<bit)) swap(trie[1].ch[0], trie[1].ch[1]); printf("%d\n", query(1, bit)); } } return 0; }