Geiz-Revive > SP1716-GSS3

SP1716-GSS3

2019-08-03

动态dp

题意就是要求区间最大子段和，带修。

维护前缀最大和后缀最大的思路由前几个GSS系列的题继承过来就行了，这里讲一点有意思的东西。

因为最近刚好在学习动态dp，这题正好也算是个典型，就又做了一遍。

动态dp是把正常的状态转移方程转化成矩阵的形式，然后用数据结构维护矩阵的连乘积。当然这里的矩阵乘法不是正常的矩阵乘法，重定义后的矩乘长这个亚子：

1
2
3
4
5
6
7
8
9
10
11
12
13
struct matrix{
    ...
};
matrix operator* (matrix a,matrix b){
    matrix c;
    for(int i...){
        for(int j...){
            for(int k...){
                c[i][j]=max(c[i][j],a[i][k]+b[k][j]);
            }
        }
    }
}

也就是把乘变成了加，把加变成了取$max$

最大子段和的状态转移方程大概是这样的：

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

所以我们构造出的矩阵长这样:

$\left( \begin{matrix} tmp_{i-1}&ans_{i-1}&0\end{matrix} \right)\left( \begin{matrix}a_i&a_i&-inf\ -inf&0&-inf\ a_i&a_i&0\end{matrix} \right) = \left( \begin{matrix} tmp_{i}&ans_{i}&0\end{matrix} \right)$

我们只要用线段树维护这个矩阵的连乘积：$\left( \begin{matrix}a_i&a_i&-inf\ -inf&0&-inf\ a_i&a_i&0\end{matrix} \right)$

每次修改把四个$a_i$全部改掉，然后$pushup$就好了。

$\Large 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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#pragma region revive
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define inl inline
#define re register int
#define fa(x) fa[x]
#define son(x, y) t[x].child[y]
#define ls(x) child[x][0]
#define rs(x) child[x][1]
#define ll long long
const int inf = 0x3f3f3f3f;
#define lowbit(x) ((x) & (-x))
using namespace std;
#ifndef _DEBUG
#define getchar() (*(IOB.in.p++))
#define putchar(c) (*(IOB.out.p++) = (c))
#define io_eof() (IOB.in.p >= IOB.in.pend)
struct IOBUF {
	struct {
		char buff[1 << 26], *p, *pend;
	} in;
	struct {
		char buff[1 << 26], *p;
	} out;
	IOBUF() {
		in.p = in.buff;
		out.p = out.buff;
		in.pend = in.buff + fread(in.buff, 1, 1 << 27, stdin);
	}
	~IOBUF() { fwrite(out.buff, 1, out.p - out.buff, stdout); }
} IOB;
#endif
template <typename IO>
inl void write(IO x) {
	if (x == 0) return (void)putchar('0');
	if (x < 0) putchar('-'), x = -x;
	static char buf[30];
	char *p = buf;
	while (x) {
		*(p++) = x % 10 + '0';
		x /= 10;
	}
	while (p > buf)
		putchar(*(--p));
}
inl void writestr(const char *s) {
	while (*s != 0)
		putchar(*(s++));
}
template <typename IO>
inl void writeln(IO x) { write(x), putchar('\n'); }
template <typename IO>
inl void writesp(IO x) { write(x), putchar(' '); }
inl int readstr(char *s) {
	char *begin = s, c = getchar();
	while (c < 33 || c > 127) {
		c = getchar();
	}
	while (c >= 33 && c <= 127) {
		*(s++) = c;
		c = getchar();
	}
	*s = 0;
	return s - begin;
}
template <typename IO>
inl IO read() {
	IO x = 0;
	register bool w = 0;
	register char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-') w = 1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar();
	}
	return w ? -x : x;
}
template<>
inl double read<double>() {
	double x = 0;
	int w = 0, y = 0;
	ll z = 1;
	register char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-') w = 1;
		c = getchar();
	}
	while (c >= '0' && c <= '9' || c == '.') {
		if (c == '.') {
			y = 1, c = getchar();
			continue;
		}
		x = x * 10 + (c ^ 48);
		if (y)z *= 10;
		c = getchar();
	}
	return (w ? -x : x) / z;
}
#pragma endregion
struct matrix {
	int a[3][3];
	matrix() { a[0][0] = a[0][1] = a[0][2] = a[1][0] = a[1][1] = a[1][2] = a[2][0] = a[2][1] = a[2][2] = -inf; }
	matrix(bool x) { a[0][0] = a[1][1] = a[2][2] = 0, a[0][1] = a[0][2] = a[1][0] = a[1][2] = a[2][0] = a[2][1] = -inf; }
	inl int *operator[](int x) { return a[x]; }
	inl const int *operator[](int x) const { return a[x]; }
	friend matrix operator*(const matrix &a, const matrix &b) {
		matrix c;
		for (re i = 0; i < 3; i++) {
			for (re j = 0; j < 3; j++) {
				for (re k = 0; k < 3; k++) {
					c[i][j] = max(c[i][j], a[i][k] + b[k][j]);
				}
			}
		}
		return c;
	}
	inl int getmax() { return max(a[0][1], a[2][1]); }
}t[200001];
inl void upd(int k) {
	t[k] = t[k << 1] * t[k << 1 | 1];
}
inl void build(int k, int l, int r) {
	if (l == r) return (void)(t[k][0][0] = t[k][0][1] = t[k][2][0] = t[k][2][1] = read<int>(), t[k][1][1] = t[k][2][2] = 0);
	re mid = l + r >> 1;
	build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
	upd(k);
}
inl void change(int k, int l, int r, int p, int w) {
	if (l == r)return (void)(t[k][0][0] = t[k][0][1] = t[k][2][0] = t[k][2][1] = w);
	re mid = l + r >> 1;
	if (p <= mid)change(k << 1, l, mid, p, w);
	else change(k << 1 | 1, mid + 1, r, p, w);
	upd(k);
}
inl matrix query(int k, int l, int r, int x, int y) {
	if (l >= x && r <= y)return t[k];
	re mid = l + r >> 1;
	matrix ans = matrix(0);
	if (x <= mid)ans = ans * query(k << 1, l, mid, x, y);
	if (y > mid)ans = ans * query(k << 1 | 1, mid + 1, r, x, y);
	return ans;
}
signed main() {
	re n = read<int>(), m, op, x, y;
	build(1, 1, n);
	m = read<int>();
	while (m--) {
		op = read<int>(), x = read<int>(), y = read<int>();
		if (op) {
			writeln(query(1, 1, n, x, y).getmax());
		}
		else {
			change(1, 1, n, x, y);
		}
	}
}