题目描述

给定长度为$n$的整数序列,你需要在数列上进行两类操作:

  1. 把$a_x$变$a_x+c$为
  2. 求$l \le i \le j \le r$中$\sum_{k=i}^{j}a_k$的最大值

题解

考虑没有修改的时候,且查询$l=1,r=n$时怎么做

1
2
3
4
for(int i = 1, ans = -inf, cur = 0 ; i <= n ; ++ i) {
cur = max(cur + a[i], a[i]);
ans = max(ans, cur);
}

贪心的维护最大且连续的值,然后更新答案对吧?

递推关系式就是

$$
\begin{cases}
cur_i=\max(cur_{i-1} + a_i,a_i) \\
ans_i=\max(ans_{i-1},cur_{i-1}+a_i,a_i)
\end{cases}
$$

也就是说

$$
\begin{pmatrix}
cur_{i-1} & ans_{i-1} & 0
\end{pmatrix}
\begin{pmatrix}
a_i & a_i & -\infty \\
-\infty & 0 & -\infty \\
a_i & a_i & 0
\end{pmatrix}
=
\begin{pmatrix}
cur_{i+1} & ans_{i+1} & 0
\end{pmatrix}
$$

其中

$$
(AB)_{ij}=\max_k A_{i,k} + B_{k,j}
$$

代码

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
#include "bits/stdc++.h"

using namespace std;

const int N = 5e5 + 10;
const int inf = 0x3f3f3f3f;

struct Mat {
int a[3][3];
Mat() { memset(a, 0xcf, sizeof a); }
int* operator [] (int x) { return a[x]; }
Mat operator * (Mat t) {
Mat ret;
for(int i = 0 ; i < 3 ; ++ i) {
for(int j = 0 ; j < 3 ; ++ j) {
for(int k = 0 ; k < 3 ; ++ k) {
ret[i][j] = max(ret[i][j], a[i][k] + t[k][j]);
}
}
}
return ret;
}
void set(int x) {
a[0][0] = x, a[0][1] = x, a[0][2] = -inf;
a[1][0] = -inf, a[1][1] = 0, a[1][2] = -inf;
a[2][0] = x, a[2][1] = x, a[2][2] = 0;
}
void output() {
for(int i = 0 ; i < 3 ; ++ i) {
for(int j = 0 ; j < 3 ; ++ j) {
printf("%d ", a[i][j]);
}
puts("");
}
}
};

Mat mat[N * 4];

#define lc (id << 1)
#define rc (id << 1 | 1)

void update(int id) { mat[id] = mat[lc] * mat[rc]; }
void build(int id, int l, int r) {
int mid = (l + r) >> 1, x;
if(l == r) mat[id].set((scanf("%d", &x), x));
else build(lc, l, mid), build(rc, mid + 1, r), update(id);
}

void modify(int id, int l, int r, int pos, int x) {
int mid = (l + r) >> 1;
if(l == r) return mat[id].set(x);
else if(pos <= mid) modify(lc, l, mid, pos, x);
else modify(rc, mid + 1, r, pos, x); update(id);
}

Mat query(int id, int l, int r, int ql, int qr) {
int mid = (l + r) >> 1;
if(ql <= l && r <= qr) return mat[id];
else if(qr <= mid) return query(lc, l, mid, ql, qr);
else if(ql >= mid + 1) return query(rc, mid + 1, r, ql, qr);
else return query(lc, l, mid, ql, mid) * query(rc, mid + 1, r, mid + 1, qr);
}

int main() {
int n, m; scanf("%d", &n);
build(1, 1, n);
scanf("%d", &m);
for(int i = 1, op, l, r, p, x ; i <= m ; ++ i) {
scanf("%d", &op);
if(op == 0) {
scanf("%d%d", &p, &x);
modify(1, 1, n, p, x);
} else {
scanf("%d%d", &l, &r);
Mat t = query(1, 1, n, l, r);
printf("%d\n", max(t[0][1], t[2][1]));
}
}
}