记录编号	142997	评测结果	WEEEEE
题目名称	[POJ 1442] 黑盒子	最终得分	0
用户昵称	JSX	是否通过	未通过
代码语言	C++	运行时间	0.366 s
提交时间	2014-12-12 13:24:21	内存使用	1.53 MiB

#include <cstdlib>
#include <algorithm>
#include <cstdio>
#include <ctime>
using namespace std;
const int INF = 0x3f3f3f3f;
 
struct Node{
	Node *ch[2];
	int r,v,s;
	int cmp(int x){
		if(x==v) return -1;
		else return x < v ? 0 : 1;
	}
	void maintain(){ s=ch[0]->s+ch[1]->s+1; }
};
 
int M=0,N=0;
int A[200010]={0},B[200010]={0};
 
Node *Empty=new Node();
Node *Root =Empty;
 
inline void rotate(Node* &o,int d){
	Node* k=o->ch[d^1]; if(k==Empty) return;
	o->ch[d^1]=k->ch[d]; k->ch[d]=o;
	o->maintain(); k->maintain(); o=k;
}
 
inline void Insert(Node* &o,int x){
	if(o==Empty){
		o=new Node(); o->ch[0]=o->ch[1]=Empty; o->v=x; o->r=rand(); o->s=1;
		return;
	}
	else{
		int d=o->cmp(x);//小于等于放在左边
		Insert(o->ch[d],x);
		if(o->ch[d]->r > o->r) rotate(o,d^1);
		o->maintain();
	}
}
 
inline int rank(Node* o,int x){
	if(o==Empty) return 0;
	int d=o->cmp(x);
	if(d==-1) return o->ch[0]->s+1;
	else{
		if(d==1) return o->ch[0]->s+1+rank(o->ch[1],x);
		else return rank(o->ch[0],x);
	}
}
 
inline int Kth(Node* o,int k){
	if(o==Empty || k<=0 || k>o->s) return 0;
	int s=o->ch[0]->s;
	if(s+1<=k) return o->v;
	else{
		if(k<=s) return Kth(o->ch[0],k);
		else return Kth(o->ch[1],k-s-1);
	}
}
 
int main(){
	freopen("blackbox.in","r",stdin);
	freopen("blackbox.out","w",stdout);
	srand(time(NULL));
	scanf("%d%d",&M,&N);
	for(int i=1;i<=M;++i)	scanf("%d",&A[i]);
	for(int i=1;i<=N;++i)	scanf("%d",&B[i]);
 
	for(int i=1;i<=N;++i){
		for(int j=B[i-1]+1;j<=B[i];++j){
			Insert(Root,A[j]);
		}
		printf("%d\n",Kth(Root,i));
	}
 
 	//while(1);
	return 0;
}