分数: 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位整数。