「SPOJ 1716」GSS3 - Can you answer these queries III

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

Description

题目链接：SPOJ 1716

维护一个长度为 $n$ 的序列 $A$，进行 $m$ 次询问或操作：

  • 0 x y：将 $A_x$ 单调修改为 $y$
  • 1 x y：求出 $\max\{\sum_{k=i}^j A_k\}(x\le i\le j\le y)$。

数据范围：$N,M\le 5\times 10^4$，$|A_i|\le 10^4$

Solution

首先分析询问的本质：求出区间最大子段和！

很显然我们可以使用线段树维护序列，本题的难点主要在如何进行上传操作，即$\text{push up}$。

将子树 $l$ 和 $r$ 的节点信息上传到子树 $rt$ 时，对于 $rt$ 维护的序列中，和最大的子段有两种情况：

  1. 子段不经过中点，那么 $rt$ 的答案为 $l$ 和 $r$ 的答案的最大值。

  2. 子段经过了中点。这种情况比较复杂，因为我们无法知道子树的答案所对应的序列。这也是本题的难点所在。

接下来对第 $2$ 种情况进行重点分析：

我们记 $res$ 为区间最长子段和，$sum$ 为区间和，$prel$ 和 $prer$ 分别表示从区间左端点和右端点开始的最大子段和。

考虑这些信息如何上传：$sum$ 可以直接上传，$prel[rt]=\max(prel[l],sum[l]+prel[r])$（$prer$ 同理），$res[rt]=\max(res[l],res[r],prer[l]+prel[r])$

时间复杂度：$O(m\log 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
#include <cstdio>
#include <algorithm>
#define lson rt<<1
#define rson rt<<1|1
using std::max;
const int N=5e4+5;
int n,m,a[N];

struct Tree {
    int prel,prer,res,sum;
}seg[N<<2];

void pushup(int rt) {
    Tree L=seg[lson],R=seg[rson];
    seg[rt].sum=L.sum+R.sum;
    seg[rt].prel=max(L.prel,L.sum+R.prel);
    seg[rt].prer=max(R.prer,R.sum+L.prer);
    seg[rt].res=max(L.prer+R.prel,max(L.res,R.res));
}
void build(int rt,int l,int r) {
    if(l==r) {
        seg[rt].prel=seg[rt].prer=seg[rt].res=seg[rt].sum=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
    pushup(rt);
}
void modify(int x,int rt,int l,int r,int val) {
    if(l==r) {
        seg[rt].prel=seg[rt].prer=seg[rt].res=seg[rt].sum=val;
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) modify(x,lson,l,mid,val);
    else modify(x,rson,mid+1,r,val);
    pushup(rt);
}
Tree query(int x,int y,int rt,int l,int r) {
    if(x<=l&&r<=y) return seg[rt];
    int mid=(l+r)>>1;
    if(y<=mid) return query(x,y,lson,l,mid);
    if(mid<x) return query(x,y,rson,mid+1,r);
    Tree L=query(x,mid,lson,l,mid),R=query(mid+1,y,rson,mid+1,r),res;
    res.sum=L.sum+R.sum;
    res.prel=max(L.prel,L.sum+R.prel);
    res.prer=max(R.prer,R.sum+L.prer);
    res.res=max(L.prer+R.prel,max(L.res,R.res));
    return res;
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    build(1,1,n);
    for(scanf("%d",&m);m--;) {
        int opt,x,y;
        scanf("%d%d%d",&opt,&x,&y);
        if(opt) printf("%d\n",query(x,y,1,1,n).res);
        else modify(x,1,1,n,y);
    }
    return 0;
}
0%