WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
Link-Cut-Tree 模版
Link-Cut-Tree 模版
namespace LCT{
    #define fa(x) tree[x].fa
    #define ls(x) tree[x].ch[0]
    #define rs(x) tree[x].ch[1]
    #define LL long long
    const int MAXN=2e5+50;
    const int MOD=51061;
    struct BTree{
        int ch[2], fa, rev;
        int siz, sum, val; // Splay大小,Splay子树和,点权
        int si, tsiz; // LCT虚子树大小和与子树大小和
        int mul, add; // 加乘Tag
        inline void clear(){
            fa=ch[0]=ch[1]=rev=0;
            siz=val=sum=1; mul=1; add=0;
            tsiz=1; si=0;
        }
    }tree[MAXN];
    int ident(int x){ return tree[fa(x)].ch[0]==x?0:1; } // 判断左右节点
    void connect(int x, int f, int s){ tree[x].fa=f, tree[f].ch[s]=x; } // 将x设为f的s儿子
    inline bool isRoot(int x){ return ls(fa(x))!=x && rs(fa(x))!=x; } // 判断x是否为其所在Splay的根

    void update(int x){ // 更新维护值
        // Update Info
        tree[x].siz=tree[ls(x)].siz+tree[rs(x)].siz+1;
        tree[x].tsiz=tree[ls(x)].tsiz+tree[rs(x)].tsiz+tree[x].si+1;
        tree[x].sum=(tree[ls(x)].sum+tree[rs(x)].sum+tree[x].val)%MOD;
    }

    void modify(int x, int m, int a){ // 修改点的元素值
        tree[x].val=(1LL*tree[x].val*m%MOD+a)%MOD;
        tree[x].sum=(1LL*tree[x].sum*m%MOD+1LL*tree[x].siz*a%MOD)%MOD;
        tree[x].mul=1LL*tree[x].mul*m%MOD;
        tree[x].add=1LL*tree[x].add*m%MOD;
        tree[x].add=(tree[x].add+a)%MOD;
    }

    void clean(int x){ // 下推标记
        if (tree[x].rev){
            tree[x].rev=0; swap(ls(x), rs(x));
            tree[ls(x)].rev^=1; tree[rs(x)].rev^=1;
        }
        // Push Down Tag
        if (tree[x].mul!=1){
            int mul=tree[x].mul; tree[x].mul=1;
            if (ls(x)) modify(ls(x), mul, 0);
            if (rs(x)) modify(rs(x), mul, 0);
        }
        if (tree[x].add!=0){
            int add=tree[x].add; tree[x].add=0;
            if (ls(x)) modify(ls(x), 1, add);
            if (rs(x)) modify(rs(x), 1, add);
        }
    }

    void rotate(int x){ // 将x向上旋转
        int y=fa(x), r=fa(y);
        int ys=ident(x), rs=ident(y);
        int b=tree[x].ch[ys^1];
        fa(x)=r;
        if (!isRoot(y)) connect(x, r, rs);
        connect(b, y, ys);
        connect(y, x, ys^1);
        update(y); update(x);
    }
    int st[MAXN];
    void splay(int x){ // 将x转到Splay的根节点
        int y=x, top=0;
        st[++top]=y;
        while(!isRoot(y)) st[++top]=y=fa(y);
        while(top) clean(st[top--]);
        for (int y=fa(x); !isRoot(x); rotate(x), y=fa(x)){
            if (!isRoot(y)) rotate(ident(x)==ident(y)?x:y);
        }
    }

    void access(int x){ // 提取根到x的路径
        for (int y=0; x; x=fa(y=x)) {
            splay(x);
            tree[x].si+=tree[rs(x)].tsiz;
            rs(x)=y;
            tree[x].si-=tree[rs(x)].tsiz;
            update(x);
        }
    }
    void makeRoot(int x){ access(x); splay(x); tree[x].rev^=1; clean(x); } // 将x变为整个LCT的根节点
    int findRoot(int x){ //找到x所在Splay的根节点
        access(x); splay(x); clean(x);
        while(ls(x)) clean(x=ls(x));
        return x;
    }
    void split(int x, int y){ makeRoot(x); access(y); splay(y); } // 提取x到y的路径(y为根)
    void link(int x, int y){ // 在x与y之间连边(存在则不连接)
        makeRoot(x);
        if (findRoot(y)!=x) {
            fa(x)=y;
            tree[fa(x)].si+=tree[x].tsiz;
        }
    }
    void cut(int x, int y){ // 删除x到y之间的边(没有则不删除)
        makeRoot(x);
        if (findRoot(y)==x && fa(x)==y && ls(y)==x && !rs(x))
            fa(x)=ls(y)=0, update(y);
    }
}
赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

Link-Cut-Tree 模版
namespace LCT{ #define fa(x) tree[x].fa #define ls(x) tree[x].ch[0] #define rs(x) tree[x].ch[1] #define LL long long const int MAXN=2e5+50; const int …
扫描二维码继续阅读
2018-10-14
<--! http2https -->