UVA501 Black Box

题意

要求维护一个序列，可以动态插入和查询第 $k$ 大。

命令总数 $\le 30000$ 。

题解

用两个堆维护，大根堆大小为 $k-1$ ，其余放入小根堆。

1. 插入操作时，先插入大根堆，然后取堆顶放入小根堆。
2. 查询操作时，答案就是小根堆顶，并将答案放入大根堆。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int t,n,m,add[30005],Get[30005];

signed main()
{
    t=read();
    while (t--)
    {
        priority_queue <int> mx;
        priority_queue <int,vector<int>,greater<int> > mn;
        n=read(); m=read();
        for (int i=1;i<=n;i++) add[i]=read();
        for (int i=1;i<=m;i++) Get[i]=read();
        int j=1;
        for (int i=1;i<=n;i++)
        {
            mx.emplace(add[i]);
            mn.emplace(mx.top());
            mx.pop();
            while (Get[j]==i && j<=m)
            {
                printf("%d\n",mn.top());
                mx.emplace(mn.top());
                mn.pop();
                j++;
            }
        }
        if (t) puts("");
    }
    return 0;
}