题目链接:看看
对顶堆?如图
对顶堆就是由小根堆和大根堆所组成,小根堆的值都比大根堆的大,这种数据结构可以用来动态查询数组中的前k小值,我们要维护大根堆的数量是k,当大根堆的size大于小根堆,就把最大值push进小根堆,如果大根堆数量不够,就往小根堆里拿最小值。
代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int N=200010;
int n,m;
int a[N],b[N];
priority_queue<int,vector<int>,greater<int> >q1;
priority_queue<int>q2;
int st[N];
int cnt=1;
int main()
{
   
    cin >> n >> m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++)
        cin>>b[i],st[b[i]]++;
    for(int i=1;i<=n;i++)
    {
   
       q2.push(a[i]);
       if(q2.size()>cnt)
        {
   
            q1.push(q2.top());
            q2.pop();
        }
        while(st[i]--)
        {
   
            cout<<q2.top()<<endl;
            cnt++;
            if(q2.size()<cnt && q1.size())
            {
   
                q2.push(q1.top());
                q1.pop();
            }
        }
    }
    return 0;  
}