AT_abc212_d [ABC212D] Querying Multiset

题目描述

高桥君有许多没有写字的球和一个袋子。最开始，袋子是空的，高桥君将进行 $Q$ 次操作。每次操作属于以下三种之一：

• 操作 $1$：在一个还没有写字的球上写上整数 $X_i$，然后把它放进袋子。
• 操作 $2$：对袋子里所有的球，将其上写的数都加上 $X_i$。
• 操作 $3$：从袋子里取出写有最小数字的球（如果有多个，任选一个），记录下这个数字，然后把这个球丢弃。

给定每次操作的类型 $P_i$ 以及操作 $1$、$2$ 时的 $X_i$，请按顺序输出每次操作 $3$ 时记录下的数字。

输入格式

输入通过标准输入给出。

第一行为 $Q$。

接下来的 $Q$ 行，每行表示一次操作 $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$ 的操作，按顺序输出记录下的数字，每个数字占一行。

输入输出样例 #1

输入 #1

5
1 3
1 5
3
2 2
3

输出 #1

3
7

输入输出样例 #2

输入 #2

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

输出 #2

5000000000

说明/提示

限制条件

• $1\leq Q\leq 2\times 10^5$
• $1\leq P_i\leq 3$
• $1\leq X_i\leq 10^9$
• 所有输入均为整数。
• 至少存在一次 $P_i=3$ 的操作。
• 每次 $P_i=3$ 操作前，袋子里至少有一个球。

样例解释 1

高桥君按如下方式进行操作：

• 把写有 $3$ 的球放入袋子。
• 把写有 $5$ 的球放入袋子。
• 现在袋子里有写有 $3$ 和 $5$ 的球，取出较小的 $3$ 并记录，然后丢弃。
• 现在袋子里只剩写有 $5$ 的球，将其数字加上 $2$ 变为 $7$。
• 现在袋子里只剩写有 $7$ 的球，取出并记录 $7$，然后丢弃。

因此，按顺序输出 $3$ 和 $7$。

样例解释 2

请注意，答案可能超出 $32$ 位整数的范围。

由 ChatGPT 4.1 翻译