• P3369 【模板】普通平衡树

玄关

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int Q,root,tot,s[N][2],fa[N],cnt[N],Size[N],w[N];

void pushup(int u){
	if(u!=0)
		Size[u]=Size[s[u][0]]+Size[s[u][1]]+cnt[u];
}

void Rotate(int u){
	int k=s[fa[u]][1]==u,y=fa[u],z=fa[fa[u]];
	s[z][s[z][1]==y]=u,fa[u]=z;
	s[y][k]=s[u][k^1],fa[s[u][k^1]]=y;
	s[u][k^1]=y,fa[y]=u;
	pushup(y),pushup(u);
}

void splay(int u,int t){
	while(fa[u]!=t){
		int y=fa[u],z=fa[fa[u]];
		if(z!=t){
			if((s[y][1]==u)^(s[z][1]==y)) Rotate(u);
			else Rotate(y);
		}
		Rotate(u);
	}
	if(!t) root=u;
}

int Insert(int v){
	int u=root,Fa=0;
	while(u&&w[u]!=v) Fa=u,u=s[u][v>w[u]];
	if(u) cnt[u]++;
	else{
		u=++tot;
		if(Fa) s[Fa][v>w[Fa]]=u;
		w[u]=v,fa[u]=Fa,Size[u]=cnt[u]=1;
	}
	splay(u,0);
	return u;
}

void Find(int v){
	int u=root;
	if(!u) return ;
	while(s[u][v>w[u]]&&v!=w[u]) u=s[u][u>w[u]];
	splay(u,0);
}

int Head(int v){
	int u=root,ans=0;
	while(u)
		if(v>=w[u]) u=s[u][0];
		else{ans=u;u=s[u][1];}
	return ans;
}

int Tail(int x){
	int u=root,sum=0;
	while(u){
		if(w[u]<=x) u=s[u][1];
		else{sum=u;u=s[u][0];}
	}
	return sum;
}

void Delete(int v){
	int head=Head(v),tail=Tail(v);
	splay(head,0),splay(tail,head);
	int b=s[s[head][1]][0];
	if(cnt[b]>1) cnt[b]--,Size[b]--;
	else s[s[head][1]][0]=0,cnt[b]--,Size[b]--;
	pushup(s[head][1]),pushup(head);
}

int Rank(int v){
	Find(v);
	return Size[s[root][0]];
}

int Get(int k){
	int u=root;
	if(Size[u]<k) return -1;
	while(true)
		if(k>Size[s[u][0]]+cnt[u]){
			k-=Size[s[u][0]]+cnt[u];
			u=s[u][1];
		}
	else if(k<=Size[s[u][0]]) u=s[u][1];
	else return w[u];
}

int main(){
	scanf("%d",&Q);
	Insert(INT_MAX),Insert(INT_MIN);
	while(Q--){
		int opt,x;
		scanf("%d%d",&opt,&x);
		switch(opt){
			case 1:Insert(x);break;
			case 2:Delete(x);break;
			case 3:{
//				Insert(x);
				int ans=Rank(x);
				printf("%d\n",ans);
//				Delete(x);
				break;
			}
			case 4:{
				int ans=Get(x+1);
				printf("%d\n",ans);
				break;
			}
			case 5:{
//				Insert(x);
				int ans=Head(x);
				printf("%d\n",ans);
//				Delete(x);
				splay(ans,0);
				break;
			}
			case 6:{
//				Insert(x);
				int ans=Head(x);
				printf("%d\n",ans);
//				Delete(x);
				splay(ans,0);
				break;
			}
		}
	}
	return 0;
}