法一：算法思想较精妙--两个堆
先将数字放入大根堆，然后取出堆顶元素，放入小根堆，如果要求输出，则取出小根堆堆顶元素，输出并放入大根堆。
如何得出的呢？
先从简单的开始：
若当前已经add了x-1个数，将要add第x个数并查询，还未进行过查询，那么将x放入后，小根堆中应该是从小到大排好的所有数，则会输出最小的数并将其放入大根堆。
若还要add第x+1个数，并进行第2次查询，那么大根堆堆顶会是"1~x个数中最小的那个数"还有"x+1个数"中较大的那个，将其取出并放入小根堆后，显然1~x+1个数中最小的那个还在大根堆中，那么小根堆堆顶就是第2小的数了。
若还要add一些数，但是不查询，那么显然，不管怎么add，所有数中最小的2个永远会被留在大根堆中，小根堆堆顶永远是第3小的。
若这之后要查询，那么以后再add时就能确保所有数中最小的3个永远会被留在大根堆中，小根堆堆顶永远是第4小的。
......
按照这样类比，很容易知道解法。
#include<cstdio>
#include<queue>
using namespace std;
priority_queue<int> q1;//大根堆
priority_queue<int,vector<int>,greater<int> > q2;//小根堆
int m,n;
int a[300000];
int main()
{
int i,j,k,p;
scanf("%d%d",&m,&n);
for(i=1;i<=m;i++)
scanf("%d",&a[i]);
int s=0;
for(i=1;i<=n;i++)
{
scanf("%d",&k);
while(s<k)
{
q1.push(a[++s]);
p=q1.top();
q1.pop();
q2.push(p);
}
p=q2.top();
q2.pop();
printf("%d
",p);
q1.push(p);
}
return 0;
}
题解里有一种类似的：
法二：数据结构--平衡树