本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-05-30 21:20:43

题外话：

E 题过样例，然而没调出来。
最后 rating: $\color{brown}\text{725} \rightarrow \color{brown}\text{747}$

A

略

B

略

C

题目翻译：

给你一个空集合 $S$
有 $Q$ 次操作，每次操作分三种类型。

1. 给定 $x$，向 $S$ 中加入 $x$
2. 给定 $x$ 和 $c$，设 $m$ 等于 $c$ 与 ($x$ 在 $S$ 中出现的次数) 的 min。重复从 $S$ 中删除 $x$ 数 $m$ 次
3. 输出集合中最大的数与集合中最小的数的差，保证进行此操作时集合不为空。

数据范围：

$1\ \le Q \le 2 \cdot 10^5$
$1 \le c \le Q$
$0 \le x \le 10^9$

做法：

我说一下我的做法和 $\color{black}\text{t}\color{red}\text{ourist}$ 的做法

我的做法：
可以使用一个大根堆和一个小根堆（就是两个 priority_queue）来维护最大值和最小值。然后使用 map 记录每个数出现的次数。
当加入一个数时，就将其同时丢进大根堆和小根堆，然后 map 记录这个数出现的次数加一
删数的时候，直接将 map 记录的这个数出现的次数减一就行了。要注意的是，删数的过程可能会把最大值或最小值删没，这样会影响到操作三查询结果，所以在操作三查询的时候要将大根堆和小根堆的 (通过 map 记录的 (出为 0 的队首元素)) 通过 while 不断弹出，直到队首元素在 map 中的记录次数不为 0。
至于中间的非最大最小值的数不用管，因为查询用不着，不用将它们弹出。
复杂度： $O(nlogn)$
我的代码：

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	int q;
	int op,x,c;
	priority_queue<int> que;
	priority_queue<int> que2;
	unordered_map<int,int> im;
	
	void main()
	{
		scanf("%d",&q);
		while(q--)
		{
			scanf("%d",&op);
			if(op==1)
			{
				scanf("%d",&x);
				if(!im[x])
				{
					que.push(x);
					que2.push(-x);
				}
				im[x]++;
			}
			if(op==2)
			{
				scanf("%d%d",&x,&c);
				int m=min(c,im[x]);
				im[x]-=m;
			}
			if(op==3)
			{
				while(im[que.top()]==0)
				{
					que.pop();
				}
				while(im[-que2.top()]==0)
				{
					que2.pop();
				}
				int imax=que.top();
				int imin=-que2.top();
				printf("%d\n",imax-imin);
			}
		}
	}
}
int main()
{
	Main::main();
	return 0;
}

$\color{black}\text{t}\color{red}\text{ourist}$ 的做法：
我之所以使用两个 priority_queue 分别存储最大值和最小值，是因为 priority_queue 只能访问队首元素，只需要换一个既可以访问队列中任意元素的 STL 就行了。$\color{black}\text{t}\color{red}\text{ourist}$ 使用的是 multiset，使用这个就能完成所需功能（multiset 中的元素从小到大排序） 下附 $\color{black}\text{t}\color{red}\text{ourist}$ 的代码：
注：multiset 的队首元素实际上是 multiset.end() 的上一个地址的元素，所以使用 prev 函数获取 multiset.end() 指针的上一个地址。

\/**
 *    author:  tourist
 *    created: 28.05.2022 16:02:11       
**\/
#include <bits\/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo\/debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int q;
  cin >> q;
  multiset<int> s;
  while (q--) {
    int op;
    cin >> op;
    if (op == 1) {
      int x;
      cin >> x;
      s.insert(x);
    }
    if (op == 2) {
      int x, c;
      cin >> x >> c;
      while (c--) {
        auto it = s.find(x);
        if (it == s.end()) {
          break;
        }
        s.erase(it);
      }
    }
    if (op == 3) {
      cout << (*prev(s.end()) - *s.begin()) << '\n';
    }
  }
  return 0;
}