103662: [Atcoder]ABC366 C - Balls and Bag Query

Problem Statement

You have an empty bag. You are given $Q$ queries, which must be processed in order.

There are three types of queries.

• 1 x : Put one ball with the integer $x$ written on it into the bag.
• 2 x : Remove one ball with the integer $x$ written on it from the bag and discard it. It is guaranteed that the bag has a ball with the integer $x$ written on it when this query is given.
• 3 : Print the number of different integers written on the balls in the bag.

Constraints

• $1 \leq Q \leq 2 \times 10^{5}$
• $1 \leq x \leq 10^{6}$
• When a query of the second type is given, the bag has a ball with the integer $x$ written on it.
• There is at least one query of the third type.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

The $i$-th query $\text{query}_i$ is given in one of the following three formats:

$1$ $x$

$2$ $x$

$3$

Output

If there are $K$ queries of the third type, print $K$ lines. The $i$-th line $(1 \leq i \leq K)$ should contain the answer to the $i$-th query of the third type.

Sample Input 1

8
1 3
1 1
1 4
3
2 1
3
1 5
3

Sample Output 1

3
2
3

Initially, the bag is empty.

For the first query 1 3, a ball with the integer $3$ written on it enters the bag.

For the second query 1 1, a ball with the integer $1$ written on it enters the bag.

For the third query 1 4, a ball with the integer $4$ written on it enters the bag.

For the fourth query 3, the bag has balls with the integers $1, 3, 4$, so print $3$.

For the fifth query 2 1, a ball with the integer $1$ written on it is removed from the bag.

For the sixth query 3, the bag has balls with the integers $3, 4$, so print $2$.

For the seventh query 1 5, a ball with the integer $5$ written on it enters the bag.

For the eighth query 3, the bag has balls with the integers $3, 4, 5$, so print $3$.

Sample Input 2

8
1 2
1 2
3
2 2
1 4
1 4
2 2
3

Sample Output 2

1
1

问题陈述

你有一个空袋子。 你得到了$Q$个查询，必须按顺序处理。

查询有三种类型。

• 1 x ：将一个带有整数$x$的球放入袋子中。
• 2 x ：从袋子中移除一个带有整数$x$的球并将其丢弃。保证在给出此查询时，袋子中有一个带有整数$x$的球。
• 3 ：打印袋子中球上不同整数的数量。

约束条件

• $1 \leq Q \leq 2 \times 10^{5}$
• $1 \leq x \leq 10^{6}$
• 当给出第二种类型的查询时，袋子中有一个带有整数$x$的球。
• 至少有一个第三种类型的查询。
• 所有输入值都是整数。

输入

输入从标准输入以以下格式给出：

$Q$
$\text{query}_1$
$\text{query}_2$
$\vdots$
$\text{query}_Q$

第$i$个查询$\text{query}_i$以以下三种格式之一给出：

$1$ $x$

$2$ $x$

$3$

输出

如果有$K$个第三种类型的查询，打印$K$行。 第$i$行$(1 \leq i \leq K)$应包含对第$i$个第三种类型查询的答案。

示例输入1

8
1 3
1 1
1 4
3
2 1
3
1 5
3

示例输出1

3
2
3

最初，袋子是空的。

对于第一个查询1 3，一个带有整数$3$的球进入袋子。

对于第二个查询1 1，一个带有整数$1$的球进入袋子。

对于第三个查询1 4，一个带有整数$4$的球进入袋子。

对于第四个查询3，袋子中有整数$1, 3, 4$的球，所以打印$3$。

对于第五个查询2 1，一个带有整数$1$的球从袋子中移除。

对于第六个查询3，袋子中有整数$3, 4$的球，所以打印$2$。

对于第七个查询1 5，一个带有整数$5$的球进入袋子。

对于第八个查询3，袋子中有整数$3, 4, 5$的球，所以打印$3$。

示例输入2

8
1 2
1 2
3
2 2
1 4
1 4
2 2
3

示例输出2

1
1