记录编号	233482	评测结果	AAAAAA
题目名称	[POJ 1442] 黑盒子	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.041 s
提交时间	2016-03-05 08:17:48	内存使用	1.09 MiB

#include<cstdio> 
#include<algorithm>
#define lch(x) x<<1
#define rch(x) x<<1|1
using namespace std;
int st[120050];
int ori[30005];
int num[30005];
int dict[30005];
void insert(int rt,int l,int r,int x){
//	printf("i(%d %d %d)",l,r,x);
	if(l==x&&r==x){
		st[rt]++;
	}else{
		int mid=(l+r)>>1;
		if(x<=mid)insert(lch(rt),l,mid,x);
		else insert(rch(rt),mid+1,r,x);
		st[rt]=st[lch(rt)]+st[rch(rt)]; 
	}
}
int query(int rt,int l,int r,int x){//返回离散化后的值 
//	printf("q(%d %d %d)",l,r,x);
	if(l==r&&x==1)return l;
	int mid=(l+r)>>1;
	if(st[lch(rt)]>=x)return query(lch(rt),l,mid,x);
	else return query(rch(rt),mid+1,r,x-st[lch(rt)]);
}
bool cmp(const int &a,const int &b){
	return ori[a]<ori[b];
}
int read(){
	int x;char ch;bool minus=false;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if(ch=='-'){
		ch=getchar();
		minus=true;
	}
	x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
	return minus?-x:x;
}
//思路一：离散化后建立线段树，每个节点存储该区间内有几个数 查询时根据数的总数进行二分总体O(nlogn)
//思路二：快速查找，选取轴点，平均nlogn，最差n^2 
int main(){
	freopen("blackbox.in","r",stdin);
	freopen("blackbox.out","w",stdout);
	int m,n;n=read();m=read();
	for(int i=1;i<=n;++i){
		ori[i]=read();
		num[i]=i;
	}
	//离散化 
	sort(num+1,num+1+n,cmp);
	int cnt=0,old=2000009;
	for(int i=1;i<=n;++i){
	//	if(ori[num[i]]!=old){
	//		old=ori[num[i]];
			dict[num[i]]=++cnt;
	//	}else dict[num[i]]=cnt;
	}
//	for(int i=1;i<=n;++i)printf("%d ",dict[i]);
	
	int pos,k=1;
	for(int i=1;i<=m;++i){//循环变量i同时表示查询第几小的数 
		pos=read();
		for(;k<=pos;++k)insert(1,1,n,dict[k]);
		int q=query(1,1,n,i);//现在需要找到q离散化之前的值 
		printf("%d\n",ori[num[q]]); 
	}
	fclose(stdin);fclose(stdout);
	return 0;
}