蒟蒻刚学Splay 1ms,被猎奇bug霸凌

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const long long inf = 1e18;
const long long mod = 1e9;
const long long N = 5e5 + 5;
int n , m;
struct node{
	int l , r;
	int val , cnt;
	int size;
	int fa;
}a[N];
int root = 1 , cnt = 0;
bool is_rson(int x , int y){return a[y].r == x;}
void rotate(int x)
{
	if(!a[x].fa)return ;
	if(is_rson(x , a[x].fa))
	{
		a[a[x].fa].r = a[x].l , a[a[x].l].fa = a[x].fa , a[x].l = a[x].fa;
		if(is_rson(a[x].fa , a[a[x].fa].fa))a[a[a[x].fa].fa].r = x;
		else a[a[a[x].fa].fa].l = x;
		a[x].fa = a[a[x].fa].fa;
		a[a[x].l].fa = x;
		
		a[a[x].l].size = a[a[a[x].l].l].size + a[a[a[x].l].r].size + a[a[x].l].cnt;
		a[x].size = a[a[x].l].size + a[a[x].r].size + a[x].cnt;
	}
	else
	{
		a[a[x].fa].l = a[x].r , a[a[x].r].fa = a[x].fa , a[x].r = a[x].fa;
		if(is_rson(a[x].fa , a[a[x].fa].fa))a[a[a[x].fa].fa].r = x;
		else a[a[a[x].fa].fa].l = x;
		a[x].fa = a[a[x].fa].fa;
		a[a[x].r].fa = x;
		
		a[a[x].r].size = a[a[a[x].r].l].size + a[a[a[x].r].r].size + a[a[x].r].cnt;
		a[x].size = a[a[x].l].size + a[a[x].r].size + a[x].cnt;
	}
	if(!a[x].fa)root = x;
	return ;
}

void splay(int x)
{
	if(!a[a[x].fa].fa)
	{
		rotate(x);
		return ;
	}
	if(!(is_rson(x , a[x].fa) ^ is_rson(a[x].fa , a[a[x].fa].fa)))rotate(a[x].fa) , rotate(x);
	else rotate(x) , rotate(x);
	return ;
}
void splay_to_root(int x){while(a[x].fa)splay(x);}
void add(int x)
{
	if(cnt == 0)
	{
		cnt = 1;
		a[cnt].val = x;
		a[cnt].size = a[cnt].cnt = 1;
		return ;
	}
	int y = root;
	while(1)
	{
		a[y].size++;
		if(a[y].val == x)
		{
			a[y].cnt++;
			splay_to_root(y);
			return ;
		}
		if(a[y].val < x)
		{
			if(a[y].r)y = a[y].r;
			else
			{
				a[y].r = ++cnt;
				a[cnt].val = x;
				a[cnt].size = a[cnt].cnt = 1;
				a[cnt].fa = y;
				splay_to_root(cnt);
				return ;
			}
		}
		else
		{
			if(a[y].l)y = a[y].l;
			else
			{
				a[y].l = ++cnt;
				a[cnt].val = x;
				a[cnt].size = a[cnt].cnt = 1;
				a[cnt].fa = y;
				splay_to_root(cnt);
				return ;
			}
		}
	}
	return ;
}
int get_maxn(int y)
{
	while(a[y].r)y = a[y].r;
	return y;
}
void del(int x)
{
	int y = root;
	while(1)
	{
		a[y].size--;
		if(a[y].val == x)
		{
			a[y].cnt--;
			if(a[y].cnt == 0)
			{
				if(a[y].l == 0 && a[y].r == 0)
				{
					if(is_rson(y , a[y].fa))a[a[y].fa].r = 0 , a[y].fa = 0;
					else a[a[y].fa].l = 0 , a[y].fa = 0;
					return ;
				}
				else if(a[y].l == 0|| a[y].r == 0)
				{
					if(a[y].l == 0)
					{
						a[a[y].r].fa = a[y].fa;
						if(is_rson(y , a[y].fa))a[a[y].fa].r = a[y].r;
						else a[a[y].fa].l = a[y].r;
						a[y].l = a[y].r = a[y].fa = 0;
					}
					else
					{
						a[a[y].l].fa = a[y].fa;
						if(is_rson(y , a[y].fa))a[a[y].fa].r = a[y].l;
						else a[a[y].fa].l = a[y].l;
						a[y].l = a[y].r = a[y].fa = 0;
					}
				}
				else
				{
					int z = get_maxn(y);
					while(a[z].fa != y && a[a[z].fa].fa != y)splay(z);
					if(a[z].fa == z)rotate(z);
					else splay(z);
					
					a[a[y].l].fa = z , a[z].l = a[y].l;
					a[y].l = a[y].r = a[y].fa = 0;
				}
			}
			return ;
		}
		if(a[y].val < x)
		{
			if(a[y].r)y = a[y].r;
			else break;
		}
		else
		{
			if(a[y].l)y = a[y].l;
			else break;
		}
	}
	return ;
}

int get_rank(int x)
{
	int y = root , sum = 0;
	while(1)
	{
		if(a[y].val == x)return sum + a[a[y].l].size + 1;
//		cerr<<a[y].val<<' '<<a[y].size<<':'<<a[a[y].l].val<<' '<<a[a[y].l].size<<':'<<a[a[y].r].val<<' '<<a[a[y].r].size<<endl;
		if(a[y].val < x)
		{
			sum += a[a[y].l].size + a[y].cnt;
			if(a[y].r)y = a[y].r;
			else return sum + 1;
		}
		else
		{
			if(a[y].l)y = a[y].l;
			else return sum + 1;
		}
	}
	return sum + 1;
}

int get_by_rank(int x)
{
	int y = root;
	while(1)
	{
		if(a[a[y].l].size < x)x -= a[a[y].l].size;
		else
		{
			if(a[y].l)y = a[y].l;
			else break;
			continue;
		}
		
		if(x <= a[y].cnt)return a[y].val;
		x -= a[y].cnt;
		if(a[y].r)y = a[y].r;
		else break;
	}
	return a[y].val;
}

int get_smaller(int x)
{
	int y = root , maxn = -inf;
	while(1)
	{
//		cerr<<a[y].val<<' '<<a[y].size<<':'<<a[a[y].l].val<<' '<<a[a[y].l].size<<':'<<a[a[y].r].val<<' '<<a[a[y].r].size<<endl;
		if(a[y].val < x)
		{
			if(a[y].val != x)maxn = max(maxn , a[y].val);
			if(a[y].r)y = a[y].r;
			else return maxn;
		}
		else
		{
			if(a[y].l)y = a[y].l;
			else return maxn;
		}
	}
	return maxn;
}

int get_bigger(int x)
{
	int y = root , minn = inf;
	while(1)
	{
		if(x < a[y].val)
		{
			if(a[y].val != x)minn = min(a[y].val , minn);
			if(a[y].l)y = a[y].l;
			else return minn;
		}
		else
		{
			if(a[y].r)y = a[y].r;
			else return minn;
		}
	}
}
signed main()
{
//	freopen("ce.in" , "r" , stdin);
//	freopen("ce.out" , "w" , stdout);
	cin.tie(0) , cout.tie(0);
	ios::sync_with_stdio(0);
	cin>>n;
	int op , x;
	for(int i = 1 ; i <= n ; i++)
	{
		cin>>op>>x;
		if(op == 1)add(x);
		else if(op == 2)del(x);
		else if(op == 3)cout<<get_rank(x)<<endl;
		else if(op == 4)cout<<get_by_rank(x)<<endl;
		else if(op == 5)cout<<get_smaller(x)<<endl;
		else cout<<get_bigger(x)<<endl;
		
	}
	return 0;
}