2018-team4-modules-树链剖分

从 Trac 迁移的文章

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

原文章内容如下：

{{{
struct Edge{
    int to,next;
}G[maxn<<1];
int head[maxn],cnt;
void add(int u,int v){
    G[++cnt].to = v;
    G[cnt].next = head[u];
    head[u] = cnt;
}
int n,m;
namespace seg{
#define v G[i].to
    int top[maxn],son[maxn],siz[maxn];
    int dep[maxn],ind[maxn],oud[maxn];
    int dfs_clock,fa[maxn];
    void dfs(int u){
        siz[u] = 1;
        for(int i = head[u];i;i=G[i].next){
            if(v == fa[u]) continue;
            fa[v] = u;
            dep[v] = dep[u] + 1;
            dfs(v);
            siz[u] += siz[v];
            if(siz[son[u]] < siz[v]) son[u] = v;
        }
    }
    void dfs(int u,int tp){
        top[u] = tp;
        ind[u] = ++ dfs_clock;
        if(son[u]) dfs(son[u],tp);
        for(int i = head[u];i;i=G[i].next){
            if(v == fa[u] || v == son[u]) continue;
            dfs(v,v);
        }
        oud[u] = dfs_clock;
    }
#undef v
    struct segTree{
        int sum[maxn<<2],tag[maxn<<2],mx[maxn<<2];
        inline void pushdown(int rt,int l,int r){
            if(rt == 0 || tag[rt] == 0) return ;
            int mid = l+r >> 1;
            sum[rt<<1] += tag[rt]*(mid - l + 1);
            sum[rt<<1|1] += tag[rt]*(r - mid);
            mx[rt<<1] += tag[rt];
            mx[rt<<1|1] += tag[rt];
            tag[rt<<1] += tag[rt];
            tag[rt<<1|1] += tag[rt];
            tag[rt] = 0;
        }
        void modify(int rt,int l,int r,int L,int R,int d){
            if(L <= l && r <= R){
                tag[rt] += d;
                sum[rt] += d*(r - l + 1);
                mx[rt] += d;
                return ;
            }
            int mid = l+r >> 1;pushdown(rt,l,r);
            if(L <= mid) modify(rt<<1,l,mid,L,R,d);
            if(R >  mid) modify(rt<<1|1,mid+1,r,L,R,d);
            sum[rt] = sum[rt<<1] + sum[rt<<1|1];
            mx[rt] = max(mx[rt<<1],mx[rt<<1|1]);
        }
        int query_max(int rt,int l,int r,int L,int R){
            if(L <= l && r <= R) return mx[rt];
            int mid = l+r >> 1;pushdown(rt,l,r);
            if(R <= mid) return query_max(rt<<1,l,mid,L,R);
            if(L >  mid) return query_max(rt<<1|1,mid+1,r,L,R);
            return max(query_max(rt<<1,l,mid,L,R),query_max(rt<<1|1,mid+1,r,L,R));
        }
        int query_sum(int rt,int l,int r,int L,int R){
            if(L <= l && r <= R) return sum[rt];
            int mid = l+r >> 1;pushdown(rt,l,r);
            if(R <= mid) return query_sum(rt<<1,l,mid,L,R);
            if(L >  mid) return query_sum(rt<<1|1,mid+1,r,L,R);
            return query_sum(rt<<1,l,mid,L,R) + query_sum(rt<<1|1,mid+1,r,L,R);
        }
    }T1,T2;
}
inline int query(int u,int v){
    using namespace seg;
    int ret = 0;
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]) swap(u,v);
        ret += T1.query_sum(1,1,n,ind[top[u]],ind[u]);
        u = fa[top[u]];
    }if(dep[u] > dep[v]) swap(u,v);
    if(ind[u] + 1 <= ind[v]) ret += T1.query_sum(1,1,n,ind[u]+1,ind[v]);
    return ret;
}
}}}

struct Edge{
    int to,next;
}G[maxn<<1];
int head[maxn],cnt;
void add(int u,int v){
    G[++cnt].to = v;
    G[cnt].next = head[u];
    head[u] = cnt;
}
int n,m;
namespace seg{
#define v G[i].to
    int top[maxn],son[maxn],siz[maxn];
    int dep[maxn],ind[maxn],oud[maxn];
    int dfs_clock,fa[maxn];
    void dfs(int u){
        siz[u] = 1;
        for(int i = head[u];i;i=G[i].next){
            if(v == fa[u]) continue;
            fa[v] = u;
            dep[v] = dep[u] + 1;
            dfs(v);
            siz[u] += siz[v];
            if(siz[son[u]] < siz[v]) son[u] = v;
        }
    }
    void dfs(int u,int tp){
        top[u] = tp;
        ind[u] = ++ dfs_clock;
        if(son[u]) dfs(son[u],tp);
        for(int i = head[u];i;i=G[i].next){
            if(v == fa[u] || v == son[u]) continue;
            dfs(v,v);
        }
        oud[u] = dfs_clock;
    }
#undef v
    struct segTree{
        int sum[maxn<<2],tag[maxn<<2],mx[maxn<<2];
        inline void pushdown(int rt,int l,int r){
            if(rt == 0 || tag[rt] == 0) return ;
            int mid = l+r >> 1;
            sum[rt<<1] += tag[rt]*(mid - l + 1);
            sum[rt<<1|1] += tag[rt]*(r - mid);
            mx[rt<<1] += tag[rt];
            mx[rt<<1|1] += tag[rt];
            tag[rt<<1] += tag[rt];
            tag[rt<<1|1] += tag[rt];
            tag[rt] = 0;
        }
        void modify(int rt,int l,int r,int L,int R,int d){
            if(L <= l && r <= R){
                tag[rt] += d;
                sum[rt] += d*(r - l + 1);
                mx[rt] += d;
                return ;
            }
            int mid = l+r >> 1;pushdown(rt,l,r);
            if(L <= mid) modify(rt<<1,l,mid,L,R,d);
            if(R >  mid) modify(rt<<1|1,mid+1,r,L,R,d);
            sum[rt] = sum[rt<<1] + sum[rt<<1|1];
            mx[rt] = max(mx[rt<<1],mx[rt<<1|1]);
        }
        int query_max(int rt,int l,int r,int L,int R){
            if(L <= l && r <= R) return mx[rt];
            int mid = l+r >> 1;pushdown(rt,l,r);
            if(R <= mid) return query_max(rt<<1,l,mid,L,R);
            if(L >  mid) return query_max(rt<<1|1,mid+1,r,L,R);
            return max(query_max(rt<<1,l,mid,L,R),query_max(rt<<1|1,mid+1,r,L,R));
        }
        int query_sum(int rt,int l,int r,int L,int R){
            if(L <= l && r <= R) return sum[rt];
            int mid = l+r >> 1;pushdown(rt,l,r);
            if(R <= mid) return query_sum(rt<<1,l,mid,L,R);
            if(L >  mid) return query_sum(rt<<1|1,mid+1,r,L,R);
            return query_sum(rt<<1,l,mid,L,R) + query_sum(rt<<1|1,mid+1,r,L,R);
        }
    }T1,T2;
}
inline int query(int u,int v){
    using namespace seg;
    int ret = 0;
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]]) swap(u,v);
        ret += T1.query_sum(1,1,n,ind[top[u]],ind[u]);
        u = fa[top[u]];
    }if(dep[u] > dep[v]) swap(u,v);
    if(ind[u] + 1 <= ind[v]) ret += T1.query_sum(1,1,n,ind[u]+1,ind[v]);
    return ret;
}