【题目来源】
https://www.luogu.com.cn/problem/P1801
【题目描述】
Black Box 是一种原始的数据库。它可以储存一个整数数组，还有一个特别的变量 i。最开始的时候 Black Box 是空的。而 i=0。这个 Black Box 要处理一串命令。
命令只有两种：
● ADD(x）：把 x 元素放进 Black Box；
● GET：i 加 1，然后输出 Black Box 中第 i 小的数。
记住：第 i 小的数，就是 Black Box 里的数的按从小到大的顺序排序后的第 i 个元素。
我们来演示一下一个有 11 个命令的命令串。（如下表所示）
现在要求找出对于给定的命令串的最好的处理方法。ADD 命令共有 m 个，GET 命令共有 n 个。现在用两个整数数组来表示命令串：
1. a1，a2，…，am：一串将要被放进 BlackBox 的元素。例如上面的例子中 a=[3,1,−4,2,8,−1000,2]。
2. u1，u2，…，un：表示第 ui 个元素被放进了 Black Box 里后就出现一个 GET 命令。例如上面的例子中 u=[1,2,6,6] 。输入数据不用判错。
【输入格式】
第一行两个整数 m 和 n，表示元素的个数和 GET 命令的个数。
第二行共 m 个整数，从左至右第 i 个整数为 ai，用空格隔开。
第三行共 n 个整数，从左至右第 i 个整数为 ui，用空格隔开。
【输出格式】
输出 Black Box 根据命令串所得出的输出串，一个数字一行。
【输入样例】
7 4
3 1 -4 2 8 -1000 2
1 2 6 6
【输出样例】
3
3
1
2
【数据范围】
● 对于 30% 的数据，1≤n,m≤10^4。
● 对于 50% 的数据，1≤n,m≤10^5。
● 对于 100% 的数据，1≤n,m≤2×10^5，|ai|≤2×10^9，保证 u 序列单调不降。
【算法分析】
● 堆是「抽象思想 / 数据结构」，priority_queue 是「C++ 对堆的封装实现」。
（1）简单而言，priority_queue 是 C++ 对 “堆” 这个数据结构的封装实现，但堆的概念比 priority_queue 更宽泛（比如还有左偏树、二项堆等特殊堆）。
（2）priority_queue 是堆的 “常用款实现”，但堆不仅仅只有 priority_queue 这一种实现。
（3）在需要堆的「高级功能」时，会发现 priority_queue 只是堆的 “子集实现”。例如，priority_queue 只能删除堆顶，无法直接删除中间节点等。
● 左偏树
（1）左偏树是一种可合并的堆（也叫 “可并堆”），它在普通二叉堆（大根 / 小根堆）的基础上，增加了「快速合并两个堆」的能力，同时保证堆的性质（小根堆：父节点≤子节点；大根堆反之）。普通二叉堆合并两个堆的时间复杂度是 O(n)，而左偏树能做到 O(logn)，这是它的核心优势。
（2）STL 未提供左偏树的实现，必须手动实现（指针 / 结构体 + 递归）。
● 为什么大家常说 “priority_queue 就是堆”？
在 C++ 日常开发 / 算法题中，99% 的场景只需要普通二叉堆（大根 / 小根堆），而 priority_queue刚好完美封装了普通二叉堆的所有核心操作。
（1）小根堆：priority_queue<int,vector<int>,greater<int>> pq;
（2）大根堆：priority_queue<int> pq;
【算法代码】
#include <bits/stdc++.h>
using namespace std;priority_queue<int,vector<int>,greater<int>> s;
priority_queue<int> g;int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n,m;cin>>n>>m;vector<int> a(n+1,0),u(m+1,0);for(int i=1; i<=n; i++) {cin>>a[i];}for(int i=1; i<=m; i++) {cin>>u[i];}int p=0;for(int i=1; i<=m; i++) {while(p<u[i]) {p++;g.push(a[p]);s.push(g.top());g.pop();}cout<<s.top()<<endl;g.push(s.top());s.pop();}return 0;
}/*
in:
7 4
3 1 -4 2 8 -1000 2
1 2 6 6out:
3
3
1
2
*/
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/158207666
https://blog.csdn.net/hnjzsyjyj/article/details/146358448
https://www.cnblogs.com/Seren-blingbling/p/19413027