3981 动态最大子段和

/*

线段树区间操作GSS

一段长的区间的 GSS 有三种情况：

1 完全在左子区间

2 完全在右子区间

3 横跨左右区间

前两种情况可使用子区间的 GSS，但如何处理第三种情况？

注意到我们可以把区间拆成两部分，这两部分是不相关的。

所以我们需要维护一个区间的“最大左子段和”和“最大右子段和”。

gss = MAX{l.gss,r.gss,l.rgss + r.lgss}

由 GSS 一直推下来,对于每个节点,我们一共需要设计4个状态。

1 GSS：最大子段和

2 LGSS：最大左子段和

3 RGSS：最大右子段和

4 SUM：整段和

这里我用了结构体存储（元元真厉害啊！）

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define ll long long

#define maxn 2000010

using namespace std;

ll n,a[maxn],q,x,y,ans;

struct node{

    ll l,r,dis,mx,lmx,rmx;

}tre[maxn>>];

ll init()

{

    ll x=,f=;char c=getchar();

    while(c>''||c<''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

void build(int now,ll l,ll r)

{

    tre[now].l=l;tre[now].r=r;

    if(l==r)

    {

        tre[now].dis=init();

        tre[now].lmx=tre[now].rmx=tre[now].mx=tre[now].dis;

        return ;

    }

    ll mid=(l+r)>>;

    build(now<<,l,mid);

    build(now<<|,mid+,r);

    //下面是重点之一，要注意。

    tre[now].lmx=max(tre[now<<].lmx,tre[now<<].dis+tre[now<<|].lmx);

    tre[now].rmx=max(tre[now<<|].rmx,tre[now<<|].dis+tre[now<<].rmx);

    tre[now].mx=max(tre[now<<].rmx+tre[now<<|].lmx,max(tre[now<<].mx,tre[now<<|].mx));

    tre[now].dis=tre[now<<].dis+tre[now<<|].dis;

}

node query(int now,ll l,ll r)

{

    node ans;

    if(l==tre[now].l&&r==tre[now].r) return tre[now];

    ll mid=(tre[now].l+tre[now].r)>>;

    if(l>mid) return query(now<<|,l,r);

    else if(r<=mid) return query(now<<,l,r);

    else//就是这里咋也不会写，递归找边界思路不清晰

    {

        node lch=query(now<<,l,mid);

        node rch=query(now<<|,mid+,r);

        ans.lmx=max(lch.lmx,lch.dis+rch.lmx);

        ans.rmx=max(rch.rmx,rch.dis+lch.rmx);

        ans.mx=max(max(lch.mx,rch.mx),lch.rmx+rch.lmx);

    }

    return ans;

}

int main()

{

    n=init();

    build(,,n);

    q=init();

    for(int i=;i<=q;i++)

    {

        x=init();y=init();

        printf("%lld\n",query(,x,y).mx);

    }

    return ;

}