文件详细信息

下载本文件

本文件的大小为 2884 字节。

#include<cstdio>
#define maxn 100005
int n,root,total,fa[maxn],child[maxn][2],value[maxn],count[maxn],size[maxn];
inline int read(){
	int ch=getchar(),num=0;
	while(ch<48||ch>57)ch=getchar();
	while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
	return num;
}
inline void maintain(int a){
	size[a]=size[child[a][0]]+size[child[a][1]]+count[a];
}
inline bool get(int a){
	return a==child[fa[a]][1]; 
}
inline void clear(int a){
	fa[a]=child[a][0]=child[a][1]=value[a]=count[a]=size[a]=0;
}
inline void rotate(int a){
	bool check=get(a);
	int b=fa[a],c=fa[b];
	child[b][check]=child[a][!check];
	fa[child[a][!check]]=b;
	child[a][!check]=b;
	fa[b]=a;
	fa[a]=c;
	if(c)child[c][b==child[c][1]]=a;
	maintain(b);
	maintain(a);
}
inline void splay(int a){
	for(int i=fa[a];i=fa[a],i;rotate(a))
		if(fa[i])
			rotate(get(a)==get(i)?i:a);
	root=a;
}
inline void ins(int k){
	if(!root){
		value[++total]=k;
		count[total]++;
		root=total;
		maintain(root);
		return;
	}
	int cnr=root,f=0;
	while(true){
		if(value[cnr]==k){
			count[cnr]++;
			maintain(cnr);
			maintain(f);
			splay(cnr);
			return;
		}
		f=cnr;
		cnr=child[cnr][value[cnr]<k];
		if(!cnr){
			value[++total]=k;
			count[total]++;
			fa[total]=f;
			child[f][value[f]<k]=total;
			maintain(total);
			maintain(f);
			splay(total);
			return;
		}
	}
}
inline int rank(int k){
	int res=0,cnr=root;
	while(true){
		if(k<value[cnr])cnr=child[cnr][0];
		else{
			res+=size[child[cnr][0]];
			if(k==value[cnr]){
				splay(cnr);
				return res+1;
			}
			res+=count[cnr];
			cnr=child[cnr][1];
		}
	}
}
inline int kth(int k){
	int cnr=root;
	while(true){
		if(child[cnr][0]&&k<=size[child[cnr][0]])cnr=child[cnr][0];
		else{
			k-=count[cnr]+size[child[cnr][0]];
			if(k<=0){
				splay(cnr);
				return value[cnr];
			}
			cnr=child[cnr][1];
		}
	}
}
inline int pre(){
	int cnr=child[root][0];
	while(child[cnr][1])cnr=child[cnr][1];
	splay(cnr);
	return cnr;
}
inline int next(){
	int cnr=child[root][1];
	while(child[cnr][0])cnr=child[cnr][0];
	splay(cnr);
	return cnr;
}
inline void del(int k){
	rank(k);
	if(count[root]>1){
		count[root]--;
		maintain(root);
		return;
	}
	if(!child[root][0]&&!child[root][1]){
		clear(root);
		root=0;
		return;
	}
	if(!child[root][0]){
		int cnr=root;
		root=child[root][1];
		fa[root]=0;
		clear(cnr);
		return;
	}
	if(!child[root][1]){
		int cnr=root;
		root=child[root][0];
		fa[root]=0;
		clear(cnr);
		return;
	}
	int cnr=root;
	int x=pre();
	splay(x);
	fa[child[cnr][1]]=x;
	child[x][1]=child[cnr][1];
	clear(cnr);
	maintain(root);
}
int main(){
	scanf("%i",&n);
	int opt,x;
	for(int i=1;i<=n;i++){
		scanf("%i%i",&opt,&x);
		if(opt==1)ins(x);
		else if(opt==2)del(x);
		else if(opt==3)printf("%i\n",rank(x));
		else if(opt==4)printf("%i\n",kth(x));
		else if(opt==5)ins(x),printf("%i\n",value[pre()]),del(x);
		else ins(x),printf("%i\n",value[next()]),del(x);
	}
	return 0;
}