A15454. Balance (Hard version)
编程题
普及/提高-
知识点
题目描述
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.
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 ?.
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$ .
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$ .