# 题目大意
GSS3 - Can you answer these queries III
需要你维护一种数据结构，支持两种操作：
单点修改求一个区间的最大子段和
# 解题思路
一个区间的最大子段和(GSS)，只能通过三种方式转移而来。
左儿子的最大子段和右儿子的最大子段和左儿子的最大右子段和+右儿子的最大左子段和
那这就比较好办了。只需要维护四个东西就可以了
sum，区间和gss，最大子段和gssl，最大左子段和gssr，最大右子段和
emmm，比较可做。
# 代码
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
inline int read() {
int x =
0, f =
1;
char c =
getchar();
while (c <
'0' || c >
'9') {
if(c ==
'-') f = -
1; c =
getchar();}
while (c <=
'9' && c >=
'0') {x = x*
10 + c-
'0'; c =
getchar();}
return x *
f;
}
const int maxn = 5e4+
3, inf =
2147483647;
int n, m, opt, l, r;
struct node {
int l, r, gss, gssr, gssl, sum;
}tree[maxn <<
2];
struct TREE {
#define Lson (k << 1)
#define Rson ((k << 1) + 1)
inline int MAX(
int a,
int b,
int c) {
return max(max(a, b), c);
}
inline void build(
int k,
int ll,
int rr) {
tree[k].l = ll, tree[k].r =
rr;
if(tree[k].l ==
tree[k].r) {
tree[k].sum =
read();
tree[k].gss = tree[k].gssr = tree[k].gssl =
tree[k].sum;
return ;
}
int mid = (tree[k].l + tree[k].r) >>
1;
build (Lson, tree[k].l, mid);
build (Rson, mid+
1, tree[k].r);
tree[k].sum = tree[Lson].sum +
tree[Rson].sum;
tree[k].gss = MAX(tree[Lson].gss, tree[Rson].gss, tree[Lson].gssr+
tree[Rson].gssl);
tree[k].gssr = max(tree[Rson].gssr, tree[Rson].sum+
tree[Lson].gssr);
tree[k].gssl = max(tree[Lson].gssl, tree[Lson].sum+
tree[Rson].gssl);
}
inline void update(
int k,
int pos,
int num) {
if(tree[k].l == tree[k].r && tree[k].l ==
pos) {
tree[k].sum =
num;
tree[k].gss = tree[k].gssr = tree[k].gssl =
tree[k].sum;
return ;
}
int mid = (tree[k].l + tree[k].r) >>
1;
if(pos <=
mid) update(Lson, pos, num);
else update(Rson, pos, num);
tree[k].sum = tree[Lson].sum +
tree[Rson].sum;
tree[k].gss = MAX(tree[Lson].gss, tree[Rson].gss, tree[Lson].gssr+
tree[Rson].gssl);
tree[k].gssr = max(tree[Rson].gssr, tree[Rson].sum+
tree[Lson].gssr);
tree[k].gssl = max(tree[Lson].gssl, tree[Lson].sum+
tree[Rson].gssl);
}
inline node query(int k,
int L,
int R) {
if(tree[k].l == L && tree[k].r == R)
return tree[k];
int mid = (tree[k].l + tree[k].r) >>
1;
if(L > mid)
return query(Rson, L, R);
else if(R <= mid)
return query(Lson, L, R);
else {
node lson, rson, res;
lson =
query(Lson, L, mid);
rson = query(Rson, mid+
1, R);
res.sum = lson.sum +
rson.sum;
res.gss = MAX(lson.gss, rson.gss, lson.gssr+
rson.gssl);
res.gssl = max(lson.gssl, lson.sum+
rson.gssl);
res.gssr = max(rson.gssr, rson.sum+
lson.gssr);
return res;
}
}
}T;
int main() {
n = read(), T.build(
1,
1, n);
m =
read();
for(
int i=
1; i<=m; i++
) {
opt = read(), l = read(), r =
read();
if(opt ==
1) printf(
"%d\n", T.query(
1, l, r).gss);
else T.update(
1, l, r);
}
}
转载于:https://www.cnblogs.com/bljfy/p/9749572.html
相关资源：数据结构—成绩单生成器
