线性变换与矩阵递推习题：spoj GSS3

题目描述

给定长度为$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$时怎么做

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}
$$

代码

#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]));
        }
    }
}