总算过了，附上AC代码：
```cpp
#include <bits/stdc++.h>
const int Maxn = 1e5 + 10;
int T;
int n, m;
int val[Maxn];
struct node {
int sum;
int maxl, maxr;
int max_;
} tree[Maxn << 2], Null;
int read() {
int sum = 0, flag = 1; char ch = getchar();
for (; (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
if (ch == '-') flag = -1, ch = getchar();
for (; ch >= '0' && ch <= '9'; ch = getchar())
sum = sum * 10 + ch - '0';
return sum * flag;
}
inline int lson(int x) {
return x << 1;
}
inline int rson(int x) {
return x << 1 | 1;
}
void push_up(int x) {
tree[x].sum = tree[lson(x)].sum + tree[rson(x)].sum;
tree[x].maxl = std::max(tree[lson(x)].maxl, tree[lson(x)].sum + tree[rson(x)].maxl);
tree[x].maxr = std::max(tree[rson(x)].maxr, tree[rson(x)].sum + tree[lson(x)].maxr);
tree[x].max_ = std::max(std::max(tree[lson(x)].max_, tree[rson(x)].max_), tree[lson(x)].maxr + tree[rson(x)].maxl);
}
void build(int now, int l, int r) {
if (l > r) return;
if (l == r) {
tree[now].sum = tree[now].maxl = tree[now].maxr = tree[now].max_ = val[l];
return;
}
int mid = l + r >> 1;
build(lson(now), l, mid);
build(rson(now), mid + 1, r);
push_up(now);
}
node query(int now, int l, int r, int L, int R) {
int mid = l + r >> 1;
if (L > R) return Null;
if (L <= l && r <= R)
return tree[now];
else if (R <= mid)
return query(lson(now), l, mid, L, R);
else if (mid < L)
return query(rson(now), mid + 1, r, L, R);
else {
node a, b, ans;
a = query(lson(now), l, mid, L, R);
b = query(rson(now), mid + 1, r, L, R);
ans.sum = a.sum + b.sum;
ans.maxl = std::max(a.maxl, a.sum + b.maxl);
ans.maxr = std::max(b.maxr, b.sum + a.maxr);
ans.max_ = std::max(std::max(a.max_, b.max_), a.maxr + b.maxl);
return ans;
}
}
int main() {
int i, j;
T = read();
Null.sum = Null.maxl = Null.maxr = Null.max_ = 0;
while (T--) {
n = read();
for (i = 1; i <= n; i++) {
val[i] = read();
}
build(1, 1, n);
m = read();
for (i = 1; i <= m; i++) {
int x1, y1, x2, y2;
x1 = read(), y1 = read(), x2 = read(), y2 = read();
if (y1 < x2) {
printf("%d\n", query(1, 1, n, x1, y1).maxr
+ query(1, 1, n, y1 + 1, x2 - 1).sum
+ query(1, 1, n, x2, y2).maxl
);
}
else if (x1 <= x2 && x2 <= y1 && y1 <= y2) {
printf("%d\n", std::max(std::max(
query(1, 1, n, x1, x2).maxr
+ ((x2 == y1) ? -1 * val[x2] : query(1, 1, n, x2 + 1, y1 - 1).sum)
+ query(1, 1, n, y1, y2).maxl,
query(1, 1, n, x2, y1).max_),
std::max(
query(1, 1, n, x1, x2).maxr
+ query(1, 1, n, x2, y1).maxl
- val[x2],
query(1, 1, n, x2, y1).maxr
+ query(1, 1, n, y1, y2).maxl
- val[y1])));
}
}
}
return 0;
}
```
by zzzYheng @ 2021-08-13 20:08:29