HDU 5052 /// 树链剖分+线段树区间合并

题目大意：

给定n （表示树有n个结点）

接下来n行给定n个点的点权（在这个点上买鸡或者卖鸡的价钱就是点权）

接下来n-1行每行给定 x y 表示x结点和y结点之间有一条边

给定q （表示有q个询问）

接下来q行每行给定 x y v

查询x到y的路径上先买鸡再卖鸡能够赢得的最大利润

买卖完后 x到y整条路径的点权都要加上v

因为必须先买再卖所以这个买卖有方向性

就得维护区间从左向右买卖的最大利润maxl 和从右向左买卖的最大利润maxr

而从左向右买卖的利润maxl = 右子区间的最大值 - 左子区间的最小值（maxr同理）

所以还要维护区间最大值maxw 和最小值minw

整条路径都加上v 区间更新还要加个 lazy 标记

查询时最后路径被分成 LCA-x 和 LCA-y 由LCA到底部的两段

所以按方向更新答案应该 ans=max( LCA-y.maxl , LCA-x.maxr )

最后还要通过 ans=max( ans , LCA-y.maxw - LCA-x.minw ) 更新一下答案

最后我的代码里线段树的 pushUp() 操作直接调用了 Merge() 函数

而 lazy 在合并前已经更新过了防止出错将已得到的 lazy 传参赋值

而查询时的合并操作只需要查询线段树不需要修改所以lazy直接传个没用的0就好了

#include <stdio.h>

#include <algorithm>

#include <cstring>

using namespace std;

#define INF 0x3f3f3f3f

#define mem(i,j) memset(i,j,sizeof(i))

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define root 1,n,1

const int maxn=1e5+;

int n, q, w[maxn];

struct IntervalTree {

    struct EDGE { int to,ne; }e[maxn<<];

    int head[maxn], tot;

    void addE(int u,int v) {

        e[tot].to=v;

        e[tot].ne=head[u];

        head[u]=tot++;

    }

    int fa[maxn], son[maxn], dep[maxn], num[maxn];

    int top[maxn], p[maxn], fp[maxn], pos;

    void init() {

        tot=; mem(head,);

        pos=; mem(son,);

    }

    struct TREE {

        int lazy;

        int maxw,minw; // 区间极值

        int maxl,maxr; // 从左开始最大差值 从右开始最大差值

        TREE(){ lazy=maxw=minw=maxl=maxr=; }

    }tree[maxn<<];

// --------------------以下是线段树-------------------------

    TREE Merge(TREE L,TREE R,int lazy) {

        if(R.maxw==) return L;

        TREE ans; ans.lazy=lazy;

        ans.maxw=max(L.maxw,R.maxw);

        ans.minw=min(L.minw,R.minw);

        ans.maxl=max(max(L.maxl,R.maxl),R.maxw-L.minw);

        ans.maxr=max(max(L.maxr,R.maxr),L.maxw-R.minw);

        return ans;

    }

    void pushUp(int rt) {

        tree[rt]=Merge(tree[rt<<],tree[rt<<|],tree[rt].lazy);

    }

    void pushDown(int rt) {

        if(tree[rt].lazy) {

            int t=tree[rt].lazy;

            tree[rt<<].minw+=t;

            tree[rt<<].maxw+=t;

            tree[rt<<].lazy+=t;

            tree[rt<<|].minw+=t;

            tree[rt<<|].maxw+=t;

            tree[rt<<|].lazy+=t;

            tree[rt].lazy=;

        } // 差值不变 不需要更新

    }

    void build(int l,int r,int rt) {

        tree[rt].lazy=;

        if(l==r) {

            tree[rt].maxw=tree[rt].minw=fp[l];

            tree[rt].maxl=tree[rt].maxr=;

            return;

        }

        int m=(l+r)>>;

        build(lson), build(rson);

        pushUp(rt);

    }

    void update(int L,int R,int v,int l,int r,int rt) {

        if(l==L && R==r) {

            tree[rt].lazy+=v;

            tree[rt].maxw+=v;

            tree[rt].minw+=v;

            return;

        }

        pushDown(rt);

        int m=(l+r)>>;

        if(R<=m) update(L,R,v,lson);

        else if(L>m) update(L,R,v,rson);

        else update(L,m,v,lson),update(m+,R,v,rson);

        pushUp(rt);

    }

    TREE query(int L,int R,int l,int r,int rt) {

        if(L==l && r==R) return tree[rt];

        pushDown(rt);

        int m=(l+r)>>;

        if(R<=m) return query(L,R,lson);

        else if(L>m) return query(L,R,rson);

        else return Merge(query(L,m,lson),query(m+,R,rson),tree[rt].lazy);

    }

// --------------------以上是线段树-------------------------

// --------------------以下是树链剖分-------------------------

    void dfs1(int u,int pre,int d) {

        dep[u]=d; fa[u]=pre; num[u]=;

        for(int i=head[u];i;i=e[i].ne) {

            int v=e[i].to;

            if(v!=fa[u]) {

                dfs1(v,u,d+);

                num[u]+=num[v];

                if(!son[u] || num[v]>num[son[u]])

                    son[u]=v;

            }

        }

    }

    void dfs2(int u,int sp) {

        top[u]=sp; p[u]=++pos; fp[p[u]]=w[u];

        if(!son[u]) return;

        dfs2(son[u],sp);

        for(int i=head[u];i;i=e[i].ne) {

            int v=e[i].to;

            if(v!=son[u] && v!=fa[u])

                dfs2(v,v);

        }

    }

    int solve(int x,int y,int v) {

        int fx=top[x], fy=top[y];

        TREE ans1, ans2;

        while(fx!=fy) {

            if(dep[fx]>dep[fy]) {

                ans1=Merge(query(p[fx],p[x],root),ans1,);

                update(p[fx],p[x],v,root);

                x=fa[fx];

            } else {

                ans2=Merge(query(p[fy],p[y],root),ans2,);

                update(p[fy],p[y],v,root);

                y=fa[fy];

            }

            fx=top[x], fy=top[y];

        }

        if(p[x]>p[y]) {

            ans1=Merge(query(p[y],p[x],root),ans1,);

            update(p[y],p[x],v,root);

        }

        else {

            ans2=Merge(query(p[x],p[y],root),ans2,);

            update(p[x],p[y],v,root);

        }

        int ans=max(ans1.maxr,ans2.maxl);

        if(ans1.minw) ans=max(ans,ans2.maxw-ans1.minw);

        return ans;

    }

// --------------------以上是树链剖分-------------------------

    void initQTree() {

        dfs1(,,), dfs2(,);

        build(root);

    }

}T;

int main()

{

    int t; scanf("%d",&t);

    while(t--) {

        scanf("%d",&n);

        T.init();

        for(int i=;i<=n;i++) scanf("%d",&w[i]);

        for(int i=;i<=n;i++) {

            int u,v; scanf("%d%d",&u,&v);

            T.addE(u,v); T.addE(v,u);

        }

        T.initQTree();

        scanf("%d",&q);

        while(q--) {

            int x,y,v; scanf("%d%d%d",&x,&y,&v);

            printf("%d\n",T.solve(x,y,v));

        }

    }

    return ;

}

巴特西

HDU 5052 /// 树链剖分+线段树区间合并

最新文章

热门文章