题解 | #两端问优先队列#

普通的堆只能要么维护最小值要么维护最大值，对于本题这种需要同时维护最小最大值的数据结构，我们可以先直接各开一个小根堆大根堆，剩下的重点则是保证每个插入数据的唯一性。

对此，一种非常经典的保证数据唯一性的方法，我称其为「惰性删除」。具体而言，我们首先给每个插入数据分配唯一的序列号 serial，然后新建一个布尔数组 ondelete，其中 ondelete[x] 表示序列号为 x 的数据是否已经被删除。

建立堆的时候，插入的数据类型为 pair<int, int>，第一个是数据值 ，第二个是序列号 serial。根据 C++ 里面 pair 的默认比较方式， 仍然会先被比较，所以直接使用不会有影响。对于堆顶元素，我们可以通过其序列号查询它有没有被删除。如果根据 ondelete 数组它已经被删了，则直接弹出，直到堆为空或发现一个没被删的元素。

参考代码：

#include <cstdlib>
#include <iostream>
#include <functional>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int main() {

    int n;
    cin >> n;

    using node = pair<int, int>;
    priority_queue<node, vector<node>, greater<>> minpq;
    priority_queue<node> maxpq;
    vector<char> ondelete;
    ondelete.reserve(n);
    int serial = 0;

    for(int i = 0; i < n; ++i) {
        int op;
        cin >> op;
        switch (op) {
        case 1: {
            int x;
            cin >> x;
            minpq.emplace(x, serial);
            maxpq.emplace(x, serial);
            ondelete.emplace_back(0);
            ++serial;
            break;
        }
        case 2: {
            for(; !minpq.empty() && ondelete[minpq.top().second]; minpq.pop());
            cout << minpq.top().first << '\n';
            break;
        }
        case 3: {
            for(; !maxpq.empty() && ondelete[maxpq.top().second]; maxpq.pop());
            cout << maxpq.top().first << '\n';
            break;
        }
        case 4: {
            for(; !minpq.empty() && ondelete[minpq.top().second]; minpq.pop());
            ondelete[minpq.top().second] = 1;
            minpq.pop();
            break;
        }
        case 5: {
            for(; !maxpq.empty() && ondelete[maxpq.top().second]; maxpq.pop());
            ondelete[maxpq.top().second] = 1;
            maxpq.pop();
            break;
        }
        }
    }
}