这道题是提高+省选-的难度，做出来的话对数据结构题目的理解会增加很多。
可以使用一种叫做对顶堆的东西，对顶堆是在线维护第n小的logn的算法。大概的思路是，假如我们要找的是第n小，我们就维护一个大小为n的（位于下方的）大顶堆，（位于上方的）小顶堆中每个元素都比大顶堆的大。在这道题中，n不变时每次有新的比他小的就把堆顶弹出到对顶（也就是小顶堆）的堆顶，每次n扩大的时候就从（上面的）小顶堆里取出堆顶放进大顶堆的堆顶……
但是看样子应该其他平衡树也是可以解决这个问题的。比如支持快速名次的splay？还有完全另一个维度复杂的主席树（区间第k大）。
这道题应该是对顶堆最简单了。但是明显是用别的数据结构更好，因为对顶堆的第n小只能慢慢变……这样真的不如splay……（当然啦！splay这么复杂，你怎么不用主席树呢？主席树还区间第k大呢？）
Pdalao说了一个，可以用BST来维护，每个节点维护左子树的名次，那么找k的时候就可以判断是进入左子树还是右子树了，陷入思考……其实还是要旋转来保持平衡树的特性……
真实的递归学习法，一个两个都不会。
动态维护第k小也可以交给各类平衡树去完成。 而且k还可以不断改。
对顶堆用来维护一种顶堆只会不断扩大的情形非常方便。和之前的动态求中位数一个道理。
这里我们根据题目命名为“黑匣子堆”：注意每次顶堆扩大时，假如底堆有元素则优先从底堆获取。
#include<bits/stdc++.h>
using namespace std; struct Black_Box_Heap{
//top_heap has the min element,bottom heap has the max element priority_queue<int,vector<int>,less<int> > top_heap;
priority_queue<int,vector<int>,greater<int> > bottom_heap; int i; Black_Box_Heap(){i=;} void add(int value){
if(top_heap.size()<=i){
top_heap.push(value);
}
else{
if(value<top_heap.top()){
bottom_heap.push(top_heap.top());
top_heap.pop();
top_heap.push(value);
}
else{
bottom_heap.push(value);
}
}
} int get(){
int t=top_heap.top();
i++;
while(top_heap.size()<=i&&!bottom_heap.empty()){
top_heap.push(bottom_heap.top());
bottom_heap.pop();
}
return t;
}
}bbh; int a[]; int main(){
int m,n;
scanf("%d%d",&m,&n);
for(int i=;i<=m;i++){
scanf("%d",&a[i]);
} int j=;
for(int i=;i<=n;i++){
int u;
scanf("%d",&u);
while(u>=j){
bbh.add(a[j]);
j++;
} printf("%d\n",bbh.get());
}
}