线段树然后yy一下，搞一搞。
GSS1:
题意：求最大区间和。
#include <cstdio>
#include <algorithm>
using namespace std;
int lm[200005],rm[200005],ma[200005],s[200005],left,right,n,m,ans,rans;
void build(int l,int r,int num){
if(l==r){scanf("%d",&ma[num]);rm[num]=lm[num]=s[num]=ma[num];return;}
int mid=(l+r)/2;
build(l,mid,num*2);
build(mid+1,r,num*2+1);
s[num]=s[num*2]+s[num*2+1];
lm[num]=max(lm[num*2],s[num*2]+lm[num*2+1]);
rm[num]=max(rm[num*2+1],s[num*2+1]+rm[num*2]);
ma[num]=max(lm[num*2+1]+rm[num*2],max(ma[num*2+1],ma[num*2]));
}
void find(int l,int r,int num){
if(l>=left&&r<=right){
ans=max(ans,max(ma[num],rans+lm[num]));
rans=max(rm[num],rans+s[num]);
return;
}
int mid=(l+r)/2;
if(mid>=left)find(l,mid,num*2);
if(mid<right)find(mid+1,r,num*2+1);
}
int main()
{
scanf("%d",&n);
build(1,n,1);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&left,&right);
rans=ans=-1*0x3fffffff,find(1,n,1),printf("%d\n",ans);
}
}GSS3:
GSS3就是GSS1加一个修改操作。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf 0x3fffffff
#define N 2000000
using namespace std;
int n,m,s[N],ma[N],lm[N],rm[N],jy,le,ri,ans,rans;
void bu(int l,int r,int num){
if(l==r){scanf("%d",&s[num]),ma[num]=lm[num]=s[num]=rm[num]=s[num];return;}
int m=(l+r)/2;
bu(l,m,num*2);bu(m+1,r,num*2+1);
lm[num]=max(lm[num*2],lm[num*2+1]+s[num*2]);
rm[num]=max(rm[num*2+1],s[num*2+1]+rm[num*2]);
s[num]=s[num*2]+s[num*2+1];
ma[num]=max(ma[num*2],max(ma[num*2+1],lm[num*2+1]+rm[num*2]));
}
void fi(int l,int r,int num){
if(l>=le&&r<=ri){
ans=max(ans,max(ma[num],rans+lm[num]));
rans=max(rm[num],rans+s[num]);
return;
}
int m=(l+r)/2;
if(m>=le)fi(l,m,num*2);
if(m<ri)fi(m+1,r,num*2+1);
}
void ch(int l,int r,int num){
if(l==r){ma[num]=lm[num]=s[num]=rm[num]=s[num]=ri;return;}
int m=(l+r)/2;
if(m>=le)ch(l,m,num*2);
else ch(m+1,r,num*2+1);
lm[num]=max(lm[num*2],lm[num*2+1]+s[num*2]);
rm[num]=max(rm[num*2+1],s[num*2+1]+rm[num*2]);
s[num]=s[num*2]+s[num*2+1];
ma[num]=max(ma[num*2],max(ma[num*2+1],lm[num*2+1]+rm[num*2]));
}
int main()
{
scanf("%d",&n);
bu(1,n,1);
scanf("%d",&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&jy,&le,&ri);
if(jy){rans=ans=-inf;fi(1,n,1);printf("%d\n",ans);}
else ch(1,n,1);
}
} GSS5写挂ing……自己写了个对拍，和网上AC的code拍，一开始还找出来点儿错，交上去，WA，，，完之后就不知道错哪了，ZRT只是说我的maker写得没有问题，还说什么线段树的错特别难找。。就挂了。。。。。。
放个WA code吧。。。（但是至少能水掉90%的官方数据，100%我的自测数据。。目前已拍30000多组）
#include <cstdio>
#include <cstring>
#include <algorithm>
#define inf 0x3fffffff
#define N 2000000
using namespace std;
int n,m,s[N],ma[N],lm[N],rm[N],jy,ans,rans,lans,cases;
void bu(int l,int r,int num){
if(l==r){scanf("%d",&s[num]),ma[num]=lm[num]=s[num]=rm[num]=s[num];return;}
int m=(l+r)/2;
bu(l,m,num*2);bu(m+1,r,num*2+1);
lm[num]=max(lm[num*2],lm[num*2+1]+s[num*2]);
rm[num]=max(rm[num*2+1],s[num*2+1]+rm[num*2]);
s[num]=s[num*2]+s[num*2+1];
ma[num]=max(ma[num*2],max(ma[num*2+1],lm[num*2+1]+rm[num*2]));
}
void fm(int left,int right,int l,int r,int num){
if(l>=left&&r<=right){
ans=max(ans,max(ma[num],rans+lm[num]));
rans=max(rm[num],rans+s[num]);
return;
}
int m=(l+r)/2;
if(m>=left)fm(left,right,l,m,num*2);
if(m<right)fm(left,right,m+1,r,num*2+1);
}
int fs(int left,int right,int l,int r,int num){
if(left<=l&&right>=r)return s[num];
int m=(l+r)/2,sum=0;
if(m>=left)sum+=fs(left,right,l,m,num*2);
if(m<right)sum+=fs(left,right,m+1,r,num*2+1);
return sum;
}
void fl(int left,int right,int l,int r,int num){
if(left<=l&&right>=r){
rans=max(rans+s[num],rm[num]);
return;
}
int m=(l+r)/2;
if(m>=left)fl(left,right,l,m,num*2);
if(m<right)fl(left,right,m+1,r,num*2+1);
}
void fr(int left,int right,int l,int r,int num){
if(left<=l&&right>=r){
lans=max(lans+s[num],lm[num]);
return;
}
int m=(l+r)/2;
if(m<right)fr(left,right,m+1,r,num*2+1);
if(m>=left)fr(left,right,l,m,num*2);
}
int main()
{
int x1,x2,y1,y2;
scanf("%d",&cases);
while(cases--){
scanf("%d",&n);
bu(1,n,1);
scanf("%d",&m);
for(int i=1;i<=m;i++){
lans=rans=ans=-inf;
scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
if(y1>x2){
if(x2>x1&&y2>y1){
int Q=fs(x2,y1,1,n,1);
fl(x1,x2-1,1,n,1);
fr(y1+1,y2,1,n,1);
ans=max(Q,max(max(rans+Q,lans+Q),rans+lans+Q));
printf("%d\n",ans);
}
else if(x1==x2){
int Q=fs(x2,y1,1,n,1);
fr(y1+1,y2,1,n,1);
ans=max(lans,lans+Q);
printf("%d\n",ans);
}
else if(y1==y2)
{
int Q=fs(x2,y1,1,n,1);
fl(x1,x2-1,1,n,1);
ans=max(rans,Q+rans);
printf("%d\n",ans);
}
}
else if(y1==x2){
if(x2-1>=x1)fl(x1,x2-1,1,n,1);
if(y1+1<=y2)fr(y1+1,y2,1,n,1);
int Q=fs(y1,y1,1,n,1);
ans=max(Q,max(max(Q+lans,Q+rans),Q+lans+rans));
printf("%d\n",ans);
}
else if(y1<x2){
fl(x1,y1,1,n,1);fr(y1,y2,1,n,1);int Q=fs(y1,y1,1,n,1);
ans=max(rans,max(lans,rans+lans-Q));
rans=lans=-inf;
fl(x1,x2,1,n,1);fr(x2,y2,1,n,1);Q=fs(x2,x2,1,n,1);
ans=max(ans,max(lans,max(rans,rans+lans-Q)));
rans=lans=-inf;
fm(y1,x2,1,n,1);
printf("%d\n",ans);
}
}
}
}这么杂乱无章&冗长的代码不是我的风格，但是越改代码越丑。。。。。