code

#include<bits/stdc++.h>
using namespace std;
int tot,del,rt;
struct node
{
	int lc,rc,v,siz;
	node(){lc=rc=siz=0;}
	node(const int x){lc=rc=0;v=x;siz=1;}
}a[1000001];
void upt(int x){a[x].siz=a[a[x].lc].siz+a[a[x].rc].siz+1;}
void lx(int& x)
{
	int k=a[x].rc;
	a[x].rc=a[k].lc;
	a[k].lc=x;
	a[k].siz=a[x].siz;
	upt(x);
	x=k;
}
void rx(int& x)
{
	int k=a[x].lc;
	a[x].lc=a[k].rc;
	a[k].rc=x;
	a[k].siz=a[x].siz;
	upt(x);
	x=k;
}
void maintain(int& x,bool flag)
{
	if(!flag)
		if(a[a[a[x].lc].lc].siz>a[a[x].rc].siz)rx(x);
		else if(a[a[a[x].lc].rc].siz>a[a[x].rc].siz)lx(a[x].lc),rx(x);
		else return;
	else
		if(a[a[a[x].rc].rc].siz>a[a[x].lc].siz)lx(x);
		else if(a[a[a[x].rc].lc].siz>a[a[x].lc].siz)rx(a[x].rc),lx(x);
		else return;
	maintain(a[x].lc,0);
	maintain(a[x].rc,1);
	maintain(x,1);
	maintain(x,0);
}
void insert(const int v,int &x=rt)
{
	if(!x)x=++tot,a[x]=v;
	else if(v<=a[x].v)insert(v,a[x].lc);
	else if(v>a[x].v)insert(v,a[x].rc);
	upt(x);
	maintain(x,v>a[x].v);
}
int erase(const int v,int &x=rt)
{
	if(v==a[x].v||(v<a[x].v&&!a[x].lc)||(v>a[x].v&&!a[x].rc))
	{
		del=v;
		if(!a[x].lc||!a[x].rc)x=a[x].lc+a[x].rc;
		else a[x].v=erase(v+1,a[x].lc);
		return del;
	}
	if(v<a[x].v)erase(v,a[x].lc);
	else erase(v,a[x].rc);
}
int rak(const int v)
{
	int x=rt,res=1;
	while(x)
	{
		if(v==a[x].v)return res+a[a[x].lc].siz;
		if(v<a[x].v)x=a[x].lc;
		else res+=a[a[x].lc].siz+1,x=a[x].rc;
	}
	return res;
}
int kth(int k)
{
	int x=rt;
	while(x)
	{
		if(a[a[x].lc].siz<k&&a[a[x].lc].siz+1>=k)return a[x].v;
		if(a[a[x].lc].siz>=k)x=a[x].lc;
		else k-=a[a[x].lc].siz+1,x=a[x].rc;
	}
	return 0;
}
int prv(const int v)
{
	int x=rt,res=0;
	while(x)
		if(a[x].v<v)res=a[x].v,x=a[x].rc;
		else x=a[x].lc;
	return res;
}
int nxt(const int v)
{
	int x=rt,res=0;
	while(x)
	{
		if(a[x].v>v)res=a[x].v,x=a[x].lc;
		else x=a[x].rc;
	}
	return res;
}
int main()
{
	int T,x,y;
	cin>>T;
	while(T--)
	{
		scanf("%d%d",&x,&y);
		if(x==1)insert(y);
		if(x==2)erase(y);
		if(x==3)printf("%d\n",rak(y));
		if(x==4)printf("%d\n",kth(y));
		if(x==5)printf("%d\n",prv(y));
		if(x==6)printf("%d\n",nxt(y));
	}
	return 0;
}

写的 SBT，但是RE了。