学。
题意：区间推平，区间加，区间极值，区间历史极值。
- 区间加区间历史最大值
试图在每个节点维护操作序列，这样答案一定是正确的。
具体而言，维护加标记和赋值标记，维护历史最大值 \(mx\) 和当前值 \(x\)，标记形如 \(x \gets x + t\) 或 \(mx \gets \max(mx, x)\)。
对所有加标记做前缀和，则维护赋值标记相当于维护前缀和序列的极值。发现存前缀和的最后一项就可以维护在后面加入数字这一个操作了。
因此，在每个节点维护两个标记，表示前缀和序列的极值，以及前缀和序列的最后一项（其实就是当前值）。合并是显然的。
- 矩乘做区间加区间历史极值
https://www.luogu.com.cn/blog/502410/seg-hismax-matrix-tag-p4314
在每个节点维护标记 \(\begin{bmatrix} a \\ b\end{bmatrix}\)，分别为当前值与历史极值。使用广义矩乘，$ \begin{bmatrix} k & -\infty \ k & 0 \end{bmatrix} \begin{bmatrix} a \ b \end{bmatrix} = \begin{bmatrix} a+k \ \max{a+k, b} \ \end{bmatrix}$。广义矩乘有结合律，因此能用线段树等可以维护半群信息的数据结构维护。
这样能做的关键是，信息有结合律。其实广义矩乘无非用另一种形式写出了第一种做法朴素的维护标记，进而发现了结合律。第一个做法并没有用到结合律。
- 区间加区间推平历史极值
需要讨论两个标记的互相影响。操作序列可以简化成推平再加，还是方便结合的。
矩乘做法使用势能线段树进行推平，感觉很厉害。但是不大通用的样子。
\[\begin{bmatrix} -\infty & -\infty & k \\ -\infty & 0 & k\\ -\infty & -\infty & 0 \end{bmatrix} \begin{bmatrix} a \\ b \\ 0 \end{bmatrix} = \begin{bmatrix} k \\ \max\{b, k\} \\ 0 \end{bmatrix} \\ \]\[\begin{bmatrix} k & -\infty & -\infty \\ k & 0 & -\infty\\ -\infty & -\infty & 0 \end{bmatrix} \begin{bmatrix} a \\ b \\ 0 \end{bmatrix} = \begin{bmatrix} a + k \\ \max\{b, a + k\} \\ 0 \end{bmatrix} \]要知道，矩阵乘法更多是用来理解标记的，而不是用在代码实现上的。
解决。体感比打标记做法好写不少。
想卡常可以只存可能不是负无穷的位置，矩阵只是帮助理解而不是帮助运算。
这样真的很方便解决标记互相影响的问题。
注意到 \((1, 2), (2, 2), (3, 0), (3, 3), (3, 2)\) 的值是固定的，只维护剩余的 \(4\) 个数字，常数变为 \(\frac{1}{4}\)。
#include <bits/stdc++.h>
const int M = 1e5 + 5;
using LL = long long;
const LL inf = 1e14;
struct vec {
LL x11, x21;
// x31 = 0
vec() {
x11 = x21 = -inf;
}
vec(LL a, LL b) { x11 = a, x21 = b; }
vec operator + (const vec &t) const {
return { std::max(x11, t.x11), std::max(x21, t.x21) };
}
} s[M << 2];
struct matrix {
LL x11, x13, x21, x23;
// x12 = x31 = x32 = x23 = -inf, x22 = x33 = 0
matrix operator * (const matrix &t) const {
matrix ans;
ans.x11 = x11 + t.x11;
ans.x13 = std::max(x11 + t.x13, x13);
ans.x21 = std::max(x21 + t.x11, t.x21);
ans.x23 = std::max({x21 + t.x13, t.x23, x23});
return ans;
}
vec operator * (const vec &t) const {
vec ans;
ans.x11 = std::max(x11 + t.x11, x13);
ans.x21 = std::max({x21 + t.x11, t.x21, x23});
return ans;
}
matrix() {
x11 = 0, x13 = x21 = x23 = -inf;
}
} laz[M << 2];
int n, a[M];
void pushdown(int o) {
s[o << 1] = laz[o] * s[o << 1], laz[o << 1] = laz[o] * laz[o << 1];
s[o << 1 | 1] = laz[o] * s[o << 1 | 1], laz[o << 1 | 1] = laz[o] * laz[o << 1 | 1];
laz[o] = matrix();
}
void build(int o, int l, int r) {
if (l == r) {
s[o] = {a[l], a[l]};
return ;
}
int mid = l + r >> 1;
build(o << 1, l, mid), build(o << 1 | 1, mid + 1, r);
s[o] = s[o << 1] + s[o << 1 | 1];
}
void mdf(int o, int l, int r, int x, int y, matrix &t) {
if (x <= l && r <= y) {
s[o] = t * s[o], laz[o] = t * laz[o];
return ;
}
int mid = l + r >> 1; pushdown(o);
if (x <= mid) mdf(o << 1, l, mid, x, y, t);
if (y > mid) mdf(o << 1 | 1, mid + 1, r, x, y, t);
s[o] = s[o << 1] + s[o << 1 | 1];
}
vec qry(int o, int l, int r, int x, int y) {
if (x <= l && r <= y) return s[o];
int mid = l + r >> 1;
vec ans; pushdown(o);
if (x <= mid) ans = ans + qry(o << 1, l, mid, x, y);
if (y > mid) ans = ans + qry(o << 1 | 1, mid + 1, r, x, y);
return ans;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
build(1, 1, n);
int m, l, r; scanf("%d", &m); while (m--) {
char op; scanf(" %c %d %d", &op, &l, &r);
if (op == 'Q') {
printf("%lld\n", qry(1, 1, n, l, r).x11);
} else if (op == 'A') {
printf("%lld\n", qry(1, 1, n, l, r).x21);
} else if (op == 'P') {
matrix t; int k; scanf("%d", &k);
t.x11 = t.x21 = k;
mdf(1, 1, n, l, r, t);
} else if (op == 'C') {
matrix t; int k; scanf("%d", &k);
t.x13 = t.x23 = k;
t.x11 = -inf;
mdf(1, 1, n, l, r, t);
}
}
}