记录编号	428405	评测结果	AAAAAA
题目名称	[POJ 1442] 黑盒子	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.077 s
提交时间	2017-07-25 16:05:51	内存使用	1.11 MiB

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <map>
using namespace std;
inline int in(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int n,m,k;
const int maxn=30010;
int sum[4*maxn];
map<int,int>pos;
int data[maxn];
int ha[maxn];
int cha[maxn];
inline void insert(int o,int l,int r,int nl,int nr){
	if(l>=nl&&r<=nr){
		sum[o]++;
		return ;
	}
	int m=(l+r)>>1,ls=o<<1,rs=ls+1;
	if(m>=nl)insert(ls,l,m,nl,nr);
	if(m<nr)insert(rs,m+1,r,nl,nr);
	sum[o]=sum[ls]+sum[rs];
}
inline int kth(int o,int l,int r,int rank){
	int m=(l+r)>>1,ls=o<<1,rs=ls+1;
	if(l==r)return l;
	if(rank<=sum[ls])return kth(ls,l,m,rank);
	if(rank>sum[ls])return kth(rs,m+1,r,rank-sum[ls]);
}
int main(){
	freopen("blackbox.in","r",stdin);
	freopen("blackbox.out","w",stdout);
	n=in();m=in();
	for(int i=1;i<=n;i++){
		data[i]=in();
		ha[i]=data[i];
	}
	for(int i=1;i<=m;i++){
		cha[i]=in();
	}
	sort(ha+1,ha+n+1);
	for(int i=1;i<=n;i++){
		if(pos[ha[i]])continue;
		pos[ha[i]]=i;
	}
	int c=1;
	for(int i=1;i<=n;i++){
		insert(1,1,30000,pos[data[i]],pos[data[i]]);
		while(i==cha[c]){
			k++;
			printf("%d\n",ha[kth(1,1,30000,k)]);
			c++;
		}
	}
	return 0;
}