Balance (Hard version)

题意翻译

# Balance (Hard version) ## 题目描述 这是原题的加强版（就是加上了删除操作啦）。 最初你有一个集合，该集合仅包括一个元素 $0$ 。你需要处理 $q$ 个下述类型的操作： - `+ x` 向集合中添加一个整数 $x$ 。数据保证集合中原来没有这个整数。 - `- x` 从集合中移除整数 $x$ 。数据保证集合包含这个就要删除的整数。 - `? k` 找出当前是 $k$ 的倍数且不被包含在集合中的最小非负整数 $x$ 。 除 $q$ 外，本题涉及的数据都在 $10^{18}$ 内。 ## 输入格式 第一行：一个整数 $q$ ，表示询问的个数。（$1 \leq q \leq 2 · 10^5$） 接下来 $q$ 行，描述题目对你的询问，格式如上文。 数据保证至少会有一个 `? k` 询问。 ## 输出格式 对于每一个 `? k` 询问，输出一个整数 $x$ ，表示当前是 $k$ 的倍数且不被包含在集合中的最小非负整数 $x$ 。 ## 样例说明 **对于第一个样例：** 在第一次和第二次**查询**之后，集合将包含元素 $\{0,1,2\}$ 。是 $1$ 的倍数且不在集合中的最小非负数为 $3$ 。 在第四次**查询**之后，集合将包含元素 $\{0，1，2，4\}$ 。是 $2$ 的倍数且不在集合中的最小非负数是 $6$ 。 **对于第二个样例：** - 最初，集合只包含元素 $\{0\}$ 。 - 添加整数 $100$ 后，集合包含元素 $\{0，100\}$ 。 - 集合的 $x$ 为 $200$ 。 - 添加整数 $200$ 后，集合包含元素 $\{0，100，200\}$ 。 - 集合的 $x$ 为 $300$ 。 - 移除整数 $100$ 后，该集合包含元素 $\{0，200\}$ 。 - 集合的 $x$ 为 $100$ 。 - 添加整数 $50$ 后，集合包含元素 $\{0，50，200\}$ 。 - 集合的 $x$ 为 $100$ 。 - 移除整数 $50$ 后，该集合包含元素 $\{0，200\}$ 。 - 集合的 $x$ 为 $50$ 。

题目描述

This is the hard version of the problem. The only difference is that in this version there are remove queries. Initially you have a set containing one element — $ 0 $ . You need to handle $ q $ queries of the following types: - + $ x $ — add the integer $ x $ to the set. It is guaranteed that this integer is not contained in the set; - - $ x $ — remove the integer $ x $ from the set. It is guaranteed that this integer is contained in the set; - ? $ k $ — find the $ k\text{-mex} $ of the set. In our problem, we define the $ k\text{-mex} $ of a set of integers as the smallest non-negative integer $ x $ that is divisible by $ k $ and which is not contained in the set.

输入输出格式

输入格式

The first line contains an integer $ q $ ( $ 1 \leq q \leq 2 \cdot 10^5 $ ) — the number of queries. The following $ q $ lines describe the queries. An addition query of integer $ x $ is given in the format + $ x $ ( $ 1 \leq x \leq 10^{18} $ ). It is guaranteed that $ x $ is not contained in the set. A remove query of integer $ x $ is given in the format - $ x $ ( $ 1 \leq x \leq 10^{18} $ ). It is guaranteed that $ x $ is contained in the set. A search query of $ k\text{-mex} $ is given in the format ? $ k $ ( $ 1 \leq k \leq 10^{18} $ ). It is guaranteed that there is at least one query of type ?.

输出格式

For each query of type ? output a single integer — the $ k\text{-mex} $ of the set.

输入输出样例

输入样例 #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

说明

In the first example: After the first and second queries, the set will contain elements $ \{0, 1, 2\} $ . The smallest non-negative number that is divisible by $ 1 $ and is not in the set is $ 3 $ . After the fourth query, the set will contain the elements $ \{0, 1, 2, 4\} $ . The smallest non-negative number that is divisible by $ 2 $ and is not in the set is $ 6 $ . In the second example: - Initially, the set contains only the element $ \{0\} $ . - After adding an integer $ 100 $ the set contains elements $ \{0, 100\} $ . - $ 100\text{-mex} $ of the set is $ 200 $ . - After adding an integer $ 200 $ the set contains elements $ \{0, 100, 200\} $ . - $ 100\text{-mex} $ of the set $ 300 $ . - After removing an integer $ 100 $ the set contains elements $ \{0, 200\} $ . - $ 100\text{-mex} $ of the set is $ 100 $ . - After adding an integer $ 50 $ the set contains elements $ \{0, 50, 200\} $ . - $ 50\text{-mex} $ of the set is $ 100 $ . - After removing an integer $ 50 $ the set contains elements $ \{0, 200\} $ . - $ 100\text{-mex} $ of the set is $ 50 $ .

**平衡（困难版本）**

**题目大意：**
这是一个问题的加强版，区别在于这个版本中包含了删除操作。

最初你有一个集合，该集合只包含一个元素 $0$。你需要处理 $q$ 个操作，操作类型如下：

- `+ x`：向集合中添加一个整数 $x$。保证集合中原来没有这个整数。
- `- x`：从集合中移除整数 $x$。保证集合包含这个要删除的整数。
- `? k`：找出当前是 $k$ 的倍数且不被包含在集合中的最小非负整数 $x$。

除了 $q$ 以外的数据，都在 $10^{18}$ 内。

**输入格式：**
第一行：一个整数 $q$，表示询问的个数。（$1 \leq q \leq 2 \cdot 10^5$）

接下来 $q$ 行，描述对你的询问，格式如上文。

保证至少会有一个 `? k` 询问。

**输出格式：**
对于每一个 `? k` 询问，输出一个整数 $x$，表示当前是 $k$ 的倍数且不被包含在集合中的最小非负整数 $x$。

**样例说明：**
- 对于第一个样例：
- 在第一次和第二次查询之后，集合将包含元素 $\{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\}$。$50\text{-mex}$ 为 $50$。

**输入输出样例：**
- 输入样例 #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$。你需要处理 $q$ 个操作，操作类型如下： - `+ x`：向集合中添加一个整数 $x$。保证集合中原来没有这个整数。 - `- x`：从集合中移除整数 $x$。保证集合包含这个要删除的整数。 - `? k`：找出当前是 $k$ 的倍数且不被包含在集合中的最小非负整数 $x$。 除了 $q$ 以外的数据，都在 $10^{18}$ 内。 **输入格式：** 第一行：一个整数 $q$，表示询问的个数。（$1 \leq q \leq 2 \cdot 10^5$） 接下来 $q$ 行，描述对你的询问，格式如上文。 保证至少会有一个 `? k` 询问。 **输出格式：** 对于每一个 `? k` 询问，输出一个整数 $x$，表示当前是 $k$ 的倍数且不被包含在集合中的最小非负整数 $x$。 **样例说明：** - 对于第一个样例： - 在第一次和第二次查询之后，集合将包含元素 $\{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\}$。$50\text{-mex}$ 为 $50$。 **输入输出样例：** - 输入样例 #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 ```