给定一个序列。查询左端点在$[x_1, y_1]$之间，且右端点在$[x_2, y_2]$之间的最大子段和，数据保证$x_1\leq x_2,y_1\leq y_2$，但是不保证端点所在的区间不重合

 

这题可以分为几种情况讨论

$y_1<x_2$

那么这个时候发现$[y_1+1,x_2-1]$里的数必须得选，并选出$[x1,y1]$的最大后缀和$[x2,y2]$的最大前缀。用结构体维护一下就好了

$y_1\geq x_2$

发现这个时候左右端点所在区间的情况分别如下

$l$在$[x_1,x_2]$，$r$在$[x_2,y_1]$，那么只要查询$[x_1,x_2]$的最大后缀和$[x_2,y_1]$的最大前缀

$l$在$[x_1,x_2]$，$r$在$[y_1,y_2]$，那么只要查询$[x_1,x_2]$的最大后缀和$[x_2,y_2]$的最大前缀

$l$在$[x_2,y_1]$，$r$在$[x_2,y_1]$，那么只要查询$[x_2,y_1]$的最大子段和

$l$在$[x_2,y_1]$，$r$在$[y_1,y_2]$，那么只要查询$[x_2,y_1]$的最大后缀和$[y_1,y_2]$的最大前缀

1 //minamoto 2 #include
     
       3 #include
      
        4 #include
       
         5 #define ls (p<<1) 6 #define rs (p<<1|1) 7 using namespace std; 8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 9 char buf[1<<21],*p1=buf,*p2=buf;10 template
        
         inline bool cmax(T&a,const T&b){
   return a
         
          1<<20)Ot();if(x<0)sr[++C]=45,x=-x;25     while(z[++Z]=x%10+48,x/=10);26     while(sr[++C]=z[Z],--Z);sr[++C]='\n';27 }28 const int N=1e4+5;int a[N],n,m;29 struct node{
   int pre,mid,suf,sum;}b[N<<2];30 node merge(node l,node r){31     node ans;32     ans.pre=max(l.pre,l.sum+r.pre);33     ans.mid=max(max(l.mid,r.mid),l.suf+r.pre);34     ans.suf=max(l.suf+r.sum,r.suf);35     ans.sum=l.sum+r.sum;36     return ans;37 }38 void upd(int p){b[p]=merge(b[ls],b[rs]);}39 void build(int p,int l,int r){40     if(l==r) return (void)(b[p].pre=b[p].mid=b[p].suf=b[p].sum=a[l]);41     int mid=(l+r)>>1;42     build(ls,l,mid),build(rs,mid+1,r);43     upd(p);44 }45 node query(int p,int l,int r,int ql,int qr){46     if(ql>qr) return (node){
   0,0,0,0};47     if(ql<=l&&qr>=r) return b[p];48     int mid=(l+r)>>1;49     if(qr<=mid) return query(ls,l,mid,ql,qr);50     else if(ql>mid) return query(rs,mid+1,r,ql,qr);51     else return merge(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));52 }53 int get(int l1,int r1,int l2,int r2){54     if(r1
          
           r1) cmax(ans,query(1,1,n,l1,r1).suf+query(1,1,n,r1,r2).pre-a[r1]);63 return ans;64 }65 int main(){66 // freopen("testdata.in","r",stdin);67 int T=read();68 while(T--){69 n=read();70 for(int i=1;i<=n;++i) a[i]=read();71 build(1,1,n);72 m=read();73 while(m--){74 int l1=read(),r1=read(),l2=read(),r2=read();75 print(get(l1,r1,l2,r2));76 }77 }78 return Ot(),0;79 }