题解：P7402 [COCI 2020/2021 #5] Sjeckanje

· · 题解

先考虑没有修改怎么做。我们注意到每一段只有最大值和最小值是有用的，并且如果我们并没有将实际上最大的选作最大值，或没有选到正确的最小值，答案一定是不优的，于是我们考虑直接钦定一个位置是否是最大值或最小值，设 f_{i, 0/1/2} 表示考虑完前 i 个元素，现在没开始一段（0）、已经选定了最大值而没选定这一段的最小值（1）、已经选定了最小值而没选定最大值（2）的最大答案。转移考虑要求这一位是不是最大值或最小值，有

f_{i, 0} = \max\{f_{i - 1, 0}, f_{i - 1, 1} - a_i, f_{i - 1, 2} + a_i\}\\ f_{i, 1} = \max\{f_{i - 1, 0} + a_i, f_{i - 1, 1}\}\\ f_{i, 2} = \max\{f_{i - 1, 0} - a_i, f_{i - 1, 2}\}\\

这显然可以用 (\max, +) 矩阵乘法刻画

\begin{bmatrix} f_{i - 1, 0} & f_{i - 1, 1} & f_{i - 1, 2} \end{bmatrix} \times \begin{bmatrix} 0 & a_i & -a_i\\ -a_i & 0 & -\infty\\ a_i & -\infty & 0\\ \end{bmatrix} = \begin{bmatrix} f_{i, 0} & f_{i, 1} & f_{i, 2} \end{bmatrix}

于是我们考虑用线段树来维护。考虑区间加的意义，如果线段树上 [l, r] 整个区间加上了 k，那么显然最大值和最小值都在区间中的段权值没有任何变化，只有其中一个加了 k 而另一个没加的才会发生变化，于是我们仅需将区间的矩阵加上

\begin{bmatrix} 0 & k & -k\\ -k & 0 & -2k\\ k & 2k & 0\\ \end{bmatrix}

这显然是可以打标记正常用线段树维护的了，时间复杂度 \mathcal{O}(k^3(n + q\log n))，其中 k = 3。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 2e5 + 10;

int n, q;
int a[maxn];

namespace segtree{
    struct Mat{
        long long mat[3][3];
        Mat(){
            mem(mat, -0x3f);
        }
        inline Mat operator * (const Mat & other) const {
            Mat res;
            for (int i = 0; i < 3; i++){
                for (int j = 0; j < 3; j++){
                    for (int k = 0; k < 3; k++){
                        res.mat[i][j] = max(res.mat[i][j], mat[i][k] + other.mat[k][j]);
                    }
                }
            }
            return res;
        }
    } res;
    struct{
        int l, r;
        long long tag;
        Mat val;
    } tree[maxn << 2];
    inline void build(int index, int l, int r){
        tree[index].l = l, tree[index].r = r;
        if (l == r){
            tree[index].val.mat[0][0] = tree[index].val.mat[1][1] = tree[index].val.mat[2][2] = 0;
            return tree[index].val.mat[0][2] = tree[index].val.mat[1][0] = -a[l], tree[index].val.mat[0][1] = tree[index].val.mat[2][0] = a[l], void();
        }
        const int mid = l + r >> 1;
        build(index << 1, l, mid), build(index << 1 | 1, mid + 1, r), tree[index].val = tree[index << 1].val * tree[index << 1 | 1].val;
    }
    inline void _add(int index, long long k){
        tree[index].val.mat[1][0] -= k, tree[index].val.mat[0][2] -= k, tree[index].val.mat[2][0] += k, tree[index].val.mat[0][1] += k;
        tree[index].val.mat[2][1] += k << 1, tree[index].val.mat[1][2] -= k << 1, tree[index].tag += k;
    }
    inline void pushdown(int index){
        _add(index << 1, tree[index].tag), _add(index << 1 | 1, tree[index].tag), tree[index].tag = 0;
    }
    inline void add(int index, int l, int r, int k){
        if (l <= tree[index].l && r >= tree[index].r){
            return _add(index, k);
        }
        pushdown(index);
        const int mid = tree[index].l + tree[index].r >> 1;
        l <= mid && (add(index << 1, l, r, k), 1538), r > mid && (add(index << 1 | 1, l, r, k), 1538), tree[index].val = tree[index << 1].val * tree[index << 1 | 1].val;
    }
}

using namespace segtree;

int main(){
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    build(1, 1, n);
    while (q--){
        int l, r, k;
        scanf("%d %d %d", &l, &r, &k), add(1, l, r, k), res = Mat(), res.mat[0][0] = 0, res = res * tree[1].val, printf("%lld\n", res.mat[0][0]);
    }

return 0;
}