C++ 代码

#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<functional>
using namespace std;

int v[30005];
int op[30005];

//整体思想和动态中位数差不多
int main()
{
    int m,n;
    cin>>m>>n;

    int i;
    for(i=1;i<=m;++i)cin>>v[i];
    for(i=1;i<=n;++i)cin>>op[i];

    //左边为大顶堆
    //左边元素的数量永远为i-1个
    //这样可以保证每次查询的答案在rq的顶部
    //rq为小顶堆
    priority_queue<int> lq;
    priority_queue<int,vector<int>,greater<int>> rq;

    int l=1,r=1;
    while(l<=m && r<=n)
    {
        //每次先将数放在左边的堆当中
        //在将左边堆中最大的值放到右边的堆中
        lq.push(v[l]);
        int t=lq.top();
        lq.pop();
        rq.push(t);
        while(r<=n && op[r]==l)
        {
            //每次rq的顶部即为查询的答案
            t=rq.top();
            rq.pop();
            lq.push(t);
            r++;
            cout<<t<<endl;
        }
        l++;
    }
    return 0;

}