记录编号	493893	评测结果	AAAAAA
题目名称	[POJ 1442] 黑盒子	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.138 s
提交时间	2018-04-06 12:23:39	内存使用	0.89 MiB

#include<bits/stdc++.h>

#define maxn 30010

using namespace std;

int rnd[maxn],l[maxn],r[maxn],v[maxn],siz[maxn],rot;

void update(int x)
{
	siz[x]=siz[l[x]]+siz[r[x]]+1;
}

void rt(int &x)
{
	int t=l[x];
	l[x]=r[t];
	r[t]=x;
	update(x);
	x=t;
}

void lt(int &x)
{
	int t=r[x];
	r[x]=l[t];
	l[t]=x;
	update(x);
	x=t;
}

void insert(int &n,int x)
{
	if(!n){ n=x;return; }
	if(v[x]<v[n]){
		insert(l[n],x);
		if(rnd[l[n]]>rnd[n]) rt(n);
	}
	else{
		insert(r[n],x);
		if(rnd[r[n]]>rnd[n]) lt(n);
	}
	update(n);
}

int ask(int x,int k)
{
	if(k==siz[l[x]]+1) return v[x];
	if(k<=siz[l[x]]) return ask(l[x],k);
	else return ask(r[x],k-siz[l[x]]-1);
}

int main()
{
	freopen("blackbox.in","r",stdin);
	freopen("blackbox.out","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&v[i]); 
	}
	int h=1;
	for(int i=1;i<=m;i++){
		int x;scanf("%d",&x);
		while(h<=x){
			rnd[h]=rand();
			siz[h]=1;
			insert(rot,h++);
		}
		printf("%d\n",ask(rot,i));
	}
}