RT,数据

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5+10;
const int inf = 1e9;
int siz[maxn],v[maxn],num[maxn],rd[maxn],son[maxn][2],cnt;
void pushup(int n){siz[n] = siz[son[n][0]] + siz[son[n][1]] + num[n]; return ;}
void rotate(int &n,int d)//d=0 left
//左旋增长左边，右旋增长右边 
{
	int tmp = son[n][d^1];
	son[n][d^1] = son[tmp][d];
	son[tmp][d] = n;
	pushup(n); pushup(tmp);
	n = tmp;
	return ;
}
void ins(int &n,int numm)
{
	if(!n)
	{
		siz[++cnt] = num[cnt] = 1;
		v[cnt] = numm; rd[cnt] = rand();
		n = cnt;
		return ;
	}
	if(v[n] == numm) { siz[n]++; num[n]++; return ; }
	int d = (numm>v[n]);
	ins(son[n][d],numm);
	if(rd[n] < rd[son[n][d]]) rotate(n,d^1);
	pushup(n);
	return ;
}
void del(int &n,int numm)
{
	if(!n) return ;
	if(v[n] != numm) { del(son[n][(numm>v[n])],numm); pushup(n); return ;}
	if(!son[n][0] && !son[n][1]) 
	{ 
		num[n]--; siz[n]--; 
		if(num[n] == 0) n=0;
	}
	if(son[n][0] && !son[n][1])
	{
		rotate(n,1);
		del(son[n][1],numm); 
	}
	if(!son[n][0] && son[n][1])
	{
		rotate(n,0);
		del(son[n][0],numm);
	}
	if(son[n][0] && son[n][1])
	{
		int d = (rd[son[n][0]] > rd[son[n][1]]);
		rotate(n,d);
		del(son[n][d],numm);
	}
	pushup(n); 
	return ;
}
int Rank(int n,int numm)
{
//	cout<<"               "<<siz[n]<<endl;
	if(!n) return 0;
	if(v[n] == numm) return siz[son[n][0]] + 1;
	if(v[n] > numm) return Rank(son[n][0],numm);
	if(v[n] < numm) return siz[son[n][0]] + num[n] + Rank(son[n][1],numm);
}
int ffind(int n,int numm)
{
	if(!n) return 0;
	if(siz[son[n][0]] >= numm) return ffind(son[n][0],numm);
	else if(siz[son[n][0]] + num[n] < numm) return ffind(son[n][1],numm - siz[son[n][0]] - num[n]);
	else return v[n];
}
int pre(int n,int numm)
{
	if(!n) return -inf;
	if(v[n] >= numm) return pre(son[n][0],numm);
	return max(v[n],pre(son[n][1],numm));
}
int suc(int n,int numm)
{
//	cout<<numm<<' '<<v[n]<<endl;
	if(!n) return inf;
	if(v[n] <= numm) return suc(son[n][1],numm);
	return min(v[n],suc(son[n][0],numm));
}
signed main() 
{
	freopen("P3369_5.in","r",stdin);
	int n,opt,x,rt=0;
	cin>>n;
	ins(rt,-INT_MAX); ins(rt,INT_MAX);
	while(n--)
	{
		cin>>opt>>x;
		if(opt == 1) ins(rt,x);
		if(opt == 2) del(rt,x);
		if(opt == 3) { ins(rt,x); cout<<Rank(rt,x)-1<<endl; del(rt,x);}
		if(opt == 4) cout<<ffind(rt,x+1)<<endl;
		if(opt == 5) { ins(rt,x); cout<<pre(rt,x)<<endl; del(rt,x);}
		if(opt == 6) { ins(rt,x); cout<<suc(rt,x)<<endl; del(rt,x);}
	}
	return 0;
}