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

题目描述

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

命令只有两种：

ADD(x):把x元素放进BlackBox;

GET:i加1，然后输出Blackhox中第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=(l，2，6，6)。输入数据不用判错。

输入输出格式

输入格式：

第一行，两个整数，M，N。

第二行，M个整数，表示A(l)

……A(M)。

第三行，N个整数，表示u(l)

…u(N)。

输出格式：

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

输入输出样例

按照进程结束的时间输出每个进程的进程号和结束时间。

输入输出样例

input

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

output

3
3
1
2

思路：

这一道题显然不能暴力模拟。
而要一种骚操作叫做对顶堆
即：
先用一个大根堆存一下前i小的数(用来快速求出第i小的数)。
再用一个小根队存一下后面的的数。(维护剩余队列的有序性)
这样的话既可以快速找到第i小的数，又可以维护队列的有序性。

1. 每次有一个新的元素要入堆的话先把它存到小根堆里。
2. 如果有一次get操作，就把小根堆堆顶转移到大根堆中。
   然而这样似乎还不太够，因为假如在此之前小根堆中进入了某个数，且这个数比大根堆中任何数都小，那么就会咕咕咕了，所以要比较两个堆的堆顶元素。如果大根堆的堆顶大于小根堆的堆顶，那么大根堆的堆顶就一定不是前i小的数，所以就把大根堆的堆顶转移到小根堆，小根堆的堆顶转移到大根堆中。

Code：

#include<bits/stdc++.h>
using namespace std;

const int maxn=200005;
int n,m,a[maxn];

struct cmp1
{
    bool operator()(int x,int y)
    {
        return x>y;
    }
};// 小根堆，优先队列的排序就是这么神奇

struct cmp2
{
    bool operator()(int x,int y)
    {
        return x<y;
    }
};

priority_queue<int,vector<int> ,cmp1> q1;
priority_queue<int,vector<int> ,cmp2> q2;

int main()
{
    //freopen("my.out","w",stdout);
    //freopen("my.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1,j=1;i<=m;i++){
        int x;scanf("%d",&x);
        for(;j<=x;j++)
            q1.push(a[j]);
        q2.push(q1.top());q1.pop();
        while(q2.top()>q1.top() && q1.size()>0){
            int temp1=q1.top(),temp2=q2.top();
            q1.pop();q2.pop();
            q1.push(temp2);q2.push(temp1);
        }
        printf("%d\n",q2.top());
    }
    return 0;
}

所以对顶堆这个技♂巧还是强的啊！