算法
(小根堆) $O(Q\log Q)$
序列 $A$ 给人一种“前面已排好序,而后面未排序”的感觉。
对于前面的部分我们可以用小根堆来维护,而后面的部分用普通队列来维护即可,然后我们就可以做我们想干的事了QwQ
对于操作 $1$:把 $x$ 压入队列即可
对于操作 $3$:把队列中的所有元素压入小根堆
对于操作 $2$:若小根堆里有元素,则弹出最小值;若没有元素,则把队列中的队头元素弹出
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::queue;
using std::vector;
using std::greater;
using std::priority_queue;
int main() {
int Q;
cin >> Q;
priority_queue<int, vector<int>, greater<int>> pq; // 从最小值开始取出
queue<int> q;
rep(qi, Q) {
int c;
cin >> c;
if (c == 1) {
int x;
cin >> x;
q.push(x);
}
else if (c == 2) {
if (pq.size()) {
cout << pq.top() << '\n';
pq.pop();
}
else {
cout << q.front() << '\n';
q.pop();
}
}
else {
while (q.size()) {
pq.push(q.front());
q.pop();
}
}
}
return 0;
}