← 返回题目列表

Codeforces · 1732/D2

D2. 平衡(困难版)

中文机器翻译题面 查看原题

这是问题的困难版本。唯一的区别是,在此版本中存在删除查询。

最初,您有一个包含一个元素的集合 - $$$0$$$。您需要处理以下类型的 $$$q$$$ 查询:

- + $$$x$$$ — 将整数 $$$x$$$ 添加到集合中。保证该整数不包含在集合中;
- - $$$x$$$ — 从集合中删除整数 $$$x$$$。保证该整数包含在集合中;
- ? $$$k$$$ — 找到集合中的 $$$k\text{-mex}$$$。

在我们的问题中,我们将一组整数的 $$$k\text{-mex}$$$ 定义为可被 $$$k$$$ 整除且不包含在该集合中的最小非负整数 $$$x$$$。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — 查询数。

以下 $$$q$$$ 行描述了查询。

整数 $$$x$$$ 的加法查询以 + $$$x$$$ ($$$1 \leq x \leq 10^{18}$$$) 的格式给出。保证 $$$x$$$ 不包含在集合中。

整数 $$$x$$$ 的删除查询以以下格式给出 - $$$x$$$ ($$$1 \leq x \leq 10^{18}$$$)。保证 $$$x$$$ 包含在集合中。

$$$k\text{-mex}$$$ 的搜索查询以以下格式给出? $$$k$$$ ($$$1 \leq k \leq 10^{18}$$$)。

保证至少有一个类型为 ? 的查询。

输出

对于类型为 ? 的每个查询输出单个整数 - 集合的 $$$k\text{-mex}$$$。

示例

输入 #1

18
+ 1
+ 2
? 1
+ 4
? 2
+ 6
? 3
+ 7
+ 8
? 1
? 2
+ 5
? 1
+ 1000000000000000000
? 1000000000000000000
- 4
? 1
? 2

输出 #1

3
6
3
3
10
3
2000000000000000000
3
4

输入 #2

10
+ 100
? 100
+ 200
? 100
- 100
? 100
+ 50
? 50
- 50
? 50

输出 #2

200
300
100
100
50

注意

在第一个示例中:

在第一次和第二次查询之后,集合将包含元素 $$$\{0, 1, 2\}$$$。能被$$$1$$$整除且不在集合中的最小非负数是$$$3$$$。

第四次查询后,集合将包含元素 $$$\{0, 1, 2, 4\}$$$。能被$$$2$$$整除且不在集合中的最小非负数是$$$6$$$。

在第二个示例中:

- 最初,集合仅包含元素 $$$\{0\}$$$。
- 添加整数 $$$100$$$ 后,集合包含元素 $$$\{0, 100\}$$$。
- 该组的 $$$100\text{-mex}$$$ 为 $$$200$$$。
- 添加整数 $$$200$$$ 后,集合包含元素 $$$\{0, 100, 200\}$$$。
- $$$100\text{-mex}$$$ 组 $$$300$$$。
- 删除整数 $$$100$$$ 后,集合包含元素 $$$\{0, 200\}$$$。
- 该组的 $$$100\text{-mex}$$$ 为 $$$100$$$。
- 添加整数 $$$50$$$ 后,集合包含元素 $$$\{0, 50, 200\}$$$。
- 该组的 $$$50\text{-mex}$$$ 为 $$$100$$$。
- 删除整数 $$$50$$$ 后,集合包含元素 $$$\{0, 200\}$$$。
- 该组的 $$$100\text{-mex}$$$ 为 $$$50$$$。