【NOI导刊】黑匣子

我们使用黑匣子的一个简单模型。它能存放一个整数序列和一个特别的变量i。在初始时刻，黑匣子为空且i等于0。这个黑匣子能执行一系列的命令。有两类命令：

ADD(x)：把元素x放入黑匣子；GET：把i加1的同时，输出黑匣子内所有整数中第i小的数。牢记第i小的数是当黑匣子中的元素已非降序排序后位于第i位的元素。

下面的表6_4是一个11个命令的例子：

表6_4

现需要一个有效的算法处理给定的一系列命令。ADD和GET命令的总数至多个有30000个。定义ADD命令的个数为M个，GET命令的个数为N个。我们用下面得两个整数序列描述命令序列：

1．A(1),A(2),……,A(M)：加入黑匣子的元素序列。所有的数均为绝对值不超过2000000的整数。例如在上例中A=(3,1,-4,2,8,-1000,2)。

2．u(1),u(2),……,u(N)：u(i)表示第i个GET命令在第u(i)个ADD命令之后，例如在上例中，u=(1,2,6,6)。

你可以假定自然数序列u(1),u(2),……,u(N)以非降序排列，N≤M，且对于每一个p（1≤p≤N）有p≤u(p)≤M。

第一行存放M和N的值,第二行存放 A(1),A(2),……,A(M) ,第三行存放u(1),u(2),……,u(N)。

输出黑匣子的处理结果。

7 4

3 1 -4 2 8 -1000 2

1 2 6 6

3

3

1

2 

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

听说这题有一种很J形的做法是开一个大根堆一个小根堆互扔...？【mengbi】反正这题的话用平衡树也能过，维护两个操作：添加与查找第k大元素，添加的话考虑几种情况，然后查找也是分类讨论，具体实现的话可以看代码。

#include <cstdio>#include <algorithm>#include <cstdlib>using namespace std;const int maxx = 50000 + 100;int a[maxx],b[maxx];int n,num,root,x,m,now;struct Node{	int lc,rc;	int v,fix;	int size,cnt;}T[maxx];void update(int i){	T[i].size = T[T[i].lc].size + T[T[i].rc].size +T[i].cnt;}void lturn(int &i){	int t = T[i].rc;	T[i].rc = T[t].lc;	T[t].lc = i;	T[t].size = T[i].size;	update(i);	i = t;}void rturn(int &i){	int t = T[i].lc;	T[i].lc = T[t].rc;	T[t].rc = i;	T[t].size = T[i].size;	update(i);	i = t;}void insert(int &i,int x){	if(i == 0){		num++;		i = num;		T[i].v = x;		T[i].size = T[i].cnt = 1;		T[i].fix = rand();		return;	}//当此节点为空 	T[i].size++;	if(T[i].v == x) T[i].cnt++;	if(x < T[i].v){		insert(T[i].lc,x);		if(T[T[i].lc].fix < T[i].fix) rturn(i);	}//小于往左加，并且通过旋转维护堆性质 	if(x > T[i].v){		insert(T[i].rc,x);		if(T[T[i].rc].fix < T[i].fix) lturn(i);	}//大于往右加 }int Query_num(int i,int x){	if(i == 0) return 0;	if(x <= T[T[i].lc].size) return Query_num(T[i].lc,x);//每个数的排名：左子树大小+1，所以如果小于等于左子树大小，说明往左找 	if(x > T[T[i].lc].size + T[i].cnt)//如果大于左子树大小加重复元素，往右找 		return Query_num(T[i].rc,x-T[T[i].lc].size-T[i].cnt);//注意此时还需要找的个数为x-T[T[i].lc].size-T[i].cnt。 	else return T[i].v;}int main(){	scanf("%d%d",&n,&m);	for(int i=1;i<=n;i++)		scanf("%d",&a[i]);	for(int i=1;i<=m;i++)		scanf("%d",&x),b[x]++;//记录哪些数之后有操作 	for(int i=1;i<=n;i++){		insert(root,a[i]);		while(b[i]--){			now++;			PRintf("%d/n",Query_num(root,now));		}	}	return 0;}
QvQ........