记录编号	357399	评测结果	AAAAAA
题目名称	[POJ 1442] 黑盒子	最终得分	100
用户昵称	Hzoi_Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.049 s
提交时间	2016-12-11 07:18:18	内存使用	4.87 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100000*2;
#define LL long long
#define Inf 2e9
#define Begin freopen("blackbox.in","r",stdin);freopen("blackbox.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
int RT;
struct SBT{
	int size[maxn],ls[maxn],rs[maxn],v[maxn],cnt;
	void pushup(int rt){size[rt]=size[ls[rt]]+size[rs[rt]]+1;}
	void Turn_right(int & rt){//右旋 
		//把rt的左子树变成左儿子的右子树，rt成为左儿子的右儿子 
		int t=ls[rt];
		ls[rt]=rs[t];pushup(rt);
		rs[t]=rt;pushup(t);
		rt=t; 
	}
	void Turn_left(int & rt){//左旋 
		//把rt的右子树变成右儿子的左子树，rt成为右儿子的左儿子
		int t=rs[rt];
		rs[rt]=ls[t];pushup(rt);
		ls[t]=rt;pushup(t);
		rt=t;
	}
	#define Balance_all Balance(rt);Balance(ls[rt]);Balance(rs[rt]);
	void Balance(int & rt){
		if(size[ls[ls[rt]]]>size[rs[rt]]){
			Turn_right(rt);Balance_all;return;
		}
		if(size[rs[rs[rt]]]>size[ls[rt]]){
			Turn_left(rt);Balance_all;return;
		}
		if(size[rs[ls[rt]]]>size[rs[rt]]){
			Turn_left(ls[rt]);Turn_right(rt);Balance_all;return;
		}
		if(size[ls[rs[rt]]]>size[ls[rt]]){
			Turn_right(rs[rt]);Turn_left(rt);Balance_all;return;
		}
	}
	#undef Balance_all
	void Insert(int & rt,int date){
		if(rt==0){
			rt=++cnt;size[rt]=1;v[rt]=date;return;
		}
		if(date<v[rt])Insert(ls[rt],date);
		else Insert(rs[rt],date);
		pushup(rt);Balance(rt);
	}
	void Del(int & rt,int date){
		if(v[rt]==date){
			if(ls[rt]==0 && rs[rt]==0){rt=0;return;}
			if(ls[rt]==0){rt=rs[rt];return;}
			if(rs[rt]==0){rt=ls[rt];return;}
			Turn_right(rt);Del(rs[rt],date);pushup(rt);
			return;
		}
		if(v[rt]<date)Del(rs[rt],date);
		else Del(ls[rt],date);
		pushup(rt);Balance(rt);
	}
	int Get_prev(int rt,int date){
		if(rt==0)return -Inf;
		if(v[rt]<date)return max(v[rt],Get_prev(rs[rt],date));
		else return Get_prev(ls[rt],date);
	}
	int Get_succ(int rt,int date){
		if(rt==0)return Inf;
		if(v[rt]>date)return min(v[rt],Get_succ(ls[rt],date));
		else return Get_succ(rs[rt],date);
	}
	int Get_date(int rt,int th){
		if(size[ls[rt]]+1==th)return v[rt];
		if(size[ls[rt]]+1>th)return Get_date(ls[rt],th);
		else return Get_date(rs[rt],th-size[ls[rt]]-1);
	}
	int Get_th(int rt,int date){
		if(rt==0)return Inf;
		if(v[rt]==date)return min(size[ls[rt]]+1,Get_th(ls[rt],date));
		if(v[rt]>date)return Get_th(ls[rt],date);
		else return size[ls[rt]]+1+Get_th(rs[rt],date);
	}
}T;
int n,m,a[maxn],ques[maxn];
void Init();

int main(){
	Begin;
    Init();
    getchar();getchar();
    End;
	return 0;
}
void Init(){
	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",&ques[i]);
	int num=1;
	for(int i=1;i<=m;i++){
		for(;num<=ques[i];num++){
			T.Insert(RT,a[num]);
		}
		printf("%d\n",T.Get_date(RT,i));
	}
}