【Splay】【Luogu3369】普通平衡树

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
struct node{
    int lc,rc,fa,size,v;
}a[100004];
int n,cnt=0,rt=0;
inline void pushup(int k){
    a[k].size=a[a[k].lc].size+a[a[k].rc].size+1;
}
inline void rotate(int x,int d){
    int y=a[x].fa,z=a[y].fa;
    if(d==1){
        a[y].lc=a[x].rc;a[a[x].rc].fa=y;
        a[x].rc=y;a[y].fa=x;a[x].fa=z;
        if(a[z].lc==y) a[z].lc=x;
        if(a[z].rc==y) a[z].rc=x;
        pushup(y);pushup(x);
    }
    if(d==0){
        a[y].rc=a[x].lc;a[a[x].lc].fa=y;
        a[x].lc=y;a[y].fa=x;a[x].fa=z;
        if(a[z].rc==y) a[z].rc=x;
        if(a[z].lc==y) a[z].lc=x;
        pushup(y);pushup(x);
    }
}
inline void splay(int x,int f){
    while(a[x].fa!=f){
        int y=a[x].fa,z=a[y].fa;
        if(z==f&&a[y].lc==x) rotate(x,1);
        else if(z==f&&a[y].rc==x) rotate(x,0); 
        else if(a[z].lc==y&&a[y].lc==x) rotate(y,1),rotate(x,1); 
        else if(a[z].rc==y&&a[y].rc==x) rotate(y,0),rotate(x,0); 
        else if(a[z].lc==y&&a[y].rc==x) rotate(x,0),rotate(x,1); 
        else if(a[z].rc==y&&a[y].lc==x) rotate(x,1),rotate(x,0); 
    }
}
inline void ins(int k,const int key){
    if(a[k].v<key){
        if(a[k].rc==0){
            a[++cnt].size=1;a[cnt].v=key;a[k].rc=cnt,a[cnt].fa=k;
            splay(cnt,0),rt=cnt;
        }else {ins(a[k].rc,key);pushup(k);}
    }else{
        if(a[k].lc==0){
            a[++cnt].size=1;a[cnt].v=key;a[k].lc=cnt,a[cnt].fa=k;
            splay(cnt,0);rt=cnt;
        }else {ins(a[k].lc,key);pushup(k);}
    }
}
inline int QueryRank(int k,int x){
    int res=INF,ans=0;
    while(k){
        if(a[k].v==x) res=min(res,ans+a[a[k].lc].size+1);
        if(a[k].v<x) ans+=a[a[k].lc].size+1,k=a[k].rc;
        else k=a[k].lc;
    }
    return res==INF?ans:res;
}
inline int QueryKth(int k,int x){
    while(1){
        if(a[a[k].lc].size==x-1) return a[k].v;
        if(a[a[k].lc].size<x-1) x-=(a[a[k].lc].size+1),k=a[k].rc;
        else k=a[k].lc;
    }
}
inline int QueryQian(int k,int x){
    int ans=-INF;
    while(k){
        if(a[k].v<x) ans=max(ans,a[k].v),k=a[k].rc;
        else k=a[k].lc;
    }
    return ans;
}
inline int QueryHou(int k,int x){
    int ans=INF;
    while(k){
        if(a[k].v>x) ans=min(ans,a[k].v),k=a[k].lc;
        else k=a[k].rc;
    }
    return ans;
}
int getk(int now,int k){
    int wtf=a[a[now].lc].size+1;
    if(wtf==k) return now;
    if(wtf<k) return getk(a[now].rc,k-wtf);
    else return getk(a[now].lc,k);
}
inline void del(int x){
    int k=QueryRank(rt,x);
    int n1=getk(rt,k-1);
    splay(n1,0);rt=n1;
    splay(getk(rt,k+1),rt);
    a[a[rt].rc].lc=0;
}
int main(){
    scanf("%d",&n);
    ins(rt,-INF);
    ins(rt,INF);
    while(n--){
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt==1) ins(rt,x);
        else if(opt==2) del(x);
        else if(opt==3) printf("%d\n",QueryRank(rt,x)-1);
        else if(opt==4) printf("%d\n",QueryKth(rt,x+1));
        else if(opt==5) printf("%d\n",QueryQian(rt,x));
        else if(opt==6) printf("%d\n",QueryHou(rt,x));
    } 
}