Peoblem’s Website
- 小白逛公园
Solution
- 通过读题，我们不难得出要求一段序列的最大子段和，并且还要支持单点修改，那么线段树无疑是最佳的做法。
基础的单点修改就不说了，说一下要维护的标记以及标记上传。
v表示当前区间的和
maxl表示当前区间必须包含最左端的数的最大子段和
maxr表示当前区间必须包含最右端的数的最大子段和
maxv表示整段区间的最大子段和
对于pushup，v直接把左右儿子的v加起来，maxl则是要对左儿子的v+右儿子的maxl取max，同理，maxr要对右儿子的v+左儿子的maxr取max,maxv要对左儿子和右儿子的maxv以及左儿子的maxr与右儿子的maxl之和取最大值，可能说的有点乱，
但还是比较好理解的。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
using namespace std;
const int Maxn = 500010;
int sc() {
int xx = 0, ff = 1; char cch = gc;
while (cch < '0' || cch > '9') {
if (cch == '-') ff = -1; cch = gc;
}
while (cch >= '0' && cch <= '9') {
xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
}
return xx * ff;
}
struct TREE {
int v, maxl, maxr, maxv;
}tree[Maxn << 2];
int n, m;
int a[Maxn];
void pushup(int k, int l, int r) {
tree[k].v = tree[l].v + tree[r].v;
tree[k].maxl = max(tree[l].maxl, tree[l].v + tree[r].maxl);
tree[k].maxr = max(tree[r].maxr, tree[r].v + tree[l].maxr);
tree[k].maxv = max(max(tree[l].maxv, tree[r].maxv), tree[l].maxr + tree[r].maxl);
// cout << tree[k].maxv << endl;
}
void build(int k, int l, int r) {
if(l == r) {
tree[k].v = tree[k].maxl = tree[k].maxr = tree[k].maxv = a[l];
return ;
}
int mid = l + r >> 1;
build(k << 1, l, mid);
build(k << 1 | 1, mid + 1, r);
pushup(k, k << 1, k << 1 | 1);
}
void modify(int k, int l, int r, int id, int num) {
// cout << l << " " << r << endl;
if(l == r) {
tree[k].v = tree[k].maxl = tree[k].maxr = tree[k].maxv = num;
return ;
}
int mid = l + r >> 1;
if(id <= mid) modify(k << 1, l, mid, id, num);
else modify(k << 1 | 1, mid + 1, r, id, num);
pushup(k, k << 1, k << 1 | 1);
}
TREE query(int k,int l, int r, int x, int y) {
// cerr << l << " " << r << endl;
if(x <= l && y >= r)
return tree[k];
int mid = l + r >> 1;
if(y <= mid) return query(k << 1, l, mid, x, y);
else if(x > mid) return query(k << 1 | 1, mid + 1, r, x, y);
else {
TREE d, d1 = query(k << 1, l, mid, x, y), d2 = query(k << 1 | 1, mid + 1, r, x, y);
// cout << d1.v << " " << d1.maxl << " " << d1.maxr << " " << d1.maxv << endl;
d.maxl = max(d1.maxl, d1.v + d2.maxl);
d.maxr = max(d2.maxr, d2.v + d1.maxr);
d.maxv = max(max(d1.maxv, d2.maxv), d1.maxr + d2.maxl);
// cout << d1.maxv << endl;
return d;
}
}
int main() {
n = sc(); m = sc();
for(int i = 1; i <= n; i++)
a[i] = sc();
build(1, 1, n);
while(m--) {
int flag = sc();
if(flag == 1) {
int x = sc(), y = sc();
if(x > y) swap(x, y);
printf("%d\n", query(1, 1, n, x, y).maxv);
}
else {
int x = sc(), num = sc();
modify(1, 1, n, x, num);
}
}
return 0;
}
rp++