题解：P7402 [COCI2020-2021#5] Sjeckanje

结论是**每个划分的区间都单调**最优。

考虑差分。令 $b_i = a_i - a_{i-1}$。那么一个区间 $[l, r]$ 单调，等价于 $b_{l+1} \dots b_r$ 同号。此时对答案的贡献是 $\sum_{i=l+1}^r |b_i|$。

注意这里并没有把 $b_l$ 算进去。也就是说，如果一段区间 $[x,y]$ 被划分成了 $[x,m-1],[m,y]$，那么贡献是 $\sum_{i=x+1}^y |b_i| - |b_m|$。

于是得到了这样一个问题：

- 要求从 $b_2 \dots b_n$ 中选若干个数，使得相邻的两个数同号，并最大化选择的数的绝对值的和。

（这里一个数被选，等价于它不是划分的区间的左端点。）

（两个选择的数相邻就代表它们被划分到了同一个区间内。而同一个区间内的数应同号。）

别忘了还有 $q$ 次修改。因为是差分数组所以是单点修改。这启发我们往线段树上考虑。

我们尝试用线段树维护这个区间内选数的最大答案。发现合并（pushup）区间 $[l,mid],[mid+1,r]$ 时，我们需要知道 $mid,mid+1$ 是否**同时选择**。于是线段树的节点上维护四个值 $v_{0/1,0/1}$，表示左/右端点选/不选的最大答案。这样上传就能做了。

```cpp
// Problem: 
//     P7402 [COCI2020-2021#5] Sjeckanje
//   
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7402
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// #define tests
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10;

int n, q;
int a[N], b[N];

bool chk(int x, int y) {
	if (!x || !y) return true;
	return (x > 0) == (y > 0);
}

struct Tree {
	struct Node {
		int l, r;
		int v[2][2];
	}tr[N << 2];
	
	void pushup(int u) {
		for (int i : {0, 1}) for (int j : {0, 1})
			tr[u].v[i][j] = max({
				tr[u << 1].v[i][0] + tr[u << 1 | 1].v[0][j],
				tr[u << 1].v[i][0] + tr[u << 1 | 1].v[1][j],
				tr[u << 1].v[i][1] + tr[u << 1 | 1].v[0][j]
			});
		
		if (chk(b[tr[u << 1].r], b[tr[u << 1 | 1].l])) {
			for (int i : {0, 1}) for (int j : {0, 1})
				tr[u].v[i][j] = max(tr[u].v[i][j], tr[u << 1].v[i][1] + tr[u << 1 | 1].v[1][j]);
		}
	}
	
	void build(int u, int l, int r) {
		tr[u].l = l, tr[u].r = r;
		if (l == r) {
			tr[u].v[0][0] = 0;
			tr[u].v[1][1] = abs(b[l]);
			tr[u].v[0][1] = tr[u].v[1][0] = -2e9;
		} else {
			int mid = l + r >> 1;
			build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
			pushup(u);
		}
	}
	
	void modify(int u, int x) {
		if (tr[u].l == tr[u].r) {
			tr[u].v[1][1] = abs(b[x]);
		} else {
			int mid = tr[u].l + tr[u].r >> 1;
			if (x <= mid) modify(u << 1, x);
			else modify(u << 1 | 1, x);
			pushup(u);
		}
	}
}T;

void solve() {
	cin >> n >> q;
	
	for (int i = 1; i <= n; ++ i ) {
		cin >> a[i];
		b[i] = a[i] - a[i - 1];
	}
	
	if (n >= 2) T.build(1, 2, n);
	while (q -- ) {
		int l, r, x;
		cin >> l >> r >> x;
		b[l] += x, b[r + 1] -= x;
		if (l >= 2) T.modify(1, l);
		if (r + 1 <= n) T.modify(1, r + 1);
		cout << max({T.tr[1].v[0][0], T.tr[1].v[0][1], T.tr[1].v[1][0], T.tr[1].v[1][1]}) << '\n';
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T = 1;
#ifdef tests
	cin >> T;
#endif
	while (T -- ) solve();
	return 0;
}
```

正在渲染内容...