记录编号	156043	评测结果	AAAAAAAAAA
题目名称	[SDOI 2007] 超级数组	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	0.448 s
提交时间	2015-04-01 18:55:14	内存使用	0.31 MiB

#include<cstdio>
#include<cstdlib>
struct node{
	node *c[2];
	int v,r,siz;
	node(){c[0]=c[1]=NULL;v=r=siz=0;}
	void update(){siz=c[0]->siz+c[1]->siz+1;}
	void init(int x);
};
node *Null=new node,*root;
void node::init(int x){
	v=x,r=rand(),siz=1;
	c[0]=c[1]=Null;
}
void in(int &x){
	int ch;
	while((ch=getchar())<48);x=ch-48;
	while((ch=getchar())>47) x=x*10+ch-48;
}
void rot(node *&o,int d){
	node *tmp=o->c[!d];
	o->c[!d]=tmp->c[d],tmp->c[d]=o;
	o->update(),tmp->update(),o=tmp;
}
void ins(node *&o,int x){
	if(o==Null) {o=new node,o->init(x);return;}
	int d=x<o->v?0:1;
	ins(o->c[d],x);
	if(o->c[d]->r<o->r) rot(o,!d);
	o->update();
}
void del(node *&o,int x){
	if(o->v==x){
		if(o->c[0]==Null) {o=o->c[1];return;}
		if(o->c[1]==Null) {o=o->c[0];return;}
		int d=o->c[0]->r<o->c[1]->r?1:0;
		rot(o,d),del(o->c[d],x);
	}
	else del(o->c[(o->v<x)],x);
	o->update();
}
int kth(int k){
	int now;
	node *o=root;
	while(o!=Null){
		now=o->c[0]->siz+1;
		if(now==k) return o->v;
		else if(now>k) o=o->c[0];
		else k-=now,o=o->c[1];
	}
}
int main(){
	freopen("arr.in","r",stdin);
	freopen("arr.out","w",stdout);
	srand(19990214);
	int n,m,op,x,y;
	in(n),in(m),root=Null;
	while(m--){
		while((op=getchar())<60);
		if(op=='i') in(x),ins(root,x);
		else in(x),printf("%d\n",y=kth(x)),del(root,y);
	}
}