[数据结构与算法]洛谷P1801 黑匣子

题目描述

Black Box 是一种原始的数据库。它可以储存一个整数数组，还有一个特别的变量?ii。最开始的时候 Black Box 是空的．而?i=0i=0。这个 Black Box 要处理一串命令。

命令只有两种：

• ADD(x)：把?xx?元素放进 Black Box;

• GET：ii?加?11，然后输出 Black Box 中第?ii?小的数。

记住：第?ii?小的数，就是 Black Box 里的数的按从小到大的顺序排序后的第?ii?个元素。

我们来演示一下一个有11个命令的命令串。（如下表所示）

现在要求找出对于给定的命令串的最好的处理方法。ADD?命令共有?mm?个，GET?命令共有?nn?个。现在用两个整数数组来表示命令串：

1. a_1,a_2,\cdots,a_ma1?,a2?,?,am?：一串将要被放进 Black Box 的元素。例如上面的例子中?a=[3,1,-4,2,8,-1000,2]a=[3,1,?4,2,8,?1000,2]。

2. u_1,u_2,\cdots,u_nu1?,u2?,?,un?：表示第?u_iui??个元素被放进了 Black Box 里后就出现一个?GET?命令。例如上面的例子中?u=[1,2,6,6]u=[1,2,6,6]?。输入数据不用判错。

输入格式

第一行两个整数?mm?和?nn，表示元素的个数和?GET?命令的个数。

第二行共?mm?个整数，从左至右第?ii?个整数为?a_iai?，用空格隔开。

第三行共?nn?个整数，从左至右第?ii?个整数为?u_iui?，用空格隔开。

输出格式

输出 Black Box 根据命令串所得出的输出串，一个数字一行。

输入输出样例

输入 #1复制

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

输出 #1复制

3
3
1
2

说明/提示

数据规模与约定

• 对于?30\%30%?的数据，1 \leq n,m \leq 10^{4}1≤n,m≤104。
• 对于?50\%50%?的数据，1 \leq n,m \leq 10^{5}1≤n,m≤105。
• 对于?100\%100%?的数据，1 \leq n,m \leq 2 \times 10^{5},|a_i| \leq 2 \times 10^{9}1≤n,m≤2×105,∣ai?∣≤2×109，保证?uu?序列单调不降。

上代码：

#include <cstdio>
#include <queue>
#define Qmax priority_queue<int>
#define Qmin priority_queue<int,vector<int>,greater<int> >
#define f(i , a , b) for(int i=(a) ; i <= (b) ; i++)
using namespace std;
inline int Input(){
    char C=getchar();
    int N=0 , F=1;
    while(('0' > C || C > '9') && (C != '-')) C=getchar();
    if(C == '-') F=-1 , C=getchar();
    while('0' <= C && C <= '9') N=(N << 1)+(N << 3)+(C - 48) , C=getchar();
    return F*N; 
} //骗时间的读入优化 QAQ
int main(){
    int a[200001];
    Qmax A;
    Qmin B;
    int n=Input() , m=Input() , r=1 , q;
    f(i , 1 , n) a[i]=Input();
    f(i , 1 , m){
        q=Input();
        f(j , r , q){
            A.push(a[j]);
            if(A.size() == i) B.push(A.top()) , A.pop(); //超过大小，移除元素
        }
        r=q+1;
        printf("%d\n" , B.top()); //输出每次 GET 的答案
        A.push(B.top()) , B.pop(); //为下一次的 GET 作准备，填满小顶堆的空间
    }
    return 0;
}