记录编号	457077	评测结果	AAAAAAAAAA
题目名称	[SDOI 2007] 超级数组	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.388 s
提交时间	2017-10-06 17:50:36	内存使用	0.34 MiB

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<ctime>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum;
}
#define get_size(x) (x?x->size:0)
struct node{
	node *lch,*rch;
	int size,key,fix;
	node(int x=0):lch(NULL),rch(NULL),size(1),key(x),fix(rand()){}
	inline void pushup(){
		this->size=get_size(this->lch)+get_size(this->rch)+1;
	}
}*root;
inline void left_rotate(node *&x){
	node *tmp(x->rch);
	x->rch=tmp->lch;
	tmp->lch=x;
	x->pushup();
	tmp->pushup();
	x=tmp;
}
inline void right_rotate(node *&x){
	node *tmp(x->lch);
	x->lch=tmp->rch;
	tmp->rch=x;
	x->pushup();
	tmp->pushup();
	x=tmp;
}
inline void insert(node *&x,int v){
	if(!x){
		x=new node(v);
		return;
	}
	if(v<=x->key){
		insert(x->lch,v);
		x->pushup();
		if(x->lch->fix<x->fix)
			right_rotate(x);
	}
	else{
		insert(x->rch,v);
		x->pushup();
		if(x->rch->fix<x->fix)
			left_rotate(x);
	}
}
inline void del(node *&x,int v){
	if(x->key==v){
		if(x->lch&&x->rch){
			if(x->lch->fix<x->rch->fix){
				right_rotate(x);
				del(x->rch,v);
			}
			else{
				left_rotate(x);
				del(x->lch,v);
			}
		}
		else{
			node *tmp(NULL);
			if(x->lch)
				tmp=x->lch;
			else
				tmp=x->rch;
			delete x;
			x=tmp;
		}
	}
	else{
		if(v<=x->key)
			del(x->lch,v);
		else
			del(x->rch,v);
	}
	if(x)
		x->pushup();
}
inline int kth(int k){
	node *now(root);
	while(now){
		if(get_size(now->lch)+1==k)
			return now->key;
		if(get_size(now->lch)+1>=k)
			now=now->lch;
		else
			k-=get_size(now->lch)+1,now=now->rch;
	}
}
int n,m;
char op[2];
inline int gg(){
	freopen("arr.in","r",stdin);
	freopen("arr.out","w",stdout);
	srand(time(NULL));
	n=read(),m=read();
	while(m--){
		scanf("%s",op);
		if(op[0]=='i'){
			int x(read());
			insert(root,x);
		}
		else{
			int x(read());
			int ans(kth(x));
			printf("%d\n",ans);
			del(root,ans);
		}
	}
	return 0;
}
int K(gg());
int main(){;}