文件详细信息

下载本文件

本文件的大小为 3762 字节。

#include<cstdio>
namespace IO{
	const int ARR_SIZE=1<<20;
	#define gc() ((IO::si!=IO::ti||(IO::ti=(IO::si=IO::input)+fread(IO::input,1,IO::ARR_SIZE,stdin))),IO::si!=IO::ti?*(IO::si++):EOF)
	#define pc(ch) ((IO::o.so!=IO::o.to||(fwrite(IO::o.output,1,IO::ARR_SIZE,stdout),IO::o.so=IO::o.output)),*(IO::o.so++)=ch)
	char input[ARR_SIZE],*si=input,*ti=input;
	struct Output_Stream{
		char output[ARR_SIZE],*so=output,*to=output+ARR_SIZE;
		~Output_Stream(){
			if(so==output)return;
			fwrite(output,1,so-output,stdout);
			so=output;
		}
	}o;
	template<typename T>
	void read(T&num){
		bool flag=true;
		int ch=gc();
		num=0;
		while(ch<48||ch>57){
			if(ch=='-')flag=false;
			ch=gc();
		}
		while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=gc();
		flag||(num=-num);
	}
	template<typename T>
	void write(T a){
		static int ch[50],cnt=0;
		if(a<0)pc('-'),a=-a;
		if(a==0)pc('0');
		while(a)ch[++cnt]=a%10|48,a/=10;
		while(cnt)pc(ch[cnt--]);
	}
}
using IO::read;
using IO::write;
const int maxn=100000;
struct Node{
	Node*fa,*ch[2];
	int val,cnt,size;
};
struct MemoryPool{
	Node T[maxn+1];
	int tot;
	void clear(Node*u){
		u->fa=u->ch[0]=u->ch[1]=T;
		u->val=u->cnt=u->size=0;
	}
	void newnode(Node*&u){
		u=T+(++tot);
		clear(u);
	}
}P;
struct Splay{
	Node*rt=P.T;
	void maintain(Node*u){
		u->size=u->ch[0]->size+u->ch[1]->size+u->cnt;
	}
	int get(Node*u){
		return u==u->fa->ch[1];
	}
	void rotate(Node*x){
		Node*y=x->fa,*z=y->fa;
		const int k=get(x);
		y->ch[k]=x->ch[k^1];
		if(y->ch[k]!=P.T)y->ch[k]->fa=y;
		x->ch[k^1]=y;
		y->fa=x;
		x->fa=z;
		if(z!=P.T)z->ch[y==z->ch[1]]=x;
		maintain(y);
		maintain(x);
	}
	void splay(Node*x,const Node*target){
		for(Node*f;f=x->fa,f!=target;rotate(x))
			if(f->fa!=target)
				rotate(get(f)==get(x)?f:x);
		if(target==P.T)rt=x;
	}
	void insert(const int k){
		if(rt==P.T){
			P.newnode(rt);
			rt->val=k;
			rt->cnt=1;
			maintain(rt);
			return;
		}
		Node*u=rt,*f=P.T;
		while(true){
			if(u->val==k){
				u->cnt++;
				maintain(u);
				maintain(f);
				splay(u,P.T);
				return;
			}
			f=u,u=u->ch[k>u->val];
			if(u==P.T){
				P.newnode(u);
				u->fa=f;
				f->ch[k>f->val]=u;
				u->val=k;
				u->cnt=1;
				maintain(u);
				maintain(f);
				splay(u,P.T);
				return;
			}
		}
	}
	int rank(const int k){
		Node*u=rt,*f=P.T;
		int ans=1;
		while(true){
			if(u==P.T){
				splay(f,P.T);
				return ans;
			}
			f=u;
			if(k<u->val)u=u->ch[0];
			else{
				ans+=u->ch[0]->size;
				if(k==u->val){
					splay(u,P.T);
					return ans;
				}
				ans+=u->cnt;
				u=u->ch[1];
			}
		}
	}
	Node*kth(int k){
		Node*u=rt;
		while(true){
			if(k<=u->ch[0]->size)u=u->ch[0];
			else{
				k-=u->ch[0]->size+u->cnt;
				if(k<=0){
					splay(u,P.T);
					return u;
				}
				u=u->ch[1];
			}
		}
	}
	Node*pre(){
		Node*u=rt->ch[0];
		while(u->ch[1]!=P.T)u=u->ch[1];
		splay(u,P.T);
		return u;
	}
	Node*next(){
		Node*u=rt->ch[1];
		while(u->ch[0]!=P.T)u=u->ch[0];
		splay(u,P.T);
		return u;
	}
	void del(int k){
		rank(k);
		if(rt->cnt>1){
			rt->cnt--;
			maintain(rt);
		}else if(rt->ch[0]==P.T&&rt->ch[1]==P.T){
			P.clear(rt);
			rt=P.T;
		}else if(rt->ch[0]==P.T){
			Node*u=rt;
			rt=u->ch[1];
			rt->fa=P.T;
			P.clear(u);
		}else if(rt->ch[1]==P.T){
			Node*u=rt;
			rt=u->ch[0];
			rt->fa=P.T;
			P.clear(u);
		}else{
			Node*u=rt,*x=pre();
			u->ch[1]->fa=x;
			x->ch[1]=u->ch[1];
			P.clear(u);
			maintain(rt);
		}
	}
}T;
int n;
int main(){
	P.clear(T.rt);
	read(n);
	for(int i=1,opt,x;i<=n;i++){
		read(opt),read(x);
		if(opt==1)T.insert(x);
		else if(opt==2)T.del(x);
		else if(opt==3)write(T.rank(x)),pc('\n');
		else if(opt==4)write(T.kth(x)->val),pc('\n');
		else if(opt==5)T.insert(x),write(T.pre()->val),pc('\n'),T.del(x);
		else T.insert(x),write(T.next()->val),pc('\n'),T.del(x);
	}
	return 0;
}