CF842D题解

题目描述

给你一个长度为 \(n(n\leq 3e5)\) 整数数列，对于每一次询问，我们将序列中每一个元素都异或上一个数字 \(x\) 然后查询序列 \(mex\) ，其中 \(mex\) 定义为最小没有出现的自然数。

分析

我们先想想如何快速求一个序列的 \(mex\) ，一种可能很常见的方法是建立一颗权值线段树，然后对于每一个值域，如果左儿子中数的数量等于区间长度，那么说明答案在右子树中，否则就在左子树中。

但是这种做法不能很好的处理异或，那我们怎么办呢？处理异或的问题，我们通常采用的是01trie，那么我们如何使用01trie呢？

经过我们画图观察可以发现如果出现了一段连续的数字，01trie上对应的子树一定是满的

然后我们和上面不带修改的方法类似，再插入的过程中对于每一个01trie上的节点，我们记录一下它的子树大小，如果它是满的，说明它的 \(mex\) 在另外一边。

在考虑如何处理异或的条件，在01trie上就是相当于交换两颗子树，我们只需要加上一点小小的判断就可以了。

#include 
using namespace std;
const int N=3e5+10;
int n,m,tr[N*30][2],tot,sz[N*30];
inline void Ins(int cur,int weis,int x){
	if(weis<0) {sz[cur]=1;return;}
	int ch=x>>weis&1;
	if(tr[cur][ch]==0) tr[cur][ch]=++tot;
	Ins(tr[cur][ch],weis-1,x);
	sz[cur]=sz[tr[cur][0]]+sz[tr[cur][1]];
}
inline int Qry(int cur,int axor){
	int res=0;
	for(int weis=25;weis>=0;weis--){
		int ch=axor>>weis&1;
		if(sz[tr[cur][ch]]==(1<<(weis))) {
			res|=(1<<(weis));
			cur=tr[cur][ch^1];
		} else {
			cur=tr[cur][ch];
		}
		if(cur==0) return res;
	}
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;tot=1;
	for(int i=1;i<=n;i++){
		int x;cin>>x;Ins(1,25,x); 
	}
	int axor=0;
	for(int i=1;i<=m;i++){
		int x;cin>>x;axor^=x;
		cout<