我們使用黑匣子的一個簡單模型。它能存放一個整數(shù)序列和一個特別的變量i。在初始時刻，黑匣子為空且i等于0。這個黑匣子能執(zhí)行一系列的命令。有兩類命令：

ADD(x)：把元素x放入黑匣子；GET：把i加1的同時，輸出黑匣子內(nèi)所有整數(shù)中第i小的數(shù)。牢記第i小的數(shù)是當(dāng)黑匣子中的元素已非降序排序后位于第i位的元素。

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

表6_4

現(xiàn)需要一個有效的算法處理給定的一系列命令。ADD和GET命令的總數(shù)至多個有30000個。定義ADD命令的個數(shù)為M個，GET命令的個數(shù)為N個。我們用下面得兩個整數(shù)序列描述命令序列：

1．A(1),A(2),……,A(M)：加入黑匣子的元素序列。所有的數(shù)均為絕對值不超過2000000的整數(shù)。例如在上例中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)。

你可以假定自然數(shù)序列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)。

輸出黑匣子的處理結(jié)果。

7 4

3 1 -4 2 8 -1000 2

1 2 6 6

3

3

1

2 

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

聽說這題有一種很J形的做法是開一個大根堆一個小根堆互扔...？【mengbi】反正這題的話用平衡樹也能過，維護(hù)兩個操作：添加與查找第k大元素，添加的話考慮幾種情況，然后查找也是分類討論，具體實現(xiàn)的話可以看代碼。

#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;	}//當(dāng)此節(jié)點為空 	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);	}//小于往左加，并且通過旋轉(zhuǎn)維護(hù)堆性質(zhì) 	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);//每個數(shù)的排名：左子樹大小+1，所以如果小于等于左子樹大小，說明往左找 	if(x > T[T[i].lc].size + T[i].cnt)//如果大于左子樹大小加重復(fù)元素，往右找 		return Query_num(T[i].rc,x-T[T[i].lc].size-T[i].cnt);//注意此時還需要找的個數(shù)為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]++;//記錄哪些數(shù)之后有操作 	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........