【bzoj3224】平衡樹模闆（Splay）

bzoj 3224 普通平衡樹 包含此模闆全部操作，可以送出至此。
           

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
const int maxn=;
int fa[maxn],ch[maxn][],dat[maxn],cnt[maxn],siz[maxn],sz,root;
//fa[i]表示i的父結點，ch[i][0]表示i的左兒子，ch[i][1]表示i的右兒子，
//dat[i]表示i的關鍵字（即結點i代表的那個數字），cnt[i]表示i結點的關鍵字出現的次數（相當于權值），
//siz[i]表示包括i的這個子樹的大小；sz為整棵樹的大小，root為整棵樹的根
int n;
inline void clear(int x){//将目前點的各項值都清0
    ch[x][]=ch[x][]=fa[x]=cnt[x]=dat[x]=siz[x]=;
}
inline int get(int x){//判斷目前點是它父結點的左兒子還是右兒子
    return ch[fa[x]][]==x;
    //左兒子傳回0，右兒子傳回1;
}
inline void update(int x){//更新目前點的siz值 
    if(x){
        siz[x]=cnt[x];//定為該點的權值
        if(ch[x][])siz[x]+=siz[ch[x][]];//左兒子的大小
        if(ch[x][])siz[x]+=siz[ch[x][]];//右兒子的大小
    }
}
inline void rotate(int x){//将x結點rotate到它的父親的位置。
    int old=fa[x],oldf=fa[old],wh=get(x);
//找出x與父親的位置關系
    ch[old][wh]=ch[x][wh^];
    fa[ch[old][wh]]=old;
    fa[old]=x;
    ch[x][wh^]=old;
//将原先父親更新到x的對應兒子的位置，将x原先對應兒子更新到x原先父親的對應兒子;
    fa[x]=oldf;
    if(oldf){
        ch[oldf][ch[oldf][]==old]=x;
    }
//将x更新到原先父親的位置;
    update(old);
    update(x);
//更新子樹大小有變化的節點。
} splay(int x){//将x結點rotate到根。
    for(int f;f=fa[x];rotate(x)){
        if(fa[f])rotate((get(x)==get(f)?f:x));
        //分類讨論，如果x與父親，祖父三點共線，則需要rotate父親，否則rotate x，避免出現平衡樹失衡，可以嘗試手動證明。
    }
    root=x;//更新根節點
}
inline void insert(int v){//插入值為v的點
    if(root==){
//子樹為空則特殊處理
        sz++;ch[sz][]=ch[sz][]=fa[sz]=;
        dat[sz]=v;cnt[sz]=;siz[sz]=;root=sz;
        return;
    }
    int now=root,f=;
    while(){
        if(dat[now]==v){
            //若存在v，則增加該節點權值
            cnt[now]++;
            update(now);
            update(f);
            splay(now);
            break;
        }
        f=now;
        now=ch[now][dat[now]<v];
        if(now==){
            //若不存在，則新增節點。
            sz++;
            ch[sz][]=ch[sz][]=;
            dat[sz]=v;
            siz[sz]=;
            cnt[sz]=;
            fa[sz]=f;
            ch[f][dat[f]<v]=sz;
            update(f);
            splay(sz);
            break;
        }
    }
}e int find(int v){//查詢v的排名
    int ans=,now=root;
    while(){
        if(v<dat[now])now=ch[now][];
        else{
            ans+=(ch[now][]?siz[ch[now][]]:);
            if(v==dat[now]){splay(now);return ans+;}
            ans+=cnt[now];
            now=ch[now][];
        }
    }
}
inline int findx(int x){//找到排名為x的點
    int now=root;
    while(){
        if(ch[now][]&&x<=siz[ch[now][]]){
            now=ch[now][];
        }else{
            int tmp=(ch[now][]?siz[ch[now][]]:)+cnt[now];
            if(x<=tmp)return dat[now];
            x-=tmp;
            now=ch[now][];
        }
    }
}
inline int pre(){//查詢樹上的前驅
    int now=ch[root][];
    while(ch[now][])now=ch[now][];
    return now;
}
inline int nxt(){//查詢樹上的後繼
    int now=ch[root][];
    while(ch[now][])now=ch[now][];
    return now;
}
inline void del(int x){//删除節點x
    int wh=find(x);//把x旋轉到根
    //分類讨論每一種情況
    if(cnt[root]>){cnt[root]--;return;}
    if(!ch[root][]&&!ch[root][]){clear(root);root=;return;}
    if(!ch[root][]){
        int oldr=root;
        root=ch[root][];
        fa[root]=;
        clear(oldr);
        return;
    }else if(!ch[root][]){
        int oldr=root;
        root=ch[root][];
        fa[root]=;
        clear(oldr);
        return;
    }
    //若兩個兒子都有，則把x的前驅splay到樹根，再把原來根節點的右兒子接到現在的根上，此時原先的根就變成了葉子節點，直接删除即可。
    int lb=pre();
    int oldr=root;
    splay(lb);
    fa[ch[oldr][]]=root;
    ch[root][]=ch[oldr][];
    clear(oldr);
    update(root);
    return;
}
inline int prex(int x){//查x的前驅
    //查詢x的前驅即插入x，查詢樹上的前驅（此時x為root），然後删除x的過程，後繼同理。
    insert(x);
    int ans=pre();
    del(x);
    return dat[ans];
}
inline int nxtx(int x){//查x的後繼
    insert(x);
    int ans=nxt();
    del(x);
    return dat[ans];
}
int main(){
    scanf("%d",&n);
    int opt,xx;
    while(n--){
        scanf("%d%d",&opt,&xx);
        if(opt==){
            insert(xx);
            continue;
        }
        if(opt==){
            del(xx);
            continue;
        }
        if(opt==){
            printf("%d\n",find(xx));
            continue;
        }
        if(opt==){
            printf("%d\n",findx(xx));
            continue;
        }
        if(opt==){
            printf("%d\n",prex(xx));
            continue;
        }
        if(opt==){
            printf("%d\n",nxtx(xx));
            continue;
        }
    }
    return ;
}