Pre
太棒了，今天早上的努力总算没有白费。
顺便说一句，本文内容简单，只是动态(DP)的基本原理(而且还不全)，神犇请避让，否则会浪费时间。
原来矩阵乘法还有这么奇葩的坑(还是我太大意了)，我是小看它了(话说之前有一次考试我也是用的线段树维护矩阵乘法，貌似当时代码与自己的本意不符，但是恰好是这个错误让程序违背了我的本意，最后(A)了，我真幸运!!!^_^)
Solution
动态(DP)的基本原理我就不推导了，主要提醒一下坑，在(Conclusion)里面，这里说一下我构造的矩阵。
[left[
egin{matrix}
0 & v_i & v_i\
-infty & v_i & v_i\
-infty & -infty & 0
end{matrix}
ight]
]
用来计算答案的矩阵是
[left[
egin{matrix}
f_{i-1}\
g_{i-1}\
0
end{matrix}
ight]
]
其中的(f_i)表示在范围([0,i])中的最大子段和(准确的说是从询问操作的开头到(i)的最大字段和)。
其中的(g_i)表示强制性以(i)为结尾，并且开始地方不得小于询问操作的左端点的最大子段和。
用上面的乘以下面的。
Code
#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
const int N = 50000 + 5;
struct Matrix {
int info[4][4];
Matrix () {
for (int i = 1; i <= 3; ++i) {
for (int j = 1; j <= 3; ++j) {
info[i][j] = INT_MIN;
}
}
}
inline void init (int u, int v, int w) {
info[1][1] = u;
info[2][1] = v;
info[3][1] = w;
for (int i = 1; i <= 3; ++i) {
info[i][3] = info[i][2] = info[i][1];
}
}
inline void stt (int a1, int a2, int a3, int a4, int a5, int a6, int a7, int a8, int a9) {
info[1][1] = a1;
info[1][2] = a2;
info[1][3] = a3;
info[2][1] = a4;
info[2][2] = a5;
info[2][3] = a6;
info[3][1] = a7;
info[3][2] = a8;
info[3][3] = a9;
}
Matrix operator * (Matrix x) {
Matrix res;
for (int k = 1; k <= 3; ++k) {
for (int j = 1; j <= 3; ++j) {
for (int i = 1; i <= 3; ++i) {
if (info[i][k] == INT_MIN || x.info[k][j] == INT_MIN) {
continue;
}
res.info [i][j] = max (res.info[i][j], info[i][k] + x.info[k][j]);
}
}
}
return res;
}
inline void print () {
for (int i = 1; i <= 3; ++i) {
for (int j = 1; j <= 3; ++j) {
printf ("%d ", info[i][j]);
}
printf ("
");
}
}
}st;
int v[N], n, m;
struct Tree {
Matrix sum[N << 1];
int lson[N << 1], rson[N << 1], l[N << 1], r[N << 1], tot;
inline void push_up (int u) {
sum[u] = sum[rson[u]] * sum[lson[u]];
}
inline void build (int fr, int to) {
tot++;
int now = tot;
l[now] = fr;
r[now] = to;
if (fr == to) {
sum[now].stt (0, v[fr], v[fr], INT_MIN, v[fr], v[fr], INT_MIN, INT_MIN, 0);
return ;
}
int mid = (fr + to) / 2;
lson[now] = tot + 1;
build (fr, mid);
rson[now] = tot + 1;
build (mid + 1, to);
push_up (now);
}
inline void update (int fr, int p) {
if (l[p] == r[p]) {
sum[p].stt (0, v[fr], v[fr], INT_MIN, v[fr], v[fr], INT_MIN, INT_MIN, 0);
return ;
}
int mid = (l[p] + r[p]) / 2;
if (fr <= mid) {
update (fr, lson[p]);
}
else {
update (fr, rson[p]);
}
push_up (p);
}
Matrix query (int fr, int to, int p) {
if (fr <= l[p] && to >= r[p]) {
return sum[p];
}
int mid = (l[p] + r[p]) / 2;
if (to <= mid) {
return query (fr, to, lson[p]);
}
else if (fr > mid) {
return query (fr, to, rson[p]);
}
else {
return query (fr, to, rson[p]) * query (fr, to, lson[p]);
}
}
}tree;
inline void solve (int x, int y) {
if (x == y) {
printf ("%d
", v[x]);
return ;
}
else {
Matrix st;
st.init (v[x], v[x], 0);
Matrix tmp = tree.query (x + 1, y, 1);
Matrix ans = tmp * st;
printf ("%d
", ans.info[1][1]);
}
}
int main () {
scanf ("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf ("%d", &v[i]);
}
tree.build (1, n);
int m;
scanf ("%d", &m);
for (int i = 1; i <= m; ++i) {
int opt, x, y;
scanf ("%d%d%d", &opt, &x, &y);
if (!opt) {
v[x] = y;
tree.update (x, 1);
}
else {
solve (x, y);
}
}
return 0;
}
Conclusion
具体来讲一下我觉得坑的地方。
如果需要进行一次转移，那么
假设(M_a)表示位置在(a)的(DP)矩阵，(st)表示转移矩阵。
那么计算(st)从(i-1)转移到(i+1)顺序
1、(st=M_i*st)
2、(st=M_{i+1}*st)
也就是
(st=M_{i+1}*(M_i*st))
于是我就直接线段树维护区间了。
但是实际上展开之后是(st=M_{i+1}*M_i*st)
考虑到矩阵乘法没有交换律，我们需要在(push\_up)和(query)里面交换左右儿子的顺序。
也就是倒着乘。
总之，注意要把式子看清楚再打代码。。。