题目描述

黑盒子代表一个原始的数据库。

它可以用来储存整数数组，并且它拥有一个特殊变量i。

在最开始，黑盒子是空的，并且i=0。

现在对黑盒子进行一系列的操作处理，操作包括以下两种：

1、ADD(x)：表示将x加入到黑盒子中。
2、GET：使i增加1，输出黑盒子中第i小的数值（即将所有数按升序排序后的第i个数）。

下面给出一个具体例子：

序号 操作        i     盒子内数（升序排列后）             输出的值 
1    ADD(3)      0     3   
2    GET         1     3                                    3 
3    ADD(1)      1     1, 3   
4    GET         2     1, 3                                 3 
5    ADD(-4)     2     -4, 1, 3   
6    ADD(2)      2     -4, 1, 2, 3   
7    ADD(8)      2     -4, 1, 2, 3, 8   
8    ADD(-1000)  2     -1000, -4, 1, 2, 3, 8   
9    GET         3     -1000, -4, 1, 2, 3, 8                1 
10   GET         4     -1000, -4, 1, 2, 3, 8                2 
11   ADD(2)      4     -1000, -4, 1, 2, 2, 3, 8   

为了方便描述，下面我们定义两个序列：

1、A(1),A(2),…,A(M)：这个序列由加入到黑盒子内的所有元素按加入顺序排列后得到，上例中的A序列为(3,1,-4,2,8,-1000,2)。

2、u(1),u(2),…,u(N): 这个序列的第i项表示的是第i次GET操作时，盒子内元素的数量。上例中的u序列为(1,2,6,6)。

现在请你根据给出的序列A和u求出操作过程中输出的所有数值。

输入格式
输入包括三行。

第一行包含两个整数M和N，表示A序列和u序列的长度。

第二行包含M个整数，表示A序列的每一个元素。

第三行包含N个整数，表示u序列的每一个元素。

同行每个数之间用空格隔开。

输出格式
输出操作过程中所有GET操作输出的数值。

每个数值占一行。

数据范围
$|A(i)|<=2∗10^9$
$1≤N≤M≤30000$
对于所有$p（1≤p≤N）, p≤u(p)≤M$成立

样例

输入样例：
7 4
3 1 -4 2 8 -1000 2
1 2 6 6
输出样例：
3
3
1
2

对顶堆

拿到题目看一眼,大致就能确定是要用堆数据结构去处理,问题是怎么处理,这道题目不同于一般的堆的题目,他需要的是第K小的数,而不是最值.那么既然如此的话,我们就要思考如果取出这个最值,一个想法是开一个指针记录第K小的数,但是这个算法明显不好用而且也不好处理,那么我们可以在这个思想的前提下,进行拓展.

我们可以使用之前求动态中位数的时候的对顶堆算法,也就是大根堆和小根堆分别存放前i-1大的元素和第i到第k大的元素。然后每一次将当前序列的元素压入小根堆，如果小根堆的最小数大于大根堆的最大数则进行交换.

也就是要保证,我们的大根堆中的所有数都必须小于小根堆中的数。而且还要注意,i每一次都是要增加1的,所以我们每次做完Get操作后,都需要最小堆中的最小数弹出存入最大堆,也就是满足第K小,因为K就是i,所以我们要这么处理。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=3e4+10;
priority_queue<int> q;
priority_queue<int, vector<int> ,greater<int> > q2;
int num[N],n,m,x;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        scanf("%d",&num[i]);
    int k=1;
    for(int i=1; i<=m; i++)
    {
        scanf("%d",&x);
        while(k<=x)
        {
            q2.push(num[k]);
            if(!q.empty() && q.top()>q2.top())
            {
                int t=q.top();
                q.pop();
                q2.push(t);
                t=q2.top();
                q2.pop();
                q.push(t);
            }
            k++;
        }
        printf("%d\n",q2.top());
        int t=q2.top();
        q2.pop();
        q.push(t);
    }
    return 0;
}