一颗比较麻烦的线段树，维护变量比较多
sum区间和
Max区间最大子序列和
Ls区间从左端点开始最大子序列和，Lto终点位置
Rs从右端点开始最大子序列和，Rto终点位置
pushup()的时候，比较麻烦，细节比较多
更新Max的情况
更新Ls，Rs直接更新就可以了
#include<iostream> #include<cstdio> #include<cstring> #define maxn 100005 using namespace std; int n,m; int a[maxn]; struct tree { int l,r,Ls,Lto,Rs,Rto,Max,Ml,Mr,sum; }b[maxn*4]; void update(int z) { if(b[2*z].Max>=b[2*z+1].Max){ b[z].Ml=b[2*z].Ml; b[z].Mr=b[2*z].Mr; } else { b[z].Ml=b[2*z+1].Ml; b[z].Mr=b[2*z+1].Mr;} b[z].Max=max(b[2*z].Max,b[2*z+1].Max); if(b[z].Max==b[2*z].Rs+b[2*z+1].Ls&&b[2*z].Rto<b[z].Ml) { b[z].Ml=b[2*z].Rto;b[z].Mr=b[2*z+1].Lto; } if(b[z].Max==b[2*z].Rs+b[2*z+1].Ls&&b[2*z].Rto==b[z].Ml&&b[2*z+1].Lto<b[z].Mr) b[z].Mr=b[2*z+1].Lto; if(b[z].Max<b[2*z].Rs+b[2*z+1].Ls){ b[z].Ml=b[2*z].Rto;b[z].Mr=b[2*z+1].Lto; b[z].Max=b[2*z].Rs+b[2*z+1].Ls; } b[z].Ls=b[2*z].Ls; b[z].Lto=b[2*z].Lto; if(b[2*z].Lto==b[2*z].r&&b[2*z+1].Ls>0){ b[z].Ls=b[2*z].Ls+b[2*z+1].Ls; b[z].Lto=b[2*z+1].Lto; } if(b[2*z].sum+b[2*z+1].Ls>b[z].Ls){ b[z].Ls=b[2*z].sum+b[2*z+1].Ls; b[z].Lto=b[2*z+1].Lto; } b[z].Rs=b[2*z+1].Rs;b[z].Rto=b[2*z+1].Rto; if(b[2*z+1].Rto==b[2*z+1].l&&b[2*z].Rs>0){ b[z].Rs=b[2*z+1].Rs+b[2*z].Rs; b[z].Rto=b[2*z].Rto; } if(b[2*z+1].sum+b[2*z].Rs>b[z].Rs){ b[z].Rs=b[2*z+1].sum+b[2*z].Rs; b[z].Rto=b[2*z].Rto; } b[z].sum=b[2*z].sum+b[2*z+1].sum; } void pushup(tree tmp1,tree tmp2,tree &tmp3) { if(tmp1.Max>=tmp2.Max){ tmp3.Ml=tmp1.Ml; tmp3.Mr=tmp1.Mr; } else { tmp3.Ml=tmp2.Ml; tmp3.Mr=tmp2.Mr;} tmp3.Max=max(tmp1.Max,tmp2.Max); if(tmp3.Max==tmp1.Rs+tmp2.Ls&&tmp1.Rto<tmp3.Ml) { tmp3.Ml=tmp1.Rto;tmp3.Mr=tmp2.Lto; } if(tmp3.Max==tmp1.Rs+tmp2.Ls&&tmp1.Rto==tmp3.Ml&&tmp2.Lto<tmp3.Mr) tmp3.Mr=tmp2.Lto; if(tmp3.Max<tmp1.Rs+tmp2.Ls){ tmp3.Ml=tmp1.Rto;tmp3.Mr=tmp2.Lto; tmp3.Max=tmp1.Rs+tmp2.Ls; } tmp3.Ls=tmp1.Ls; tmp3.Lto=tmp1.Lto; if(tmp1.Lto==tmp2.l-1&&tmp2.Ls>0){ tmp3.Ls=tmp1.Ls+tmp2.Ls; tmp3.Lto=tmp2.Lto; } if(tmp1.sum+tmp2.Ls>tmp3.Ls){ tmp3.Ls=tmp1.sum+tmp2.Ls; tmp3.Lto=tmp2.Lto; } tmp3.Rs=tmp2.Rs;tmp3.Rto=tmp2.Rto; if(tmp2.Rto==tmp1.r+1&&tmp1.Rs>0){ tmp3.Rs=tmp2.Rs+tmp1.Rs; tmp3.Rto=tmp1.Rto; } if(tmp2.sum+tmp1.Rs>tmp3.Rs){ tmp3.Rs=tmp2.sum+tmp1.Rs; tmp3.Rto=tmp1.Rto; } tmp3.sum=tmp2.sum+tmp1.sum; //printf("%d %d %d %d %d\n",tmp3.l,tmp3.r,tmp3.Ml,tmp3.Mr,tmp3.Max); } tree quiry(int l,int r,int z) { //printf("%d** %d\n",l,r); //if(i==23) printf("%d %d \n",b[z].l,b[z].r); if(l<=b[z].l&&b[z].r<=r) return b[z]; int mid=(b[z].l+b[z].r)/2; if(r<=mid) return quiry(l,r,2*z); else if(l>mid) return quiry(l,r,2*z+1); else { tree tmp1=quiry(l,mid,2*z); tree tmp2=quiry(mid+1,r,2*z+1); tree tmp3;tmp3.l=l;tmp3.r=r; pushup(tmp1,tmp2,tmp3); //printf("%d %d %d\n",tmp3.l,tmp3.r,tmp3.Max); return tmp3; } } void build(int l,int r,int z) { b[z].l=l;b[z].r=r; if(l==r){ b[z].Max=b[z].Ls=b[z].Rs=b[z].sum=a[l]; b[z].Lto=b[z].Rto=b[z].Ml=b[z].Mr=l; return ; } int mid=(l+r)/2; build(l,mid,2*z); build(mid+1,r,2*z+1); update(z); // printf("l=%d, r=%d, max= %d, %d, %d\n",b[z].l,b[z].r,b[z].Max,b[z].Ls,b[z].Rs); } int main() { freopen("hill.in","r",stdin); freopen("hill.out","w",stdout); // freopen("in.txt","r",stdin); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,n,1); int L,R; for(int i=1;i<=m;i++){ scanf("%d%d",&L,&R); /// cout<<i<<" "; tree ans=quiry(L,R,1); printf("%d %d %d\n",ans.Ml,ans.Mr,ans.Max); } // while(1); return 0; }
