分数: 300 点
问题陈述
我们有一组整数 S,最初是空的。
鉴于 Q 查询,按顺序处理。 每个查询都属于以下类型之一。
-
1 x:插入 x 进入 S. -
2 x c:删除 x 来自 S m 次,其中 m = \mathrm{min}(c,( 数量 x包含在 S)). -
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
\mathrm{query}_i,表示 i-th 查询采用以下格式之一:
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 is 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 is 7 其最小值为 2,所以打印 7-2=5.
- 7-第一个查询:因为有两个 2位于 S 和 \mathrm{min(2,3)} = 2,删除 2 来自 S 两次。 S 现在 \lbrace 3, 7\rbrace.
- 8-第查询:最大值 S = \lbrace 3, 7\rbrace is 7 其最小值为 3,所以打印 7-3=4.
示例输入 2
4 1 10000 1 1000 2 100 3 1 10
示例输出 2
如果给定的查询不包含类型的查询 3,不应打印任何内容。