刚学OI的萌新求助替罪羊树

#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <istream>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <unordered_map>
#include <random>
#include <bitset>
//#define int long long
//#define double long double
#define p1(x) x.first
#define p2(x) x.second
#define i128  __int128_t
//#pragma GCC optimize(2)
#define w(x) t[x].w
#define siz(x) t[x].siz
#define fa(x) t[x].fa
#define lc(x) t[x].c[0]
#define rc(x) t[x].c[1]
#define d(x) t[x].d
#define dc(x) t[x].dc
#define pii pair<int,int>
//若汁记好了以后再用Ctrl+C/+V你就是狗
using namespace std;
int n;
const double alpha=0.7,bta=0.5;
struct node {
    int siz,w,fa,dc;
    int c[2];
    bool d;
}t[100300];
int a[100300];
int cnt;
int ct=0;
int rt=0;
inline void upd(int x){
    dc(x)=dc(lc(x))+dc(rc(x))+d(x);
    siz(x)=siz(lc(x))+siz(rc(x))+1;
}
inline int tsiz(int x){
    return siz(x)-dc(x);
}
inline void trs(int x){
    if(lc(x))trs(lc(x));
    if(!d(x))
    a[++ct]=x;
    if(rc(x))trs(rc(x));
}
inline int rb(int l,int r){
    if(r<l)return 0;
    if(l==r){
        siz(a[l])=1;
        lc(a[l])=rc(a[l])=0;
        dc(a[l])=0;
        return a[l];
    }
    else if(l==r-1){
        rc(a[l])=a[r];
        siz(a[r])=1;
        siz(a[l])=2;
        lc(a[l])=lc(a[r])=rc(a[r])=0;
        fa(a[r])=a[l];
        dc(a[l])=dc(a[r])=0;
        return a[l];
    }
    int mid=l+r>>1;
    siz(a[mid])=r-l+1;
    dc(a[mid])=0;
    lc(a[mid])=rb(l,mid-1);
    fa(lc(a[mid]))=a[mid];
    rc(a[mid])=rb(mid+1,r);
    fa(rc(a[mid]))=a[mid];
    return a[mid];
}
inline void chk(int x){
    if(max(siz(lc(x)),siz(rc(x)))>siz(x)*alpha||dc(x)>siz(x)*bta){
        ct=0;
        trs(x);
        bool p=x==t[fa(x)].c[1];
        int f=fa(x);
        t[fa(x)].c[p]=rb(1,ct);
        fa(t[f].c[p])=f;
    }
}
inline int nnd(int x){
    ++cnt;
    w(cnt)=x;
    siz(cnt)=1;
    return cnt;
}
inline void ins(int &x,int v){
    if(!x){
        x=nnd(v);
        return ;
    }
    if(v<w(x))
        ins(lc(x),v),fa(lc(x))=x;
    else ins(rc(x),v),fa(rc(x))=x;
    upd(x);
    chk(x);
}
inline void del(int &x,int k){
    if(!x)return ;
    int tmp=tsiz(x)-tsiz(rc(x));
    if(tmp==k&&!d(x)){
        d(x)=1;
        dc(x)++;
        return ;
    }
    if(tmp<=k)
        del(lc(x),k);
    else del(rc(x),k-tmp);
    upd(x);
    chk(x);
    
}
inline int rk(int &x,int v){
    if(!x)return 1;
    if(w(x)>=v)
        return rk(lc(x),v);
    else return tsiz(x)-tsiz(rc(x))+rk(rc(x),v);
}
inline int kth(int &x,int k){
    int tmp=tsiz(x)-tsiz(rc(x));
    if(k>tmp){
        k-=tmp;
        return kth(rc(x),k);
    }
    else if(k<tmp)return kth(lc(x),k);
    else {
        if(!d(x))return w(x);
        else return kth(lc(x),k);
    }
}
inline int pre(int &x,int v){
    return kth(x,rk(x,v)-1);
}
inline int suf(int &x,int v){
    return kth(x,rk(x,v+1));
}
signed main(){
    ios::sync_with_stdio(0);
//    freopen("","r",stdin);
//    freopen("","w",stdout);
    cin>>n;
    while(n--){
        int op,x;
        cin>>op>>x;
        if(op==1)ins(rt,x);
        else if(op==2)del(rt,rk(rt,x));
        else if(op==3)cout<<rk(rt,x)<<endl;
        else if(op==4)cout<<kth(rt,x)<<endl;
        else if(op==5)cout<<pre(rt,x)<<endl;
        else cout<<suf(rt,x)<<endl;
    }
    return 0;
}