WA on #1

也不知道哪里的问题,最大子段和不为空也已经注意了.

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,inf=2e9+9;
int T,n,q,sz,L,R;
struct tree{
    int l,r,len;
    int w,lw,rw;
    int ls,rs,sum;
}tr[N<<1];
inline void chg(int id,int x)
{tr[id].sum=tr[id].lw=tr[id].rw=tr[id].w=x;}
inline tree pushup(tree now,tree tls,tree trs){
    now.sum=tls.sum+trs.sum;
    now.lw=max(tls.lw,tls.sum+trs.lw);
    now.rw=max(trs.rw,trs.sum+tls.rw);
    now.w=max(max(tls.w,trs.w),tls.rw+trs.lw);
    return now;
}
inline void build(int l,int r,int id){
    tr[id]=(tree){l,r,r-l+1,0};
    if(l==r){int x;cin>>x;chg(id,x);return;}
    int ls=++sz,rs=++sz,mid=l+(r-l>>1);
    build(l,mid,ls),build(mid+1,r,rs);
    tr[id].ls=ls,tr[id].rs=rs;
    tr[id]=pushup(tr[id],tr[ls],tr[rs]);
}
inline tree qry(int id){
    int l=tr[id].l,r=tr[id].r;
    if(l>R||r<L)return (tree){0,0,0,-inf,-inf,-inf,0};
    if(L<=l&&r<=R)return tr[id];
    int ls=tr[id].ls,rs=tr[id].rs;
    return pushup(tr[id],qry(ls),qry(rs));
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int l1,l2,r1,r2,ans,t1,t2,t3;
    cin>>T;while(T--){
        cin>>n;sz=0;build(1,n,++sz);
        cin>>q;while(q--){
            cin>>l1>>l2>>r1>>r2,t1=t2=t3=ans=-inf;
            if(l2<=r1){
                L=l2,R=r1,t1=qry(1).sum;
                L=l1,R=l2-1;if(L<=R)t2=qry(1).rw;
                L=r1+1,R=r2;if(L<=R)t3=qry(1).lw;
                ans=max(max(t1+t3,t1+t2),max(t1+t2+t3,max(t1,max(t2,t3))));
                cout<<ans<<'\n';
            }else{
                L=r1,R=l2,ans=max(ans,qry(1).w);
                L=r1,R=l2,t1=qry(1).sum;
                L=l1,R=r1-1;if(L<=R)t2=qry(1).rw;
                L=l2+1,R=r2;if(L<=R)t3=qry(1).lw;
                ans=max(max(t1+t3,t1+t2),max(t1+t2+t3,max(t1,max(t2,t3))));
                L=r1,R=l2,t1=qry(1).lw;
                ans=max(ans,max(t1+t2,max(t1,t2)));
                L=r1,R=l2,t1=qry(1).rw;
                ans=max(ans,max(t1+t3,max(t1,t3)));
                cout<<ans<<'\n';
            }
        }
    }
}