题目大意
有 \(q\) 次操作和一个集合 \(A\),开始时集合中只有一个数 \(0\),下面有三种类型的操作:
-
+ x
,把 \(x\) 插入集合 \(A\)。 -
- x
,把 \(x\) 从集合 \(A\) 中删去,保证 \(x\) 已存在于集合 \(A\) 中。 -
? x
,给一个数 \(x\) 在集合A
中找一个 \(y\) 使得 \(x \operatorname{xor} y\) 最大,并求出这个值。
对于 \(100\%\) 的数据,\(1\leq q\leq 200000,1\leq x_i\leq10^9\)。
解题思路
看到异或和一些添加删除操作,首先可以想到是 01 trie
。
对于询问,要使得异或值最大,可以二进制位从大到小贪心选不同的。
另外,由于 \(x\) 是在线给出的,且要输出一个值,也就是说不能简单地判断。
考虑对每一个数在 trie
上弄标记,并在结尾处记录这个数的位置。
每次删除只需要删标记,跳的时候看一下有没有标记即可。
注意数组大小。
CODE
#include <bits/stdc++.h>
using namespace std;
const int _ = 200007;
#define int long long
inline int read()
{
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9')
{
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9')
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
char opt;
int T, x, num[27 * _], val[27 * _];
int cnt = 1, tr[27 * _][2];
void Insert(int x)
{
int p = 1;
for(int i = 32; i >= 0; --i)
{
int v = x >> i & 1;
if(!tr[p][v])
tr[p][v] = ++cnt;
p = tr[p][v];
num[p]++;
}
val[p] = x;
}
void Delete(int x)
{
int p = 1;
for(int i = 32; i >= 0; --i)
{
int v = x >> i & 1;
p = tr[p][v];
num[p]--;
}
}
int Query(int x)
{
int p = 1;
for(int i = 32; i >= 0; --i)
{
int v = x >> i & 1;
if(tr[p][v ^ 1] && num[tr[p][v ^ 1]])
p = tr[p][v ^ 1];
else
p = tr[p][v];
}
return x ^ val[p];
}
signed main()
{
T = read();
Insert(0);
while(T--)
{
cin >> opt;
x = read();
if(opt == '+')
Insert(x);
if(opt == '-')
Delete(x);
if(opt == '?')
printf("%lld\n", Query(x));
}
return 0;
}