2018-team4-modules-Splay

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
inline void rotate(Node *p,Node *x){
    int k = x->ch[1] == p;
    Node *y = p->ch[k^1],*z = x->fa;
    if(z->ch[0] == x) z->ch[0] = p;
    if(z->ch[1] == x) z->ch[1] = p;
    if(y != null) y->fa = x;
    p->fa = z;p->ch[k^1] = x;
    x->fa = p;x->ch[k] = y;
}
inline void pushdown(Node *p){
    if(p == null) return;
    if(p->tag){
        if(p->ch[0] != null) p->ch[0]->tag ^= 1;
        if(p->ch[1] != null) p->ch[1]->tag ^= 1;
        swap(p->ch[0],p->ch[1]);p->tag = 0;
    }
}
inline bool isroot(Node *p){
    return (p == null) || (p->fa->ch[0] != p && p->fa->ch[1] != p);
}
inline void Splay(Node *p){
    pushdown(p);
    while(!isroot(p)){
        Node *x = p->fa,*y = x->fa;
        pushdown(y);pushdown(x);pushdown(p);
        if(isroot(x)) rotate(p,x);
        else if((x->ch[0] == p) ^ (y->ch[0] == x)) rotate(p,x),rotate(p,y);
        else rotate(x,y),rotate(p,x);
    }
}
}}}

inline void rotate(Node *p,Node *x){
    int k = x->ch[1] == p;
    Node *y = p->ch[k^1],*z = x->fa;
    if(z->ch[0] == x) z->ch[0] = p;
    if(z->ch[1] == x) z->ch[1] = p;
    if(y != null) y->fa = x;
    p->fa = z;p->ch[k^1] = x;
    x->fa = p;x->ch[k] = y;
}
inline void pushdown(Node *p){
    if(p == null) return;
    if(p->tag){
        if(p->ch[0] != null) p->ch[0]->tag ^= 1;
        if(p->ch[1] != null) p->ch[1]->tag ^= 1;
        swap(p->ch[0],p->ch[1]);p->tag = 0;
    }
}
inline bool isroot(Node *p){
    return (p == null) || (p->fa->ch[0] != p && p->fa->ch[1] != p);
}
inline void Splay(Node *p){
    pushdown(p);
    while(!isroot(p)){
        Node *x = p->fa,*y = x->fa;
        pushdown(y);pushdown(x);pushdown(p);
        if(isroot(x)) rotate(p,x);
        else if((x->ch[0] == p) ^ (y->ch[0] == x)) rotate(p,x),rotate(p,y);
        else rotate(x,y),rotate(p,x);
    }
}