原题机！！～赤到真石的模拟赛不寻找原题并非撑不下去！

· · 题解

宝宝 ds。

若只考虑静态。性质：分段方案中每一段均单调。注意到如果一段分段不单调，那么把他按最值切割一定不劣。

那么有一个 naive 的 dp，记 f_{i,0/1/2} 为处理完前 i 个数，当前这一段单调递增且未结束，单调递减且未结束，结束于此的答案。转移 trivial。

观察到转移式中包含 a_i，不方便处理一段区间加法的贡献，所以考虑换一种方式转移：我们发现一段递增区间的贡献可以转化为，区间首位不贡献，其他位置贡献 a_i-a_{i-1}，递减同理，所以我们设 f_{i,0/1} 为处理完前 i 位，当前段递增或递减，转移也是简单的：

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

会发现这样转移的贡献是一个差分状物，区间修改对一个区间内部的差分毫无影响，所以可以上线段树直接维护。对每个区间记录信息 (l,r,g_{0/1,0/1})，分别表示区间首尾元素，区间内部处理完，并且首位状态递增或递减，末位状态递增或递减的答案，合并类似上述转移，区间加法只对 l,r 信息存在修改，然后做完了。时间复杂度 O(q\log n)，带个 2^4 合并的常数，循环展开一下跑的飞快。

#include <bits/stdc++.h>
#define uint unsigned int
#define ull unsigned long long
#define LL long long
using namespace std;
const int N = 2e5 + 10;
const LL inf = 1e18;
int n, Q, A[N];

struct Node { LL l, r, res[2][2]; } tr[N << 2]; LL tag[N << 2];
const Node operator+(const Node& a, const Node& b) {
    Node c = {a.l, b.r, {{-inf, -inf}, {-inf, -inf}}};
    for (int j = 0; j < 2; j ++) for (int p = 0; p < 2; p ++) {
        LL w = max(0ll, (j == p ? (j ? b.l - a.r : a.r - b.l) : 0));
        c.res[0][0] = max(c.res[0][0], a.res[0][j] + b.res[p][0] + w);
        c.res[0][1] = max(c.res[0][1], a.res[0][j] + b.res[p][1] + w);
        c.res[1][0] = max(c.res[1][0], a.res[1][j] + b.res[p][0] + w);
        c.res[1][1] = max(c.res[1][1], a.res[1][j] + b.res[p][1] + w);
    } return c;
}
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
void build(int p, int l, int r) {
    if (l == r) {
        tr[p].l = tr[p].r = A[l]; tr[p].res[0][1] = tr[p].res[1][0] = -1e18; return ;
    } int mid = (l + r) >> 1;
    build(ls(p), l, mid); build(rs(p), mid + 1, r); tr[p] = tr[ls(p)] + tr[rs(p)];
    return ;
}
void f(int p, LL k) { tr[p].l += k; tr[p].r += k; tag[p] += k; }
void pushdown(int p) { if (tag[p]) f(ls(p), tag[p]), f(rs(p), tag[p]), tag[p] = 0; }
void update(int p, int l, int r, int x, int y, int k) {
    if (x > r || y < l) return ;
    if (x <= l && y >= r) { f(p, k); return ; }
    int mid = (l + r) >> 1; pushdown(p);
    update(ls(p), l, mid, x, y, k); update(rs(p), mid + 1, r, x, y, k);
    tr[p] = tr[ls(p)] + tr[rs(p)]; return ;
}

int main() {
    freopen(".in", "r", stdin); freopen(".out", "w", stdout);
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> Q;
    for (int i = 1; i <= n; i ++) cin >> A[i];
    build(1, 1, n); int x, y, k;
    while (Q --) {
        cin >> x >> y >> k; update(1, 1, n, x, y, k);
        cout << max({tr[1].res[0][0], tr[1].res[0][1], tr[1].res[1][0], tr[1].res[1][1]}) << "\n";
    }
    return 0;
}