这个题

刚学splay求条

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;

struct Splay{
	int rt,tot,cnt[N],si[N],ch[N][2],val[N],fa[N];
	
	void cl(int x){cnt[x]=si[x]=ch[x][0]=ch[x][1]=val[x]=fa[x]=0;}
	
	void ch_size(int x){si[x]=si[ch[x][0]]+si[ch[x][1]]+cnt[x];}
	
	int son(int x){return ch[fa[x]][1]==x;}
	
	void rotate(int x){
		int y=fa[x],z=fa[y],s=son(x);
		ch[y][s]=ch[x][s^1];
		if(ch[x][s^1]) fa[ch[x][s^1]]=y;
		ch[x][s^1]=y;
		if(z) ch[z][son(y)]=x;
		fa[y]=x,fa[x]=z;
		ch_size(y),ch_size(x);
	}
	
	void splay(int x){
		for(int i=fa[x];i;i=fa[x]){
			if(fa[i]) rotate(son(i)==son(x)?i:x);
			rotate(x);
		}rt=x;
	}
	
	void ins(int x){
		if(!rt){
			rt=++tot;
			si[rt]=1,cnt[rt]=1,val[rt]=x;
			return;
		}
		int cur=rt,f=0;
		while(1){
			if(val[cur]==x){
				si[x]++,cnt[x]++;
				ch_size(f);
				splay(cur);
				return;
			}
			f=cur,cur=ch[cur][x>val[cur]];
			if(!cur){
				++tot;
				si[tot]=1,cnt[tot]=1,val[tot]=x;
				fa[tot]=f,ch[f][x>val[f]]=tot;
				ch_size(f);
				splay(tot);
				return;
			}
		}
	}
	
	int rank(int x){
		int cur=rt,ans=0;
		while(1){
			if(x<val[cur]) cur=ch[cur][0];
			else{
				ans+=si[ch[cur][0]];
				if(!cur) return ans+1;
				if(x==val[cur]){splay(cur);return ans+1;}
				ans+=cnt[cur],cur=ch[cur][1];
			}
		}
		return -1;
	}
	
	int kth(int k){
		int cur=rt;
		while(1){
			if(ch[cur][0]&&k<=si[ch[cur][0]]) cur=ch[cur][0];
			else{
				k-=si[ch[cur][0]];
				if(k<=cnt[cur]){splay(cur);return val[cur];}
				k-=cnt[cur],cur=ch[cur][1];
			}
		}
		return -1;
	}
	
	int pre(){
		int cur=ch[rt][0];
		if(!cur) return 0;
		while(ch[cur][1]) cur=ch[cur][1];
		splay(cur);
		return cur;
	}
	
	int nex(){
		int cur=ch[rt][1];
		if(!cur) return 0;
		while(ch[cur][0]) cur=ch[cur][0];
		splay(cur);
		return cur;
	}
	
	void del(int x){
		rank(x);
		if(cnt[rt]>1){si[rt]--,cnt[rt]--;return;}
		if(!ch[rt][0]&&!ch[rt][1]){cl(rt),rt=0;return;}
		if(!ch[rt][0]){rt=ch[rt][1],cl(fa[rt]),fa[rt]=0;return;}
		if(!ch[rt][1]){rt=ch[rt][0],cl(fa[rt]),fa[rt]=0;return;}
		int bef=rt,p=pre();
		fa[ch[bef][1]]=p,ch[p][1]=ch[bef][1];
		cl(bef);
		ch_size(p);
	}
	
}t;

int n,op,x;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	while(n--){
		cin>>op>>x;
		if(op==1) t.ins(x);
		if(op==2) t.del(x);
		if(op==3) cout<<t.rank(x)<<"\n";
		if(op==4) cout<<t.kth(x)<<"\n";
		if(op==5) t.ins(x),cout<<t.val[t.pre()]<<"\n",t.del(x);
		if(op==6) t.ins(x),cout<<t.val[t.nex()]<<"\n",t.del(x);
	}
	return 0;
}