记录编号	358292	评测结果	AAAAAAAAAA
题目名称	[SDOI 2007] 超级数组	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.478 s
提交时间	2016-12-15 15:25:36	内存使用	1.85 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=100000+500;
#define LL long long
#define Inf 2e9
#define Begin freopen("arr.in","r",stdin);freopen("arr.out","w",stdout);
int ls[maxn],rs[maxn],size[maxn],v[maxn],RT,cnt;
void Init();
void pushup(int rt){size[rt]=size[ls[rt]]+size[rs[rt]]+1;}
void Turn_right(int & rt){
	int t=ls[rt];
	ls[rt]=rs[t];pushup(rt);
	rs[t]=rt;pushup(t);
	rt=t;
}
void Turn_left(int & rt){
	int t=rs[rt];
	rs[rt]=ls[t];pushup(rt);
	ls[t]=rt;pushup(t);
	rt=t;
}
#define Balance_all Balance(rt);Balance(ls[rt]);Balance(rs[rt]);
void Balance(int & rt){
	if(size[ls[ls[rt]]]>size[rs[rt]]){
		Turn_right(rt);Balance_all;return;
	}
	if(size[rs[rs[rt]]]>size[ls[rt]]){
		Turn_left(rt);Balance_all;return;
	}
	if(size[rs[ls[rt]]]>size[rs[rt]]){
		Turn_left(ls[rt]);Turn_right(rt);Balance_all;return;
	}
	if(size[ls[rs[rt]]]>size[ls[rt]]){
		Turn_right(rs[rt]);Turn_left(rt);Balance_all;return;
	}
}
#undef Balance_all
void Insert(int & rt,int date){
	if(rt==0){
		rt=++cnt;size[rt]=1;v[rt]=date;return;
	}
	if(date<v[rt])Insert(ls[rt],date);
	else Insert(rs[rt],date);
	pushup(rt);Balance(rt);
}
void Del(int & rt,int date){
	if(v[rt]==date){
		if(ls[rt]==0 && rs[rt]==0){rt=0;return;}
		if(ls[rt]==0){rt=rs[rt];return;}
		if(rs[rt]==0){rt=ls[rt];return;}
		Turn_right(rt);Del(rs[rt],date);
		pushup(rt);return;
	}
	if(date<v[rt])Del(ls[rt],date);
	else Del(rs[rt],date);
	pushup(rt);Balance(rt);
}
int Get_date(int rt,int th){
	if(size[ls[rt]]+1==th)return v[rt];
	if(size[ls[rt]]+1>th)return Get_date(ls[rt],th);
	else return Get_date(rs[rt],th-size[ls[rt]]-1);
}
int main(){
	Begin;
	Init();
	getchar();getchar();
	return 0;
}
void Init(){
	int n;scanf("%d",&n);scanf("%d",&n);
	for(int i=1;i<=n;i++){
		char type;int date;scanf(" %c%d",&type,&date);
		if(type=='i')Insert(RT,date);
		else {
			int x=Get_date(RT,date);
			Del(RT,x);
			printf("%d\n",x);
		}
	}
}