4199: Max - Min Query

# Max - Min Query ### 内存 1024MB ### 时间 2S ## 题目描述 我们有一个整数的多重集$S$，最初为空。给定$Q$个查询，按顺序处理它们。每个查询是以下三种类型之一： 1. `1 x`：将$x$插入$S$中。 2. `2 x c`：从$S$中移除$m$个$x$，其中$m = min$($c$, $S$中$x$的数量)。 3. `3`：输出($S$的最大值) - ($S$的最小值)。保证执行此查询时$S$非空。 ## 输入格式 输入从标准输入中给出，格式如下： $Q$ $query_1$ $query_2$ $\vdots$ $query_Q$ $query_i$表示第$i$个查询，格式为以下之一： `1 x` `2 x c` `3` ## 输出格式 对于每个类型$3$的查询，按顺序输出结果，每个结果占一行。 ## 输入输出样例 ### 输入样例1 ``` 8 1 3 1 2 3 1 2 1 7 3 2 2 3 3 ``` ### 输出样例1 ``` 1 5 4 ``` ### 输入样例2 ``` 4 1 10000 1 1000 2 100 3 1 10 ``` ### 输出样例2 ``` ``` ## 数据范围与提示 【样例1说明】 多重集$S$的变化过程如下： 1. 插入3，S = {3} 2. 插入2，S = {2, 3} 3. 输出3 - 2 = 1 4. 插入2，S = {2, 2, 3} 5. 插入7，S = {2, 2, 3, 7} 6. 输出7 - 2 = 5 7. 移除两个2，S = {3, 7} 8. 输出7 - 3 = 4 【样例2说明】 如果给定的查询不包含类型$3$，则不应输出任何内容。 【数据范围】 $1 ≤ Q ≤ 2×10^5$ $0 ≤ x ≤ 10^9$ $1 ≤ c ≤ Q$ 当给出类型$3$的查询时，$S$非空。 所有输入值都是整数 ## 题目来源 ABC253C