Querying Multiset

题目描述

Takahashi 有许多空白的球和一个袋子。 最初，袋子是空的。Takahashi 将执行 $Q$ 次操作，每次操作是以下三种类型之一。

类型 $1$：在一个空白球上写下整数 $X_i$ 并将其放入袋子。 类型 $2$：对于袋子中的每个球，将其上写的整数替换为该整数加上 $X_i$。 类型 $3$：取出袋子中写有最小整数的球（如果有多个这样的球，取出其中任意一个）。记录写在该球上的整数并将其丢弃。

对于每个 $1\leq i\leq Q$，给出第 $i$ 次操作的类型 $P_i$，以及如果该操作是类型 $1$ 或 $2$ 时的值 $X_i$。按顺序输出在类型 $3$ 的操作中记录下的整数。

输入格式

输入从标准输入按以下格式给出： $Q$ $query_1$ $query_2$ : $query_Q$

第 $2$ 行到第 $(Q+1)$$行的每个$query_i$ 的格式为： $1$ $X_i$

$2$ $X_i$

$3$

每行的第一个数字为 $1\leq P_i\leq 3$，表示操作的类型。 如果 $P_i=1$ 或 $P_i=2$，则之后有一个空格，随后是 $X_i$。

输出格式

对于这 $Q$ 次操作中每个 $P_i=3$ 操作，单独一行打印记录下的整数。

5
1 3
1 5
3
2 2
3

3
7

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

5000000000

提示

$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$。 如果 $P_i=3$，则在第 $i$ 次操作之前袋子中至少有一个球。Takahashi 将执行以下操作。

在一个球上写下 $3$ 并把它放入袋子。 在一个球上写下 $5$ 并把它放入袋子。 袋子现在包含一个写有 $3$ 的球和另一个写有 $5$ 的球。取出较小的那个，即 $3$。记录 $3$ 并将其丢弃。 袋子现在只剩下一个写有 $5$ 的球。将该整数替换为 $5+2=7$。 袋子现在只剩下一个写有 $7$ 的球。取出该球，记录 $7$，并将其丢弃。

因此，我们应该按记录的顺序打印 $3$ 和 $7$。
注意输出可能超出 32 位整数的范围。

标签: AtCoder|abc212D

来源

AtCoder|abc212D