题解 P1801 【黑匣子_NOI导刊2010提高（06）】

· · 题解

平衡树是什么？初一党无法理解！

（然而现在已经是一个初二了，只能说略懂平衡树）

本题使用 两种优先队列：大顶堆和小顶堆 即可解决，比平衡树好理解但不能保证比平衡树快，具体思路和楼下某篇题解类似，但是这里我只将 ADD 函数的参数存在数组里，而 GET 函数输入就当即处理。阐明一下思路吧：用小顶堆维护第 i 大的值，那么第 i 大以前的数呢？存在大顶堆里，与小顶堆独立。GET 函数的数量决定了大顶堆限制的大小。第一次 GET，大顶堆不开放，数直接放入小顶堆，因此第 i 大（即第 1 大）的值就是那个数；第二次 GET，大顶堆的大小增加一，数进入小顶堆前先看看能不能被大顶堆容下，push 进大顶堆，将大顶堆的队首移入小顶堆（切勿忘记 pop 掉大顶堆的队首），此时小顶堆队首是第 2 大的。依此类推。因此，第 i 次 GET，大顶堆的大小为 i - 1，一旦大顶堆的大小超过 i - 1，队首就移入小顶堆，这样一来，此时小顶堆的队首就是第 i 大的数。

#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;
}