这题是维护历史最大值模板。
先套线段树，考虑怎么维护标记。
我们发现普通的标记的维护遵循能合并就合并，但是这就会出现问题：假如一个标记还没有下传时就被修改（也就是减小），那就会导致子树的历史最大值不正确（变小）。
考虑先不合并同一个节点的标记，把它们看成一个操作序列。这里讲一个简化的问题：
- 支持区间加
- 查询当前最大值
- 查询历史最大值
考虑怎么下传标记。显然每个标记都下传更新一次是可行的，但是我们无法维护这样一个操作序列。
设操作序列的前缀和为 \(S[1\cdots i]\)，那么只需要下传 \(\max(S[1\cdots i])\) 即可维护答案。考虑合并两个标记，设 \(S_1[1\cdots n]\) 和 \(S_2[1\cdots m]\)，合并完为 \(S_3[1\cdots n+m]\)。
容易推出 \(\max (S_3) = (\max (S_1), S_1[n]+\max (S_2))\)。
此时 \(S_1[n]\) 为我们普通加法标记的值。
具体的说，我们只需要维护历史最大加和当前加两个标记即可维护。
回到这题，多了操作区间赋值，若操作序列中有两种标记，不好维护。容易发现，若前面出现过赋值操作，那么之后的加法标记都可以直接加到赋值标记中变为赋值标记。
此时操作序列转化为，一段加法序列+一段赋值序列两段。前面的加法序列用前面说的一样维护，设后面赋值序列为 \(C\)，后面的赋值序列的历史最大赋值即为 \(\max C\)。
pushdown 时分两段下传即可。
#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
typedef long long i64;
const int N = 100010;
int n, m;
int a[100010];
i64 inf = 0x3f3f3f3f3f3f3f3f;
struct seg {
i64 max1, max2;
i64 fg, add;
i64 vis, hfg, hadd; //fg 覆盖，add 加法
} t[N << 2];
void pushup(int u) {
t[u].max1 = std::max(t[u << 1].max1, t[u << 1 | 1].max1);
t[u].max2 = std::max(t[u << 1].max2, t[u << 1 | 1].max2);
}
void build(int u, int l, int r) {
if(l == r) {
t[u].max1 = t[u].max2 = a[l];
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
void add(int u, i64 add, i64 hadd) {
if(t[u].vis) {
t[u].hfg = std::max(t[u].hfg, t[u].fg + hadd);
t[u].max2 = std::max(t[u].max2, t[u].max1 + hadd);
t[u].max1 += add;
t[u].fg += add;
}
else {
t[u].hadd = std::max(t[u].hadd, t[u].add + hadd);
t[u].max2 = std::max(t[u].max2, t[u].max1 + hadd);
t[u].max1 += add;
t[u].add += add;
}
}
void cov(int u, i64 fg, i64 hfg) {
if(t[u].vis) {
t[u].hfg = std::max(t[u].hfg, hfg);
t[u].max2 = std::max(t[u].max2, hfg);
}
else {
t[u].vis = 1;
t[u].hfg = hfg;
t[u].max2 = std::max(t[u].max2, hfg);
}
t[u].fg = t[u].max1 = fg;
}
void pushdown(int u) {
add(u << 1, t[u].add, t[u].hadd);
add(u << 1 | 1, t[u].add, t[u].hadd);
t[u].add = t[u].hadd = 0;
if(t[u].vis) {
cov(u << 1, t[u].fg, t[u].hfg);
cov(u << 1 | 1, t[u].fg, t[u].hfg);
t[u].fg = t[u].hfg = t[u].vis = 0;
}
}
void update(int u, int l, int r, int L, int R, i64 x, int y) {
if(L <= l && r <= R) {
if(!y) add(u, x, x);
else cov(u, x, x);
return;
}
int mid = (l + r) >> 1;
pushdown(u);
if(L <= mid) update(u << 1, l, mid, L, R, x, y);
if(R > mid) update(u << 1 | 1, mid + 1, r, L, R, x, y);
pushup(u);
}
i64 qmax1(int u, int l, int r, int L, int R) {
if(L <= l && r <= R) {
return t[u].max1;
}
int mid = (l + r) >> 1;
pushdown(u);
if(R <= mid) return qmax1(u << 1, l, mid, L, R);
if(L > mid) return qmax1(u << 1 | 1, mid + 1, r, L, R);
return std::max(qmax1(u << 1, l, mid, L, R), qmax1(u << 1 | 1, mid + 1, r, L, R));
}
i64 qmax2(int u, int l, int r, int L, int R) {
if(L <= l && r <= R) {
return t[u].max2;
}
int mid = (l + r) >> 1;
pushdown(u);
if(R <= mid) return qmax2(u << 1, l, mid, L, R);
if(L > mid) return qmax2(u << 1 | 1, mid + 1, r, L, R);
return std::max(qmax2(u << 1, l, mid, L, R), qmax2(u << 1 | 1, mid + 1, r, L, R));
}
void Solve() {
std::cin >> n;
for(int i = 1; i <= n; i++) {
std::cin >> a[i];
}
build(1, 1, n);
std::cin >> m;
while(m--) {
char c;
std::cin >> c;
int l, r;
std::cin >> l >> r;
if(c == 'Q') {
std::cout << qmax1(1, 1, n, l, r) << "\n";
} else if(c == 'A') {
std::cout << qmax2(1, 1, n, l, r) << "\n";
} else if(c == 'P') {
int x;
std::cin >> x;
update(1, 1, n, l, r, x, 0);
} else if(c == 'C') {
int x;
std::cin >> x;
update(1, 1, n, l, r, x, 1);
}
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Solve();
return 0;
}