Splay

Splay

模板：普通平衡树
洛谷3369

Splay即为伸展树，本体就是一个排序二叉树，主要通过节点的父子关系改变而进行旋转，从而使得二叉树尽量平衡；
核心部分即为splay和rotate，代码中对此有清晰的讨论

#include<cstdio>
#include<algorithm>
#define MAXN 100009
using namespace std;
int n;
class SP{
    public:
        struct T{
            int ls,rs,fa,sz,num,val;
        };
        int root;int size;
        T tree[MAXN];
        void DEBUG(int k){
            if(k==0)return;
            DEBUG(tree[k].ls);
            printf("No. %2d:val=%d|ls=%d|rs=%d|fa=%d|sz=%d|num=%d\n",k,tree[k].val,tree[k].ls,tree[k].rs,tree[k].fa,tree[k].sz,tree[k].num);
            DEBUG(tree[k].rs);
        }
        int max_t(int x){
            int k=x;
            while(x){
                k=x;
                x=tree[x].rs;
            }
            return k;
        }
        int min_t(int x){
            int k=x;
            while(x){
                k=x;
                x=tree[x].ls;
            }
            return k;
        }
        int Find(int k,int x){
            if(k==0)return 0;
            if(tree[k].val==x)
                return k;
            else if(tree[k].val<x)
                return Find(tree[k].rs,x);
            else
                return Find(tree[k].ls,x);
        }
        void update(int x){
            tree[x].sz=tree[tree[x].ls].sz+tree[tree[x].rs].sz+tree[x].num;
        }
        void rotate_l(int x){
            int flag=0;
            int y=tree[x].fa,z=tree[y].fa,p=tree[x].ls;
            if(tree[z].rs==y)flag=0;
            else flag=1;
            if(z==0)
                flag=-1;
            tree[x].ls=y;
            tree[y].rs=p;
            if(flag==0)tree[z].rs=x;
            else if(flag==1) tree[z].ls=x;
            else root=x;
            tree[x].fa=z;
            tree[y].fa=x;
            tree[p].fa=y;
            update(y);
            update(x);
        }
        void rotate_r(int x){
            int flag=0;
            int y=tree[x].fa,z=tree[y].fa,p=tree[x].rs;
            if(tree[z].rs==y)flag=0;
            else flag=1;
            if(z==0)
                flag=-1;
            tree[y].ls=p;
            tree[x].rs=y;
            if(flag==0)tree[z].rs=x;
            else if(flag==1) tree[z].ls=x;
            else root=x;
            tree[x].fa=z;
            tree[p].fa=y;
            tree[y].fa=x;
            update(y);
            update(x);
        }
        void splay(int x,int to,int type){
            int y,z;
            to=tree[to].fa;
            if(type==1)
                x=Find(root,x);
            while(tree[x].fa!=to){
                y=tree[x].fa;z=tree[y].fa;
                if(z==to){
                    if(tree[y].ls==x)rotate_r(x);
                    else rotate_l(x);
                }
                else{
                    if(tree[z].ls==y && tree[y].ls==x){
                        rotate_r(y);
                        rotate_r(x);
                    }
                    else if(tree[z].ls==y && tree[y].rs==x)
                        rotate_l(x),rotate_r(x);
                    else if(tree[z].rs==y && tree[y].rs==x)
                        rotate_l(y),rotate_l(x);
                    else if(tree[z].rs==y && tree[y].ls==x)
                        rotate_r(x),rotate_l(x);
                    update(z);
                }
            }
            if(to==0)root=x;
        }
        void insert(int &k,int v,int father){
            if(k==0){
                k=++size;
                tree[k].val=v;
                tree[k].fa=father;
                tree[k].num=tree[k].sz=1;
                return;
            }
            tree[k].sz++;
            if(tree[k].val==v)
                tree[k].num++;
            else if(tree[k].val<v)
                insert(tree[k].rs,v,k);
            else
                insert(tree[k].ls,v,k);
        }
        void del(int x){
            int p=0;
            if(!Find(root,x))return;
            splay(x,root,1);
            x=Find(root,x);
            if(tree[x].num>1){
                tree[x].num--;
                return;
            }
            if(tree[x].ls*tree[x].rs==0)root=tree[x].ls+tree[x].rs;
            else{
                p=max_t(tree[x].ls);
                tree[p].rs=tree[x].rs;
                tree[tree[x].rs].fa=p;
                root=tree[x].ls;
            }
            tree[root].fa=0;
            while(p!=0){
                update(p);
                p=tree[p].fa;
            }
        }
        int n2r(int x){
            splay(x,root,1);
            return tree[tree[root].ls].sz+1;
        }
        int r2n(int x){
            int now=root;
            while(1){
                int minused=tree[now].num+tree[tree[now].ls].sz;
                if(x>tree[tree[now].ls].sz && x<=minused)
                    break;
                if(x<=tree[tree[now].ls].sz)
                    now=tree[now].ls;
                else{
                    x-=minused;
                    now=tree[now].rs;
                }
            }
            splay(now,root,0);
            return tree[now].val;
        }
        int pred(int x){
            int re;
            insert(root,x,0);
            splay(x,root,1);
            if(tree[root].ls==0)
                re=0;
            else 
                re=tree[max_t(tree[root].ls)].val;
            del(x);
            return re;
        }
        int succ(int x){
            int re;
            insert(root,x,0);
            splay(x,root,1);
            if(tree[root].rs==0)
                re=0;
            else
                re=tree[min_t(tree[root].rs)].val;
            del(x);
            return re;
        }
}Splay;
int main(){
    freopen("splay.in","r",stdin);
    freopen("splay.out","w",stdout);
    scanf("%d",&n);
    int i;
    for(i=1;i<=n;i++){
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt==1)
            Splay.insert(Splay.root,x,0);
        else if(opt==2)
            Splay.del(x);
        else if(opt==3)
            printf("%d\n",Splay.n2r(x));
        else if(opt==4)
            printf("%d\n",Splay.r2n(x));
        else if(opt==5)
            printf("%d\n",Splay.pred(x));
        else if(opt==6)
            printf("%d\n",Splay.succ(x));
        //printf("----------DEBUG------------\norderNo.%d    root:%d\n",i,Splay.root),Splay.DEBUG(Splay.root);
    }
    return 0;
}