#include <iostream>
using namespace std;
const int N = 1e5 + 9;
typedef long long ll;
ll a[N];
struct Segment_tree{
struct node {
ll l, r, L, R, Lmax, Rmax, datamax, sum;
}tr[N << 2];
inline void pushup(ll p){
int L = tr[p].l;
int R = tr[p].r;
tr[p].datamax = max(max(tr[L].datamax, tr[R].datamax), tr[L].Rmax + tr[R].Lmax);
tr[p].sum = tr[L].sum + tr[R].sum;
tr[p].Lmax = max(tr[L].Lmax, tr[L].sum + tr[R].Lmax);
tr[p].Rmax = max(tr[R].Rmax, tr[R].sum + tr[L].Rmax);
tr[p].datamax = max(max(tr[L].datamax, tr[R].datamax), tr[L].Rmax + tr[R].Lmax);
tr[p].datamax = max(tr[p].datamax, max(tr[p].Lmax, tr[p].Rmax));
}
inline void build(ll l, ll r, ll p) {
tr[p].L = l, tr[p].R = r, tr[p].l = p << 1, tr[p].r = p << 1 | 1;
if (l == r) {
tr[p].datamax = a[l];
tr[p].Lmax = a[l];
tr[p].Rmax = a[r];
tr[p].sum = a[l];
return ;
}
int mid = l + r >> 1;
build(l, mid, tr[p].l);
build(mid + 1, r, tr[p].r);
pushup(p);
}
inline node ask(ll l, ll r, ll p) {
if (tr[p].L>=l && tr[p].R <= r)
{
return tr[p];
}
int mid = tr[p].L + tr[p].R >> 1;
if (l >= mid + 1)return ask(l, r, tr[p].r);
if (r <= mid)return ask(l, r, tr[p].l);
node a = ask(l, r, tr[p].l);
node b = ask(l, r, tr[p].r);
node ret;
ret.Lmax = max(a.Lmax, a.sum + b.Lmax);
ret.Rmax = max(b.Rmax, b.sum + a.Rmax);
ret.datamax = max(a.datamax, b.datamax);
ret.datamax = max(ret.datamax, a.Rmax + b.Lmax);
ret.datamax = max(ret.datamax, max(ret.Lmax, ret.Rmax));
ret.sum = a.sum + b.sum;
return ret;
}
}T;
int main() {
int n;scanf("%d",&n);
for (int i =1; i <=n; i ++ ) scanf("%lld", &a[i]);
T.build(1, n, 1);
int m;
scanf("%d", &m);
while (m--) {
ll l, r;
scanf("%lld%lld", &l, &r);
if (l > r)swap(l, r);
printf("%lld\n", T.ask(l, r, 1).datamax);
}
}
GSS1 - Can you answer these queries I
原文:https://www.cnblogs.com/Xiao-yan/p/14703870.html