如题

#include<bits/stdc++.h>
using namespace std;
struct SplayNode{
	int value,size,cnt=0;
	SplayNode* father=nullptr;
	SplayNode* kids[2];
	bool judge(){
		return father->kids[1]==this;
	}
	void pushup(){
		size=cnt+kids[0]->size+kids[1]->size;
	}
	SplayNode(){
		tie(value,size,father,kids[0],kids[1])=make_tuple(0,0,this,this,this);
	}
	SplayNode(int v,SplayNode* NIL){
		tie(value,size,father,cnt,kids[0],kids[1])=make_tuple(v,1,NIL,1,NIL,NIL);
	}
};
SplayNode* NIL=new SplayNode;
struct Splay{
	void insert(int x){
		if(root==NIL){
			root=new SplayNode{x,NIL};
			return;
		}
		SplayNode* father=root;
		SplayNode* n=root;
		while(n!=NIL){
			father=n;
			if(x==n->value){
				n->cnt+=1;
				splay(n);
				return;
			}
			if(x<n->value){
				n=n->kids[0];
			}else{
				n=n->kids[1];
			}
		}
		n=new SplayNode{x,NIL};
		connect(father,n,x>father->value);
		splay(n);
	}
	void remove(int x){
		SplayNode* n=find(x);
		if(n->cnt>1){
			n->cnt-=1;
			n->size-=1;
			splay(n);
			return;
		}
		if(n!=NIL){
			root=n->kids[0];
			n->kids[0]->father=NIL;
			n->kids[1]->father=NIL;
			merge(n->kids[1]);
			delete n;
		}
	}
	int rank(int x){
		return find(x)->kids[0]->size+1;
	}
	int kth(int k){
		SplayNode* n=root;
		while(n!=NIL){
			if(k<=n->kids[0]->size){
				n=n->kids[0];
			}else if(k==n->kids[0]->size+1){
				return n->value;
			}else{
				k-=n->kids[0]->size+1;
				n=n->kids[1];
			}
		}
		return 2147483647;
	}
	int prev(int x){
		SplayNode* n=root;
		int ans=0;
		while(n!=NIL){
			if(n->value<x){
				ans=n->value;
				n=n->kids[1];
			}else{
				n=n->kids[0];
			}
		}
		return ans;
	}
	int next(int x){
		SplayNode* n=root;
		int ans=0;
		while(n!=NIL){
			if(n->value>x){
				ans=n->value;
				n=n->kids[0];
			}else{
				n=n->kids[1];
			}
		}
		return ans;
	}
private:
	SplayNode* root=NIL;
	void merge(SplayNode* R){
 		if(R==NIL){
 			return;
 		}
        if(root==NIL){
            root=R;
            return;
        }
		SplayNode* n=root;
		while(n->kids[1]!=NIL){
			n=n->kids[1];
		}
		splay(n);
		connect(n,R,1);
	}
	SplayNode* find(int x){
		SplayNode* rt=root;
		while(rt!=NIL){
			if(rt->value==x){
				break;
			}else{
				rt=rt->kids[x<rt->value?0:1];
			}
		}
		if(rt!=NIL){
			splay(rt);
		}
		return rt;
	}
	void splay(SplayNode* n,SplayNode* target=NIL){
		while(n->father!=target){
			if(n->father->father!=target){
				if(n->judge()==n->father->judge()){
					rotate(n->father);
				}else{
					rotate(n);
				}
			}
			rotate(n);
		}
		n->pushup();
		if(target==NIL){
			root=n;
		}
	}
	void rotate(SplayNode* n){
		SplayNode* father=n->father;
		SplayNode* grandpa=father->father;
		int direction=n->judge()?1:0;
		connect(grandpa,n,father->judge());
		connect(father,n->kids[direction^1],direction);
		connect(n,father,direction^1);
		father->pushup();
		n->pushup();
	}
	void connect(SplayNode* a,SplayNode* b,int direction){
		if(a!=NIL){
			a->kids[direction]=b;
		}
		if(b!=NIL){
			b->father=a;
		}
	}
};
int main(){
//	freopen("2333.txt","w",stderr);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	Splay splay;
	int N;
	cin>>N;
	while(N--){
		int op,x;
		cin>>op>>x;
		if(NIL->kids[1]!=NIL||NIL->kids[0]!=NIL||NIL->father!=NIL){
			throw -1;
		}
		if(op==1){
			splay.insert(x);
		}else if(op==2){
			splay.remove(x);
		}else if(op==3){
			cout<<splay.rank(x)<<"\n";
		}else if(op==4){
			cout<<splay.kth(x)<<"\n";
		}else if(op==5){
			cout<<splay.prev(x)<<"\n";
		}else{
			cout<<splay.next(x)<<"\n";
		}
	}
}