```cpp
#include <bits/stdc++.h>
#define L id << 1
#define R id << 1 | 1
using namespace std;
const int N = 50005;
struct SegTree {
int sum, l, r, Query;
} Tree[N << 2];
int n, m, a[N];
void pushup(int id) {
Tree[id].sum = Tree[L].sum + Tree[R].sum;
Tree[id].l = max(Tree[L].l, Tree[L].sum + Tree[R].l);
Tree[id].r = max(Tree[L].r + Tree[R].sum, Tree[R].r);
Tree[id].Query = max(Tree[L].Query, max(Tree[R].Query, Tree[L].r + Tree[R].l));
}
void build(int id, int l, int r) {
if(l == r) {
Tree[id].sum = Tree[id].l = Tree[id].r = Tree[id].Query = a[l];
return ;
}
int mid = (l + r) >> 1;
build(L, l, mid);
build(R, mid + 1, r);
pushup(id);
}
SegTree query(int id, int l, int r, int x, int y) {
if(x <= l && r <= y) {
return Tree[id];
}
int mid = (l + r) >> 1;
SegTree ans;
if(mid >= x && mid < y) {
SegTree lft = query(L, l, mid, x, y);
SegTree rht = query(R, mid + 1, r, x, y);
ans.sum = max(lft.sum, rht.sum);
ans.l = max(lft.l, rht.l);
ans.r = max(lft.r, rht.r);
ans.Query = max(lft.Query, rht.Query);
}
else if(mid >= x) ans = query(L, l, mid, x, y);
else ans = query(R, mid + 1, r, x, y);
return ans;
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++) scanf("%d", a + i);
build(1, 1, n);
cin >> m;
while(m--) {
int x, y;
scanf("%d%d", &x, &y);
SegTree ans = query(1, 1, n, x, y);
printf("%d\n", ans.Query);
}
return 0;
}
```
by EggShell123 @ 2020-09-01 15:25:02
@[泥土笨笨txdy](/user/373327) 您在query的时候那个mid >= x && mid < y 的情况里面没有合并两个答案
by juicyyou @ 2020-09-01 15:39:52
@[泥土笨笨txdy](/user/373327) 合并的时候得按照pushup的方法合并（
by juicyyou @ 2020-09-01 15:40:44
楼上正解 不如重载个加号
by 陈浩然 @ 2020-09-01 15:42:26
@[SPFA](/user/177999) @[陈浩然](/user/249339) 谢谢，wssb（
by EggShell123 @ 2020-09-01 15:48:16
A 了，谢谢qwq
by EggShell123 @ 2020-09-01 15:51:10