← 返回题目列表

AtCoder · abc253_c

E. 最大 - 最小查询

中文机器翻译题面 查看原题

分数: 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,不应打印任何内容。