← 返回题目列表

AtCoder · abc212_d

G. 查询多重集

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

分数: 400 点

问题陈述

高桥有很多球,上面什么也没写,还有一个袋子。 最初,袋子是空的。高桥会做 Q 操作,每个操作属于以下三种类型之一。

  • 类型 1: 写入一个整数 X_i 在一个空白球上并将其放入袋子中。
  • 类型 2:对于袋子中的每个球,将其上写的整数替换为该整数加上 X_i.
  • 类型 3:捡起袋子中整数最小的球(如果有多个这样的球,则捡起其中一个)。记录这个球上写的整数并将其扔掉。

对于每个 1\leq i\leq Q,您将获得类型 P_i 的 i第一次操作和值 X_i 如果操作是类型 1 or 2。打印Type操作中记录的整数 3 按顺序。

约束

  • 1 \leq Q \leq 2\times 10^5
  • 1 \leq P_i \leq 3
  • 1 \leq X_i \leq 10^9
  • 输入中的所有值都是整数。
  • 有一个或多个 i 这样 P_i=3.
  • If P_i=3,袋子里至少有一个球,就在 i第次操作。

输入

输入由标准输入按以下格式给出:

Q
query_1
query_2
:
query_Q

每个 query_i 在 2-nd 通过 (Q+1)第行的格式如下:

1 X_i
2 X_i
3

每行的第一个数字是 1\leq P_i\leq 3,表示操作的类型。 如果 P_i=1 or P_i=2,后面跟一个空格,然后是 X_i.

输出

对于每个操作 P_i=3 其中 Q 操作,在其自己的行中打印记录的整数。


示例输入 1

5
1 3
1 5
3
2 2
3

示例输出 1

3
7

Takahashi 将执行以下操作。

  • 写 将 3 放在球上并将其放入袋子中。
  • 写 将 5 放在球上并将其放入袋子中。
  • 袋子现在包含一个带有 3 和另一个 5。拿起其中较小的球,或者 3。记录 3 然后把它扔掉。
  • 袋子现在只包含一个球 5。将此整数替换为 5+2=7.
  • 袋子现在只包含一个球 7。拿起这个球,记录一下 7,然后把它扔掉。

因此,我们应该打印 3 和 7,按记录顺序排列。


示例输入 2

6
1 1000000000
2 1000000000
2 1000000000
2 1000000000
2 1000000000
3

示例输出 2

5000000000

请注意,输出可能不适合 32位整数。