题面

解题思路

线段树

分析

分析一手，分为两种情况讨论

  1. 两区间没有相交的部分

    这种情况还是比较好处理的，只要找出左边的最大右子段和，找出右边的最大左子段和

  2. 两区间有相交的部分

    设左端点 $l$ 所在区间为 $A$，右端点 $r$ 所在区间为 $B$，则令 $A \cap B=C$

    显然，有这样几种情况：

    1. $l \in \complement_AC,r \in B$，变成了没有相交的情况
    2. $l \in C,r\in C$，直接普通求就好
    3. $l\in A,r\in \complement_BC$，也是没有相交的情况

直接写就好

Warning

1、八倍四倍空间

2、注意普通求解操作

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 10003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rgt int s=0,p=1;
    rgt char c=getchar();
    while(!isdigit(c)) p=(c=='-')?-1:1,c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s*p;
}
int T,n,m,a[N],f[N<<2],Fl[N<<2],Sum;
int Fr[N<<2],sum[N<<2],s[N],ans,res,Ans;//Ans和ans的区别
inline void Update(rint k,rint ls,rint rs) {//更新
    f[k]=max(max(f[ls],f[rs]),Fr[ls]+Fl[rs]),
    Fl[k]=max(Fl[ls],Fl[rs]+sum[ls]),
    Fr[k]=max(Fr[rs],Fr[ls]+sum[rs]),
    sum[k]=sum[ls]+sum[rs];
}
inline void built(rint k,rint l,rint r) {
    if(l==r) {f[k]=Fl[k]=Fr[k]=sum[k]=a[l];return;}
    rint m=(l+r)>>1,ls=k<<1;
    built(ls,l,m),built(ls|1,m+1,r),
    Update(k,ls,ls|1);
}
inline void Query(rint k,rint l,rint r,rint L,rint R) {//普通
    if(r<L||R<l) return;
    if(L<=l&&r<=R) {
        cmax(ans,max(f[k],res+Fl[k])),
        res=max(Fr[k],res+sum[k]);
        return;
    }rint m=(l+r)>>1,ls=k<<1;
    Query(ls,l,m,L,R),Query(ls|1,m+1,r,L,R);
}
inline void Query_Left(rint k,rint l,rint r,rint L,rint R) {//最大右子段和
    if(r<L||R<l) return;
    if(L<=l&&r<=R) {cmax(ans,res+Fr[k]),res+=sum[k];return;}
    rint m=(l+r)>>1,ls=k<<1;
    Query_Left(ls|1,m+1,r,L,R),
    Query_Left(ls,l,m,L,R);
}
inline void Query_Right(rint k,rint l,rint r,rint L,rint R) {//最大左子段和
    if(r<L||R<l) return;
    if(L<=l&&r<=R) {cmax(ans,res+Fl[k]),res+=sum[k];return;}
    rint m=(l+r)>>1,ls=k<<1;
    Query_Right(ls,l,m,L,R),
    Query_Right(ls|1,m+1,r,L,R);
}
inline int Q(rint L,rint R) {
    ans=-inf,res=0,Sum=0,Query(1,1,n,L,R);
    return ans;
}
inline int QL(rint L,rint R) {
    if(L<=R) {
        ans=-inf,res=0,Query_Left(1,1,n,L,R);
        return ans;
    }return 0;
}
inline int QR(rint L,rint R) {//这一串是为了方便返回值
    if(L<=R) {
        ans=-inf,res=0,Query_Right(1,1,n,L,R);
        return ans;
    }return 0;
}
int main() {
    rint i,lx,rx,ly,ry;T=read();
    while(T--) {n=read();
        for(i=1;i<=n;i++) a[i]=read(),s[i]=s[i-1]+a[i];
        built(1,1,n),m=read();
        for(i=1;i<=m;i++) {
            lx=read(),rx=read(),ly=read(),ry=read();
            if(rx<ly) printf("%d\n",QL(lx,rx)+s[ly-1]-s[rx]+QR(ly,ry));//注意中间前缀和处理
            else {
                Ans=Q(ly,rx),
                cmax(Ans,QL(lx,ly-1)+QR(ly,ry)),
                cmax(Ans,QL(lx,rx)+QR(rx+1,ry)),//分情况讨论
                printf("%d\n",Ans);
            }
        }
    }
    return 0;
}

devil.