A7395. 字典树模板（带删）
编程题
普及/提高-
知识点
题目描述
给定一个多重集 $A$，初始时 $A$ 中只包含一个整数 $0$。
现在需要依次执行 $q$ 个操作，操作共有三种：
-
-
-
对于一次
$$ \max_{y\in A}(x\oplus y) $$
其中 $\oplus$ 表示按位异或运算。
多重集允许存在相同的元素。
需要注意的是，执行
如果 $A$ 中存在 $x$，则删除其中一个 $x$。
如果 $A$ 中不存在 $x$，则本次删除操作不产生任何影响。
整数 $0$ 始终存在于多重集 $A$ 中。
现在需要依次执行 $q$ 个操作，操作共有三种：
-
+ x：向多重集 $A$ 中加入一个整数 $x$；-
- x：从多重集 $A$ 中删除一个整数 $x$；-
? x：询问 $x$ 与多重集 $A$ 中某个整数异或后的最大值。对于一次
? x 操作，你需要求出：$$ \max_{y\in A}(x\oplus y) $$
其中 $\oplus$ 表示按位异或运算。
多重集允许存在相同的元素。
需要注意的是，执行
- x 操作时，不保证当前多重集 $A$ 中一定存在 $x$。如果 $A$ 中存在 $x$，则删除其中一个 $x$。
如果 $A$ 中不存在 $x$，则本次删除操作不产生任何影响。
整数 $0$ 始终存在于多重集 $A$ 中。
输入格式
第一行输入一个整数 $q$，表示操作次数。
接下来 $q$ 行，每行输入一个字符 $op$ 和一个整数 $x$。
其中 $op$ 为
接下来 $q$ 行，每行输入一个字符 $op$ 和一个整数 $x$。
其中 $op$ 为
+、- 或 ?。输出格式
对于每个
? x 操作，输出一行一个整数，表示 $x$ 与多重集 $A$ 中某个整数异或后的最大值。输入输出样例
输入 #1
10 + 8 + 9 + 11 + 6 + 1 ? 3 - 8 ? 3 ? 8 ? 11
输出 #1
11 10 14 13
说明/提示
## 样例解释 #1
前五次操作后，多重集 $A$ 中包含：
$$ 0,8,9,11,6,1 $$
对于
$$ 3\oplus 8=11 $$
删除 $8$ 后，多重集 $A$ 中包含：
$$ 0,9,11,6,1 $$
之后三个询问的最大异或值分别为 $10,14,13$。
## 数据范围
对于所有测试数据，满足：
- $1\le q\le 200000$
- $1\le x\le 10^9$
- $op\in\{+, -, ?\}$
- 保证至少存在一次
- 初始时多重集 $A$ 中包含整数 $0$
- 整数 $0$ 始终存在于多重集 $A$ 中
前五次操作后，多重集 $A$ 中包含：
$$ 0,8,9,11,6,1 $$
对于
? 3，最大值为：$$ 3\oplus 8=11 $$
删除 $8$ 后，多重集 $A$ 中包含：
$$ 0,9,11,6,1 $$
之后三个询问的最大异或值分别为 $10,14,13$。
## 数据范围
对于所有测试数据，满足：
- $1\le q\le 200000$
- $1\le x\le 10^9$
- $op\in\{+, -, ?\}$
- 保证至少存在一次
? 操作- 初始时多重集 $A$ 中包含整数 $0$
- 整数 $0$ 始终存在于多重集 $A$ 中