CF706D Vasiliy's Multiset 题解

题目链接：CF706D Vasiliy's Multiset

题意：

有 \(q\) 次操作和一个集合 \(A\) ，开始时集合中只有一个数 \(0\) ，下面有三种类型的操作：

1. + x 把 \(x\) 插入集合 \(A\) 。
2. - x 把 \(x\) 从集合 \(A\) 中删去，保证 \(x\) 已存在于集合 \(A\) 中。
3. ? x 给一个数 \(x\) 在集合 \(A\) 中找一个 \(y\) 使得 \(x\operatorname{xor} y\) 最大，并求出这个值。

数据范围：

\(1\leq q\leq 2\times 10^5,1\leq x_i\leq10^9\)

猫猫图镇楼（我一定要养一只这样的猫猫！）

考虑建一个 01trie 。插入操作就是一条线上都加个 \(1\) ，删除就是一条线上加个 \(-1\) 。

查询稍复杂一丢丢，设下一位为 \(c = 0,1\) ，我们看 \(\neg c\) 是否有数经过，有就往那走，这样一定能找到最大的。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：（来自参考文献[1]）

#include<cstdio>
#include<algorithm>
#define N 114514
#define M 63
#define int long long
using namespace std;
int n;
struct trie{
	int ch[N*M][2],cnt=1,num[N*M],val[N*M];
	void insert(int x){
		int u=1;
		for(int i=M;i>=0;i--){
			int v=x>>i&1ll;
			if(!ch[u][v])ch[u][v]=++cnt;
			u=ch[u][v];	
			num[u]++;
		}
		val[u]=x;
	}
	void del(int x){
		int u=1;
		for(int i=M;i>=0;i--){
			int v=x>>i&1ll;
			u=ch[u][v];	
			num[u]--;
		}
	}
	int querymax(int x){
		int u=1;
		for(int i=M;i>=0;i--){
			int v=x>>i&1ll;
			if(ch[u][v^1]&&num[ch[u][v^1]])u=ch[u][v^1];
			else u=ch[u][v];
		}
		return x^val[u];
	}
}st;
signed main(){
	scanf("%lld",&n);
	st.insert(0);
	while(n--){
		char s[12];
		int a;
		scanf("%s%lld",s,&a);
		if(s[0]=='+')st.insert(a);
		else if(s[0]=='-')st.del(a);
		else printf("%lld\n",st.querymax(a));
	}
	return 0;
}

话说我想到个搞笑的，我之前在学校里开了我的博客

然后被校领导当成在看动漫网站了，我踏马笑死了（

---

参考文献：

[1] https://whindsers.blog.luogu.org/solution-cf706d