「SPOJ 6779」GSS7 - Can you answer these queries VII

发表于 | | 阅读次数:
字数统计: 1.1k 字

Description

题目链接：SPOJ 6779

给你一棵有 $n$ 个节点的树，每个点有一个权值 $x_i$。接下来有 $Q$ 个操作，操作分为以下 $2$ 种：

  • 1 a b：求出 $a$ 到 $b$ （包括 $a$ 和 $b$）这条路径上的权值组成的序列的最大子段和（可以为空）。
  • 2 a b c：将 $a$ 到 $b$（包括 $a$ 和 $b$）的路径上的所有点的权值改为 $c$。

数据范围：$n,Q\le 10^5$，$|x_i|,|c|\le 10^4$

Solution

我们可以用树链剖分来维护这棵树，修改时直接在线段树上覆盖。询问时，我们根据树链剖分的过程，可以发现只不过是把这条链拆成了若干段，那么我们可以对这几段依次查询、维护、更新答案。

关于如何用线段树维护序列的最大子段和（这个方法很套路），详见「SPOJ 1716」GSS3 - Can you answer these queries III。

时间复杂度：$O(Q\log^2 n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson rt<<1
#define rson rt<<1|1

const int N=1e5+5,M=2e5+5;
int n,q,tot,x[N],lnk[N],ter[M],nxt[M];
int idx,dfn[N],seq[N],sz[N],dep[N],hvy[N],top[N],fa[N];
struct Node {
    int sum,lmx,rmx,ret,tag;
    bool cov;
    Node() {sum=lmx=rmx=ret=0;}
}seg[N<<2];

void add(int u,int v) {
    ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot;
}
void dfs1(int u,int f) {
    dep[u]=dep[f]+1,fa[u]=f,sz[u]=1;
    for(int i=lnk[u];i;i=nxt[i]) {
        int v=ter[i];
        if(v==f) continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[hvy[u]]) hvy[u]=v;
    }
}
void dfs2(int u,int tp) {
    dfn[u]=++idx,seq[idx]=u,top[u]=tp;
    if(!hvy[u]) return;
    dfs2(hvy[u],tp);
    for(int i=lnk[u];i;i=nxt[i]) {
        int v=ter[i];
        if(v==fa[u]||v==hvy[u]) continue;
        dfs2(v,v);
    }
}
Node merge(Node x,Node y) {
    Node ans;
    ans.sum=x.sum+y.sum;
    ans.lmx=std::max(x.lmx,x.sum+y.lmx);
    ans.rmx=std::max(y.rmx,y.sum+x.rmx);
    ans.ret=std::max(std::max(x.ret,y.ret),x.rmx+y.lmx);
    ans.tag=ans.cov=0;
    return ans;
}
void build(int rt,int l,int r) {
    if(l==r) {
        seg[rt].sum=x[seq[l]];
        seg[rt].lmx=seg[rt].rmx=seg[rt].ret=std::max(seg[rt].sum,0);
        seg[rt].cov=0;
        return;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    seg[rt]=merge(seg[lson],seg[rson]);
}
void update(int rt,int l,int r,int k) {
    seg[rt].sum=(r-l+1)*k;
    seg[rt].lmx=seg[rt].rmx=seg[rt].ret=std::max(seg[rt].sum,0);
    seg[rt].cov=1,seg[rt].tag=k;
}
void pushdown(int rt,int l,int r) {
    if(!seg[rt].cov) return;
    int mid=(l+r)>>1;
    update(lson,l,mid,seg[rt].tag);
    update(rson,mid+1,r,seg[rt].tag);
    seg[rt].tag=seg[rt].cov=0;
}
void modify(int x,int y,int rt,int l,int r,int k) {
    if(x<=l&&r<=y) {
        update(rt,l,r,k);
        return;
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    if(x<=mid) modify(x,y,lson,l,mid,k);
    if(mid<y) modify(x,y,rson,mid+1,r,k);
    seg[rt]=merge(seg[lson],seg[rson]);
}
Node query(int x,int y,int rt,int l,int r) {
    if(x<=l&&r<=y) return seg[rt];
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    Node L,R;
    if(x<=mid) L=query(x,y,lson,l,mid);
    if(mid<y) R=query(x,y,rson,mid+1,r);
    return merge(L,R);
}
void chainModify(int u,int v,int k) {
    for(int fu=top[u],fv=top[v];fu^fv;u=fa[fu],fu=top[u]) {
        if(dep[fu]<dep[fv]) std::swap(u,v),std::swap(fu,fv);
        modify(dfn[fu],dfn[u],1,1,n,k);
    }
    if(dep[u]>dep[v]) std::swap(u,v);
    modify(dfn[u],dfn[v],1,1,n,k);
}
Node chainQuery(int u,int v) {
    Node L,R;
    for(int fu=top[u],fv=top[v];fu^fv;) {
        if(dep[fu]<dep[fv]) {
            R=merge(query(dfn[fv],dfn[v],1,1,n),R);
            v=fa[fv],fv=top[v];
        } else {
            L=merge(query(dfn[fu],dfn[u],1,1,n),L);
            u=fa[fu],fu=top[u];
        }
    }
    if(dep[u]>dep[v]) {
        L=merge(query(dfn[v],dfn[u],1,1,n),L);
    } else {
        R=merge(query(dfn[u],dfn[v],1,1,n),R);
    }
    std::swap(L.lmx,L.rmx);
    return merge(L,R);
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&x[i]);
    for(int i=1;i<n;++i) {
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    dfs1(1,0),dfs2(1,1),build(1,1,n);
    scanf("%d",&q);
    while(q--) {
        int opt;
        scanf("%d",&opt);
        if(opt==1) {
            int l,r;
            scanf("%d%d",&l,&r);
            printf("%d\n",chainQuery(l,r).ret);
        } else {
            int l,r,k;
            scanf("%d%d%d",&l,&r,&k);
            chainModify(l,r,k);
        }
    }
    return 0;
}
0%