2018-team4-modules-LCT

从 Trac 迁移的文章

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

原文章内容如下：

{{{
struct Node{
    Node *ch[2],*fa;
    int tag;
}mem[maxn],*null,*it;
inline void init(){
    it = mem;null = it++;
    null->ch[0] = null->ch[1] = null->fa = null;
    null->tag = 0;
}
inline void newNode(){
    Node *p = it++;p->tag = 0;
    p->ch[0] = p->ch[1] = p->fa = null;
}
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 Node* Access(Node *x){
    for(Node *y = null;x != null;y = x,x=x->fa)
        Splay(x),x->ch[1] = y;
    return x;
}
inline void makeRoot(Node *x){
    Access(x);Splay(x);x->tag ^= 1;
}
inline Node* findRoot(Node *x){
    Access(x);Splay(x);
    while(x->ch[0] != null) x = x->ch[0];
    Splay(x);return x;
}
inline void link(Node *u,Node *v){
    makeRoot(u);u->fa = v;
}
inline void cut(Node *u,Node *v){
    makeRoot(u);Access(v);Splay(v);
    v->ch[0] = v->ch[0]->fa = null;
}
}}}

struct Node{
    Node *ch[2],*fa;
    int tag;
}mem[maxn],*null,*it;
inline void init(){
    it = mem;null = it++;
    null->ch[0] = null->ch[1] = null->fa = null;
    null->tag = 0;
}
inline void newNode(){
    Node *p = it++;p->tag = 0;
    p->ch[0] = p->ch[1] = p->fa = null;
}
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 Node* Access(Node *x){
    for(Node *y = null;x != null;y = x,x=x->fa)
        Splay(x),x->ch[1] = y;
    return x;
}
inline void makeRoot(Node *x){
    Access(x);Splay(x);x->tag ^= 1;
}
inline Node* findRoot(Node *x){
    Access(x);Splay(x);
    while(x->ch[0] != null) x = x->ch[0];
    Splay(x);return x;
}
inline void link(Node *u,Node *v){
    makeRoot(u);u->fa = v;
}
inline void cut(Node *u,Node *v){
    makeRoot(u);Access(v);Splay(v);
    v->ch[0] = v->ch[0]->fa = null;
}