【2020-8-23】【黑匣子】【对顶堆】

今天开学了枯辽军训好累

晚上为了逃掉校长的讲座请假来了机房

看到了前几天写的一个对顶堆的题目

题面：

Black Box是一种原始的数据库。它可以存储一个整数数组，还有一个特别的变量i。最开始的时候Black Box是空的，而i等于0。这个Black Box要处理一串命令。
　　命令只有两种：
　　　ADD（x）：把x元素放进Black Box；
　　　GET：i加1，然后输出Black Box中第i小的数。
　　记住：第i小的数，就是Black Box里的数按从小到大的顺序排序后的第i个元素。

现在要求找出对于给定的命令串的最好的处理方法。ADD和GET命令分别最多有200000个。
现在用两个整数数组来表示命令串：
　　1.A(1),A(2)，…A(M)：一串将要被放进Black Box的元素。每个数都是绝对不超过2000000000的整数，M≤200000。例如上面的例子就是A=（3,1,-4,2,8,-1000,2）。
　　2.u(1),u(2),…u(N)：表示第u(j)个元素被放进了Black Box里后就出现了一个GET命令。例如上面的例子中的u=（1,2,6,6）。

　　输入数据不用判错。

大概的意思是在线求一个有序数组的第i个数

看到这题的第一个反应是平衡树splay但是因为没有怎么写过所以口胡了一个对顶堆的写法

我们在线维护两个堆一个是在数组里前i个数一个是剩下的数

第一个堆是大根堆第二个堆是小根堆所以一二两个堆的根是相邻的

对于每次Get 我们从A数组中输入数据每次比上次Get答案小的放入第一个堆否则放入第二个堆

对于第一个堆明显大小是i 如果大小大于i 则将根出堆放入第二个堆所以对于每次Get 第一个堆的跟就是答案

#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; 
}
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
" , B.top()); 
        A.push(B.top()) , B.pop(); 
    }
    return 0;
}

View Code