题目描述
Black Box是一种原始的数据库。它可以储存一个整数数组，还有一个特别的变量i。最开始的时候Black Box是空的．而i等于0。这个Black Box要处理一串命令。
命令只有两种： ADD(x)：把x元素放进BlackBox; GET：i加1，然后输出BlackBox中第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=(1,2,6,6)。输入数据不用判错。 输入输出格式
输入格式：
第一行，两个整数，M，N。
第二行，M个整数，表示A(1)...A(M)。 第三行，N个整数，表示u(l)...u(N)。输出格式：
输出Black Box根据命令串所得出的输出串，一个数字一行。
输入输出样例
输入样例#1：
7 4
3 1 -4 2 8 -1000 2 1 2 6 6输出样例#1：
3
3 1 2说明
对于30%的数据，M≤10000；
对于50%的数据，M≤100000； 对于100%的数据，M≤200000。思路
有两种方法：
第一种：强行splay大法，直接按照题目意思在splay上操作。（splay可以换成其他的BST） 第二种：标准方法（堆），既然询问的k是递增的，那么可以把前k−1小的数丢到一个大根堆中，剩下的数丢到一个小根堆中，操作步骤： 1. 每加入一个数，先丢到大根堆中，再将大根堆中最大的数取出来丢到小根堆中； 2. 询问第k大的数，只需要输出小根堆中的数，然后丢到大根堆中。 3. 正确性？加入的时候，如果加入的数是加入后的数列中前k小的，那么大根堆中就是前k小的所有数，应当去除第k大的数；如果不是前k小的，那么大根堆中就是前k−1小的数加上加入的数，加入的数一定是大根堆中最大的，去除堆顶放入小根堆。 4. 询问的时候，小根堆中最小的数一定是第k大的，而将其取出后由于k需要加1为下一次询问做准备，那么应当将第k大转移到大根堆中。代码（splay版）
#includeconst int maxn=200000;struct splay_tree{ int fa[maxn+10],son[2][maxn+10],val[maxn+10],size[maxn+10],tot,root; int t(int x) { return son[1][fa[x]]==x; } int updata(int x) { size[x]=1; if(son[0][x]) { size[x]+=size[son[0][x]]; } if(son[1][x]) { size[x]+=size[son[1][x]]; } return 0; } int rotate(int x) { int k=t(x),f=fa[x]; fa[x]=fa[f]; if(fa[f]) { son[t(f)][fa[f]]=x; } son[k][f]=son[!k][x]; if(son[!k][x]) { fa[son[!k][x]]=f; } son[!k][x]=f; fa[f]=x; updata(f); updata(x); return 0; } int splay(int x,int c) { while(fa[x]!=c) { int f=fa[x]; if(fa[f]==c) { rotate(x); } else if(t(x)==t(f)) { rotate(f); rotate(x); } else { rotate(x); rotate(x); } } if(!c) { root=x; } return 0; } int newnode(int x) { ++tot; val[tot]=x; size[tot]=1; return 0; } int ins(int x) { newnode(x); if(!root) { root=tot; fa[tot]=son[0][tot]=son[1][tot]=0; return 0; } int now=root; while(now) { int p=val[now]
代码（堆版）
#include#include //pbds神教，速度比STL堆快，支持两堆的合并const int maxn=200000;__gnu_pbds::priority_queue > box;//建立一个小根堆__gnu_pbds::priority_queue w;//建立一个大根堆long long sw,m,n,now;long long a[maxn+10],u[maxn+10];int main(){ now=1; scanf("%lld%lld",&m,&n); for(int i=1; i<=m; i++) { scanf("%lld",&a[i]); } for(int i=1; i<=n; i++) { scanf("%lld",&u[i]); } for(int i=1; i<=m; i++) { w.push(a[i]); box.push(w.top()); w.pop(); while(i==u[now]) { printf("%lld\n",box.top()); w.push(box.top()); box.pop(); now++; } } return 0;}