102532: [AtCoder]ABC253 C - Max - Min Query

Problem Statement

We have a multiset of integers $S$, which is initially empty.

Given $Q$ queries, process them in order. Each query is of one of the following types.

• 1 x: Insert an $x$ into $S$.

• 2 x c: Remove an $x$ from $S$ $m$ times, where $m = \mathrm{min}(c,($ the number of $x$'s contained in $S))$.

• 3 : Print $($ maximum value of $S)-($ minimum value of $S)$. It is guaranteed that $S$ is not empty when this query is given.

Constraints

• $1 \leq Q \leq 2\times 10^5$
• $0 \leq x \leq 10^9$
• $1 \leq c \leq Q$
• When a query of type 3 is given, $S$ is not empty.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$Q$
$\mathrm{query}_1$
$\vdots$
$\mathrm{query}_Q$

$\mathrm{query}_i$, which denotes the $i$-th query, is in one of the following formats:

$1$ $x$

$2$ $x$ $c$

$3$ 

Output

Print the answers for the queries of type 3 in the given order, separated by newlines.

Sample Input 1

8
1 3
1 2
3
1 2
1 7
3
2 2 3
3

Sample Output 1

1
5
4

The multiset $S$ transitions as follows.

• $1$-st query: insert $3$ into $S$. $S$ is now $\lbrace 3 \rbrace$.
• $2$-nd query: insert $2$ into $S$. $S$ is now $\lbrace 2, 3 \rbrace$.
• $3$-rd query: the maximum value of $S = \lbrace 2, 3\rbrace$ is $3$ and its minimum value is $2$, so print $3-2=1$.
• $4$-th query: insert $2$ into $S$. $S$ is now $\lbrace 2,2,3 \rbrace$.
• $5$-th query: insert $7$ into $S$. $S$ is now $\lbrace 2, 2,3, 7\rbrace$.
• $6$-th query: the maximum value of $S = \lbrace 2,2,3, 7\rbrace$ is $7$ and its minimum value is $2$, so print $7-2=5$.
• $7$-th query: since there are two $2$'s in $S$ and $\mathrm{min(2,3)} = 2$, remove $2$ from $S$ twice. $S$ is now $\lbrace 3, 7\rbrace$.
• $8$-th query: the maximum value of $S = \lbrace 3, 7\rbrace$ is $7$ and its minimum value is $3$, so print $7-3=4$.

Sample Input 2

4
1 10000
1 1000
2 100 3
1 10

Sample Output 2

If the given queries do not contain that of type $3$, nothing should be printed.

问题描述

我们有一个整数集合$S$，它最初是空的。

给定$Q$个查询，按顺序处理它们。

每个查询有以下类型之一。

• 1 x：将一个$x$插入到$S$中。

• 2 x c：从$S$中删除$x$，次数为$m=\min(c, S$中包含的$x$的数量)$。

• 3：打印$S$的最大值减去$S$的最小值。当给出此查询时，保证$S$不为空。

约束条件

• $1\leq Q\leq 2\times 10^5$
• $0\leq x\leq 10^9$
• $1\leq c\leq Q$
• 当给出类型为3的查询时，$S$不为空。
• 输入中的所有值都是整数。

输入

输入从标准输入中给出，如下所示：

$Q$
$\mathrm{query}_1$
$\vdots$
$\mathrm{query}_Q$

表示第$i$个查询的$\mathrm{query}_i$有以下格式之一：

$1$ $x$

$2$ $x$ $c$

$3$ 

输出

按照给出的顺序，以换行符分隔的方式打印类型为3的查询的答案。

样例输入 1

8
1 3
1 2
3
1 2
1 7
3
2 2 3
3

样例输出 1

1
5
4

集合$S$按以下方式进行转换。

• $1$-st查询：将$3$插入到$S$中。$S$现在是$\lbrace 3 \rbrace$。
• $2$-nd查询：将$2$插入到$S$中。$S$现在是$\lbrace 2, 3 \rbrace$。
• $3$-rd查询：$S=\lbrace 2, 3 \rbrace$的最大值是$3$，最小值是$2$，所以打印$3-2=1$。
• $4$-th查询：将$2$插入到$S$中。$S$现在是$\lbrace 2,2,3 \rbrace$。
• $5$-th查询：将$7$插入到$S$中。$S$现在是$\lbrace 2, 2,3, 7\rbrace$。
• $6$-th查询：$S=\lbrace 2,2,3, 7\rbrace$的最大值是$7$，最小值是$2$，所以打印$7-2=5$。
• $7$-th查询：由于$S$中有两个$2$，且$\min(2,3)=2$，从$S$中删除$2$两次。$S$现在是$\lbrace 3, 7\rbrace$。
• $8$-th查询：$S=\lbrace 3, 7\rbrace$的最大值是$7$，最小值是$3$，所以打印$7-3=4$。

样例输入 2

4
1 10000
1 1000
2 100 3
1 10

样例输出 2

如果给定的查询不包含类型为$3$的查询，则不打印任何内容。