萌新平衡树求救QwQ（模板）

//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
const int N=1000005;
struct tree{
    int lc,rc,siz,val,fa,cnt;
} tr[N];
int tl=1,rt;
void rotate(int now)
{
    int grfa=tr[tr[now].fa].fa,k;
    if(now==tr[tr[now].fa].lc)
    {
        if(tr[grfa].lc==tr[now].fa)
        {
            tr[grfa].lc=now;
            k=tr[now].rc;
            tr[now].rc=tr[now].fa;
            tr[tr[now].fa].lc=k;
            tr[k].fa=tr[now].fa;
        }
        else
        {
            tr[grfa].rc=now;
            k=tr[now].rc;
            tr[now].rc=tr[now].fa;
            tr[tr[now].fa].lc=k;
            tr[k].fa=tr[now].fa;
        }
    }
    else
    {
        if(tr[grfa].lc==tr[now].fa)
        {
            tr[grfa].lc=now;
            k=tr[now].lc;
            tr[now].lc=tr[now].fa;
            tr[tr[now].fa].rc=k;
            tr[k].fa=tr[now].fa;
        }
        else
        {
            tr[grfa].rc=now;
            k=tr[now].lc;
            tr[now].lc=tr[now].fa;
            tr[tr[now].fa].rc=k;
            tr[k].fa=tr[now].fa;
        }
    }
    k=tr[now].fa;
    tr[k].fa=now;
    tr[now].fa=grfa;
    tr[k].siz=tr[tr[k].lc].siz+tr[tr[k].rc].siz+1;
    tr[now].siz=tr[tr[now].lc].siz+tr[tr[now].rc].siz+1;
}
void splay(int now,int aim)
{
    while(tr[now].fa!=aim)
    {
        if(tr[tr[now].fa].fa==aim) rotate(now);
        else if((tr[tr[now].fa].lc==now&&tr[tr[tr[now].fa].fa].lc==tr[now].fa)||(tr[tr[now].fa].rc==now&&tr[tr[tr[now].fa].fa].rc==tr[now].fa))
        {
            rotate(tr[now].fa);
            rotate(now);
        }
        else
        {
            rotate(now);
            rotate(now);
        }
    }
    if(aim==0) rt=now;
}
void add(int now,int x,int fa)
{
    if(tr[now].cnt==0)
    {
        tr[now].cnt=1;
        tr[now].fa=fa;
        tr[now].siz=1;
        tr[now].val=x;
        tr[now].lc=++tl;
        tr[now].rc=++tl;
        splay(now,0);
        return;
    }
    if(tr[now].val==x)
    {
        tr[now].cnt++;
        return;
    }
    if(x>tr[now].val) add(tr[now].rc,x,now);
    else add(tr[now].lc,x,now);
}
int pos;
void zhao(int now,int x)
{
    if(tr[now].val==x)
    {
        pos=now;
        return;
    }
    if(x>tr[now].val)
    {
        if(tr[tr[now].rc].cnt==0)
        {
            pos=now;
            return;
        }
        zhao(tr[now].rc,x);
    }
    else
    {
        if(tr[tr[now].lc].cnt==0)
        {
            pos=now;
            return;
        }
        zhao(tr[now].lc,x);
    }
}
void rank(int x)
{
    zhao(rt,x);
    splay(pos,0);
    printf("%d\n",tr[tr[pos].lc].siz+1);
}
int pri(int x)
{
    zhao(rt,x);
    splay(pos,0);
    if(tr[pos].val<x)
    {
        return pos;
    }
    else
    {
        pos=tr[pos].lc;
        while(tr[tr[pos].rc].cnt!=0) pos=tr[pos].rc;
        return pos;
    }
}
int bac(int x)
{
    zhao(rt,x);
    splay(pos,0);
    if(tr[pos].val>x)
    {
        return pos;
    }
    else
    {
        pos=tr[pos].rc;
        while(tr[tr[pos].lc].cnt!=0) pos=tr[pos].lc;
        return pos;
    }
}
void del(int x)
{
	int qian=pri(x);
	if(tr[qian].cnt==0)
	{
		tr[0].lc=tr[0].rc=tr[rt].rc;
		tr[tr[rt].rc].fa=0;
		tr[rt].cnt=0;
        tr[rt].siz=0;
        tr[rt].val=0;
        rt=tr[rt].rc;
        return;
	}
	int hou=bac(x);
	if(tr[hou].cnt==0)
	{
		tr[0].lc=tr[0].rc=tr[rt].lc;
		tr[tr[rt].lc].fa=0;
		tr[rt].cnt=0;
        tr[rt].siz=0;
        tr[rt].val=0;
        rt=tr[rt].lc;
        return;
	}
	splay(qian,0);
	splay(hou,qian);
	int pos1=hou;
	pos1=tr[pos1].lc;
	if(tr[pos1].val!=x) return;
	if(tr[pos1].cnt>1) tr[pos1].cnt--;
	else
	{
		tr[pos1].cnt=0;
        tr[pos1].siz=0;
        tr[pos1].val=0;
        tr[qian].siz--;
        tr[hou].siz--;
	}
}
void kth(int x)
{
    int now=rt;
    while(1)
    {
        if(tr[tr[now].lc].cnt!=0&&x<=tr[tr[now].lc].siz)
        {
            now=tr[now].lc;
        }
        else if(x>tr[tr[now].lc].siz+tr[now].cnt&&tr[tr[now].rc].cnt!=0)
        {
            x-=tr[tr[now].lc].siz+tr[now].cnt;
            now=tr[now].rc;
        }
        else
        {
            printf("%d\n",tr[now].val);
            return;
        }
    }
}
int main()
{
	int n;
	cin>>n;                 
    int opt,x;
    tr[0].lc=1;
    tr[0].rc=1;
    rt=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&opt,&x);
        if(opt==1)
        {
            add(rt,x,0);
        }
        else if(opt==2)
        {
            del(x);
        }
        else if(opt==3)
        {
            rank(x);
        }
        else if(opt==4)
        {
            kth(x);
        }
        else if(opt==5)
        {
            printf("%d\n",tr[pri(x)].val);
        }
        else
        {
            printf("%d\n",tr[bac(x)].val);
        }
    …