```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
//Mystery_Sky
//
#define M 1000005
#define ll long long
#define Mid (l+r)>>1
struct Tree{
ll lazy;
ll L, R, E, max;
Tree *lc, *rc;
}dizhi[M<<1], *root = &dizhi[0];
int n, m, t=0;
int a[M];
inline void pushup(Tree *tree)
{
tree->max = max(max(tree->lc->max, tree->rc->max), tree->lc->R + tree->rc->L);
tree->L = max(tree->lc->L, tree->lc->E + tree->rc->L);
tree->R = max(tree->rc->R, tree->rc->E + tree->lc->R);
tree->E = tree->lc->E + tree->rc->E;
}
void build(Tree *tree, int l, int r)
{
if(l == r) {
tree->L = tree->E = tree->R = tree->max = a[l];
return;
}
int mid = Mid;
tree->lc = &dizhi[++t];
tree->rc = &dizhi[++t];
build(tree->lc, l, mid);
build(tree->rc, mid+1, r);
pushup(tree);
}
void query(Tree *tree, int l, int r, int x, int y, ll &ans, ll &l_ans, ll &r_ans)
{
if(x <= l && y >= r) {
ans = tree->max;
l_ans = tree->L;
r_ans = tree->R;
return;
}
int mid = Mid;
if(y <= mid) query(tree->lc, l, mid, x, y, ans, l_ans, r_ans);
else if(x > mid) query(tree->rc, mid+1, r, x, y, ans, l_ans, r_ans);
else {
ll L_ans, R_ans, L_lans, L_rans, R_lans, R_rans;
L_ans = R_ans = L_lans = L_rans = R_lans = R_rans = 0;
query(tree->lc, l, mid, x, y, L_ans, L_lans, L_rans);
query(tree->rc, mid+1, r, x, y, R_ans, R_lans, R_rans);
ans = max(max(L_ans, R_ans), L_rans + R_lans);
l_ans = max(l_ans, tree->lc->E + R_lans);
r_ans = max(r_ans, tree->rc->E + L_rans);
}
}
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(root, 1, n);
scanf("%d", &m);
int q, l, r, d;
for(int i = 1; i <= m; i++) {
scanf("%d%d", &l, &r);
if(l > r) swap(l, r);
ll ans, l_ans, r_ans;
ans = l_ans = r_ans = 0;
query(root, 1, n, l, r, ans, l_ans, r_ans);
printf("%lld\n", ans);
}
return 0;
}
```
by Mystery_Sky @ 2019-04-19 20:38:23
~~只有一个点（滑稽~~
by hyfhaha @ 2019-04-19 20:40:59
额
by Mystery_Sky @ 2019-04-19 20:41:52
所以哪里错了呢？
by Mystery_Sky @ 2019-04-19 20:52:21
看我blog吧
by hyfhaha @ 2019-04-19 20:59:40