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 $ .

题意翻译

# 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$ 。