当前没有测试数据。

C - 最大-最小查询

分数：300分

问题描述

我们有一个初始为空的整数集合$S$。

给定$Q$个查询，按顺序处理它们。 每个查询可以是以下类型之一。

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

• 2 x c：从$S$中$m$次删除$x$，其中$m = \mathrm{min}(c,($包含在$S$中的$x$的个数))$。

• 3 ：输出$S$的最大值减去最小值。保证在给出此查询时，$S$非空。

约束条件

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

---

输入

输入以以下格式从Standard Input中给出：

$Q$

$\mathrm{query}_1$

$\vdots$

$\mathrm{query}_Q$

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

``` $1$ $x$ ``` ``` $2$ $x$ $c$ ``` ``` $3$ ```

输出

按给定的顺序，将类型为3的查询的答案以新行分隔打印。

---

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

1
5
4

整数集合$S$的变化如下。

• 第1个查询：将$3$插入$S$。此时$S$为$\lbrace 3 \rbrace$。
• 第2个查询：将$2$插入$S$。此时$S$为$\lbrace 2, 3 \rbrace$。
• 第3个查询：$S = \lbrace 2, 3\rbrace$的最大值为$3$，最小值为$2$，所以打印$3-2=1$。
• 第4个查询：将$2$插入$S$。此时$S$为$\lbrace 2,2,3 \rbrace$。
• 第5个查询：将$7$插入$S$。此时$S$为$\lbrace 2, 2,3, 7\rbrace$。
• 第6个查询：$S = \lbrace 2,2,3, 7\rbrace$的最大值为$7$，最小值为$2$，所以打印$7-2=5$。
• 第7个查询：$S$中有两个$2$，而$\mathrm{min(2,3)} = 2$，所以将$2$从$S$中移除两次。此时$S$为$\lbrace 3, 7\rbrace$。
• 第8个查询：$S = \lbrace 3, 7\rbrace$的最大值为$7$，最小值为$3$，所以打印$7-3=4$。

---

4
1 10000
1 1000
2 100 3
1 10

如果给定的查询中没有类型为$3$的查询，则不需要打印任何内容。