rt,求帮忙看看/kk/kk心态崩了
#include <bits/stdc++.h>
using namespace std;
int mpre[40010],msuf[40010],msum[40010],sum[40010],n,m,a[10010];
void build(int o,int lf,int rg)
{
if(lf==rg)
{
msum[o]=msuf[o]=mpre[o]=max(0,a[lf]);
sum[o]=a[lf];
return ;
}
int mid=(lf+rg)>>1;
build(o<<1,lf,mid),build(o<<1|1,mid+1,rg);
mpre[o]=max(mpre[o<<1],sum[o<<1]+mpre[o<<1|1]);
msuf[o]=max(msuf[o<<1|1],sum[o<<1|1]+msuf[o<<1]);
sum[o]=sum[o<<1]+sum[o<<1|1];
msum[o]=max(max(msum[o<<1],msum[o<<1|1]),msuf[o<<1]+mpre[o<<1|1]);
}
int qsum(int o,int lf,int rg,int l,int r)
{
if(l>r)
{
return 0;
}
if(l<=lf&&rg<=r)
{
return sum[o];
}
int mid=(lf+rg)>>1,ans=0;
if(l<=mid)
{
ans+=qsum(o<<1,lf,mid,l,r);
}
if(mid<r)
{
ans+=qsum(o<<1|1,mid+1,rg,l,r);
}
return ans;
}
int query(int o,int lf,int rg,int l,int r)
{
if(l>r)
{
return 0;
}
if(l<=lf&&rg<=r)
{
return sum[o];
}
int mid=(lf+rg)>>1,ans=0;
if(l<=mid)
{
ans=ans+query(o<<1,lf,mid,l,r);
}
if(mid<r)
{
ans=ans+query(o<<1|1,mid+1,rg,l,r);
}
return ans;
}
int qsuf(int o,int lf,int rg,int l,int r)
{
if(l>r)
{
return 0;
}
if(l<=lf&&rg<=r)
{
return msuf[o];
}
int mid=(lf+rg)>>1,ans=0;
if(mid<r)
{
ans=max(ans,qsuf(o<<1|1,mid+1,rg,l,r));
if(l<=mid)
{
ans=max(ans,query(o<<1|1,mid+1,rg,l,r)+qsuf(o<<1,lf,mid,l,r));
}
}
else
{
if(l<=mid)
{
ans=max(ans,qsuf(o<<1,lf,mid,l,r));
}
}
return ans;
}
int qpre(int o,int lf,int rg,int l,int r)
{
if(l>r)
{
return 0;
}
if(l<=lf&&rg<=r)
{
return mpre[o];
}
int mid=(lf+rg)>>1,ans=0;
if(l<=mid)
{
ans=max(ans,qpre(o<<1,lf,mid,l,r));
if(mid<r)
{
ans=max(ans,query(o<<1,lf,mid,l,r)+qpre(o<<1|1,mid+1,rg,l,r));
}
}
else
{
if(mid<r)
{
ans=max(ans,qpre(o<<1|1,mid+1,rg,l,r));
}
}
return ans;
}
int qans(int o,int lf,int rg,int l,int r)
{
if(l>r)
{
return 0;
}
if(l<=lf&&rg<=r)
{
return msum[o];
}
int mid=(lf+rg)>>1,ans=0;
if(l<=mid&&mid<r)
{
ans=qsuf(o<<1,lf,mid,l,r)+qpre(o<<1|1,mid+1,rg,l,r);
}
if(l<=mid)
{
ans=max(ans,qans(o<<1,lf,mid,l,r));
}
if(mid<r)
{
ans=max(ans,qans(o<<1|1,mid+1,rg,l,r));
}
return ans;
}
int T;
int main()
{
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
cin>>m;
build(1,1,n);
for(int i=1;i<=m;i++)
{
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
if(r1<l2)
{
cout<<qsum(1,1,n,r1+1,l2-1)+qsuf(1,1,n,l1,r1)+qpre(1,1,n,l2,r2)<<"\n";
}
else
{
int val=qans(1,1,n,l2,r1);
if(l1<l2)
{
val=max(val,qsuf(1,1,n,l1,l2)+qpre(1,1,n,l2,r2)-a[l2]);
}
if(r1<r2)
{
val=max(val,qpre(1,1,n,r1,r2)+qsuf(1,1,n,l1,r1)-a[r1]);
}
cout<<val<<"\n";
}
}
}
}