题目描述
Black Box是一种原始的数据库。它可以储存一个整数数组，还有一个特别的变量i。最开始的时候Black Box是空的．而i等于0。这个Black Box要处理一串命令。
命令只有两种：
ADD(x):把x元素放进BlackBox;
GET:i加1，然后输出Blackhox中第i小的数。
记住：第i小的数，就是Black Box里的数的按从小到大的顺序排序后的第i个元素。例如：
我们来演示一下一个有11个命令的命令串。（如下图所示）
现在要求找出对于给定的命令串的最好的处理方法。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根据命令串所得出的输出串，一个数字一行。
输入输出样例
7 4 3 1 -4 2 8 -1000 2 1 2 6 6
3 3 1 2
说明
对于30%的数据，M≤10000;
对于50%的数据，M≤100000：
对于100%的数据，M≤200000。
思路：不难想到求第i小需要堆排序。
难点：难道每输出一个数，就要维护堆后重新堆排一遍？
机关（优化）：只需求第i小的（即对于第i小的这个元素之前是否按顺序排好无要求）。
分析：堆的一个特点是只知最大（小）的那个元素，剩余位置较混乱；这也是它快的一个原因。
【故求第i小，则可以建一个含i个元素的大根堆，堆顶即为所求】。
而i个之外的元素可以放在另一个【小根堆】中，【以便向大根堆中补给】。
难点：随着输入数的增多，第i小的值会不断变化。
先把输入的数据都输完了，才输要求输出的数据；如何做到随时向那个大根堆中补给适当的数？
思路：只需要将输入的数存入一个数组，就可以做到适时输入一样的效果，方便地取用。
于是诞生了很快的代码（n·logn）：
#include<iostream> #include<cstdio> using namespace std; int n,m,xnt1,xnt2,s=1; long long c,hp1[200005],hp2[200005],a[200005];//hp1为那个小根堆,hp2为那个大根堆 void pus1(long long a) { xnt1++; hp1[xnt1]=a; int now=xnt1; while(now>1) { int tp=now/2; if(hp1[tp]>hp1[now])swap(hp1[tp],hp1[now]); else break; now=tp; } } void pus2(long long a) { xnt2++; hp2[xnt2]=a; int now=xnt2; while(now>1) { int tp=now/2; if(hp2[tp]<hp2[now])swap(hp2[tp],hp2[now]); else break; now=tp; } } long long del1() { long long res=hp1[1]; hp1[1]=hp1[xnt1]; xnt1--; int now=1; while(now*2<=xnt1) { int tp=now*2; if(tp<xnt1&&hp1[tp+1]<hp1[tp])tp++; if(hp1[tp]<hp1[now])swap(hp1[tp],hp1[now]); else break; now=tp; } return res; } long long del2() { long long res=hp2[1]; hp2[1]=hp2[xnt2]; xnt2--; int now=1; while(now*2<=xnt2) { int tp=now*2; if(tp<xnt2&&hp2[tp+1]>hp2[tp])tp++; if(hp2[tp]>hp2[now])swap(hp2[tp],hp2[now]); else break; now=tp; } return res; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); for(int i=1;i<=m;i++) { scanf("%lld",&c); for(;s<=c;s++) { if(!hp2[1]) { pus2(a[s]);continue; } if(a[s]>=hp2[1])pus1(a[s]); else { if(xnt2==i)//原来xnt2是i-1,当已经进入过一个元素后,再要进入,就需调整 pus1(del2());//把原来的堆顶挤入hp1中 pus2(a[s]); } } if(xnt2<i) pus2(del1());//从hp1中取出一个放入hp2 printf("%lld ",hp2[1]); } }