4191: Querying Multiset

# Querying Multiset ### 内存 1024MB ### 时间 2S ## 题目描述 小高有许多球和一个袋子。最初，袋子是空的。小高将进行 $Q$ 次操作，每次操作是以下三种类型之一。 1. 在一个空白球上写上整数 $X_i$ 并将其放入袋中。 2. 对于袋中的每个球，将其上写的整数替换为该整数加上 $X_i$。 3. 从袋中取出写有最小整数的球（如果有多个这样的球，取出其中一个）。记录这个球上的整数并将其丢弃。 对于每个类型为 3 的操作，请按顺序输出记录的整数。 ## 输入格式 输入格式如下： $Q$ $query_1$ $query_2$ $\vdots$ $query_Q$ 每个 $query_i$ 的格式如下三者之一： - $1$ $X_i$ - $2$ $X_i$ - $3$ 第一个数字是 $1 \leq P_i \leq 3$，表示操作类型。如果 $P_i=1$ 或 $P_i=2$，后面会跟一个空格和 $X_i$。 ## 输出格式 对于每个 $P_i=3$ 的操作，在单独的一行中输出记录的整数。 ## 输入输出样例 ### 输入样例1 ``` 5 1 3 1 5 3 2 2 3 ``` ### 输出样例1 ``` 3 7 ``` ### 输入样例2 ``` 6 1 1000000000 2 1000000000 2 1000000000 2 1000000000 2 1000000000 3 ``` ### 输出样例2 ``` 5000000000 ``` ## 数据范围与提示 【样例说明1】 小高将进行以下操作： 1. 在一个球上写3并放入袋中。 2. 在一个球上写5并放入袋中。 3. 袋中现在有一个写着3的球和一个写着5的球。取出较小的那个，即3。记录3并丢弃。 4. 袋中现在只有一个写着5的球。将这个整数替换为5+2=7。 5. 袋中现在只有一个写着7的球。取出这个球，记录7，并丢弃。 因此，我们应该按顺序输出3和7。 【样例说明2】 注意输出可能不适合32位整数。 【数据范围】 - $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$ 次操作之前袋中至少有一个球。 ## 题目来源 ABC212D