记录编号	465793	评测结果	AAAAAA
题目名称	[POJ 1442] 黑盒子	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.093 s
提交时间	2017-10-27 21:18:14	内存使用	16.34 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cassert>
using namespace std;
const int SIZE=600010,INF=0x7fffffff;//it should be "absolute INF"
class Node{//little root heap
public:
	int l,r;
	int key;
	int hkey;
	int sz;
	#define l(x) Tree[x].l
	#define r(x) Tree[x].r
	#define key(x) Tree[x].key
	#define hkey(x) Tree[x].hkey
	#define sz(x) Tree[x].sz
}Tree[SIZE];
// Tree[0] is empty node
int root,tot=0;
int newnode(int val){
	int hs=((rand()<<15)|rand())&0x7fffffff; // hath
	tot++;
	key(tot)=val;
	hkey(tot)=hs;
	sz(tot)=1;
	return tot;
}
void update(int x){
	sz(x) = sz(l(x)) + sz(r(x)) + 1;
}
//to rotate x, we mean to get x "pushed" to next layer
int zag(int x){//left-rotate
	int y=r(x);
	r(x)=l(y);
	l(y)=x;
	update(x);
	update(y);
	return y;
}
int zig(int x){//right-rotate
	int y=l(x);
	l(x)=r(y);
	r(y)=x;
	update(x);
	update(y);
	return y;
}
int insert(int x,int val){
	if(val<key(x)){
		if(!l(x)) l(x)=newnode(val);
		else l(x)=insert(l(x),val);
	}
	else{
		if(!r(x)) r(x)=newnode(val);
		else r(x)=insert(r(x),val);
	}
	if(hkey(l(x)) < hkey(x)) x=zig(x);
	else if(hkey(r(x)) < hkey(x)) x=zag(x);
	else update(x);
	assert(x);
	return x;
}
int get_kth(int x,int k){
	assert(x);
	//cout<<x<<" "<<sz(x)<<" "<<k<<endl;
	int a=sz(l(x));
	if(k<=a) return get_kth(l(x),k);
	else if(k==a+1) return key(x);
	else return get_kth(r(x),k-a-1);
}
void init(void){
	key(0) = 0;
	hkey(0) = INF;//to avoid "rotate 0 up"
	root = newnode(-INF);
	root = insert(root,INF);
}
int N,M;
int A[SIZE],U[SIZE];
void work(void){
	int p=1,rnk=0;
	for(int i=1;i<=M;i++){
		root=insert(root,A[i]);
		while(p<=N&&U[p]<i) p++;
		while(p<=N&&U[p]==i){
			rnk++;
			printf("%d\n",get_kth(root,rnk+1));
			p++;
		}
	}
}
void read(void){
	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",&U[i]);
}
int main(){
	//freopen("blackbox1.in","r",stdin);
	freopen("blackbox.in","r",stdin);
	freopen("blackbox.out","w",stdout);
	read();
	init();
	work();
	return 0;
}