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

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%