好像没有什么高级数据结构能够很高效地实现这个东西；
那就上万能的分块，我们用一些数形结合的思想，把下标看成横坐标，前缀和的值看成纵坐标；
给区间内每个数都加k相当于相邻两点的斜率都加上k；
这种东西我们可以考虑用凸包来维护，因为根据凸包的几何意义，显然最值点在凸包上；
根据凸包的构造方式，相邻两点的斜率都加上k，在凸包中的点集是不变的，这就很好了；
每次二分出斜率为零的地方就好了；
#include<iostream> #include<cstring> #include<cmath> #include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const ll inf=1e16; const int maxn=100010; int bo,tu[400][400],siz[400],pos[maxn]; //fir是他被包含在某一个区间加中时，对这个块的贡献；arr时不包含；d是这个块被区间加了多少； int m,sta[400],top,n,cnt; ll h[maxn],fir[400],arr[400],d[400]; inline double xl(int x,int y){return double(h[y]-h[x])/double(y-x);} //good void build(int x){//在x这一块中构造凸包 int be=(x-1)*bo+1,en=min(x*bo,n); top=0;sta[++top]=be; for(int i=be+1;i<=en;++i){ while(top>=2&&xl(sta[top-1],sta[top])<xl(sta[top-1],i))top--; sta[++top]=i; } sta[0]=0;sta[top+1]=n+1; siz[x]=top; for(int i=0;i<=top+1;++i)tu[x][i]=sta[i]; } // //good void pushdown(int x){ ll tmp=fir[x]; int be=(x-1)*bo+1,en=min(x*bo,n); for(int i=be;i<=en;++i){ h[i]+=tmp;tmp+=d[x];h[i]+=arr[x]; } fir[x]=d[x]=arr[x]=0; } // //good ll cal(int p){ if(p==0||p==n+1)return -inf; int x=pos[p]; return h[p]+fir[x]+d[x]*(p-((x-1)*bo+1))+arr[x]; } // //good ll fin(int x){ int l=1,r=siz[x]; ll h1,h2,h3; while(l<=r){ int mid=(l+r)>>1; h1=cal(tu[x][mid-1]),h2=cal(tu[x][mid]),h3=cal(tu[x][mid+1]); if(h1<h2&&h2<h3)l=mid+1; else { if(h1>h2&&h2>h3)r=mid-1; else{return h2;} } } } // int main(){ cin>>n; bo=(int)sqrt(n); cnt=(n-1)/bo+1; h[0]=h[n+1]=-inf; for(int i=1;i<=n;++i){ scanf("%lld",&h[i]); } for(int i=2;i<=n;++i){ h[i]+=h[i-1]; } for(int i=1;i<=n;++i){ pos[i]=(i-1)/bo+1; } for(int i=1;i<=cnt;++i)build(i); cin>>m; int op,x,y,l,r; ll k,tmp,ans; for(int i=1;i<=m;++i){ scanf("%d%d%d",&op,&x,&y); if(!op){ scanf("%lld",&k); l=pos[x];r=pos[y]; tmp=k*(l*bo+1-x+1); for(int i=l+1;i<=r-1;++i){ fir[i]+=tmp;d[i]+=k; tmp+=bo*k; } pushdown(l); tmp=k; for(int i=x;i<=min(y,min(l*bo,n));++i) h[i]+=tmp,tmp+=k; build(l); pushdown(r); if(l!=r){ tmp=k*((r-1)*bo-x+2); for(int i=(r-1)*bo+1;i<=y;++i){ h[i]+=tmp;tmp+=k; } } tmp=k*(y-x+1); for(int i=y+1;i<=min(r*bo,n);++i)h[i]+=tmp; build(r); for(int i=r+1;i<=cnt;++i)arr[i]+=tmp; } else{ l=pos[x];r=pos[y];ans=-inf; for(int i=l+1;i<r;++i) ans=max(ans,fin(i)); for(int i=x;i<=min(y,min(l*bo,n));++i){ ans=max(ans,cal(i)); } if(l!=r){ for(int i=(r-1)*bo+1;i<=y;++i){ ans=max(ans,cal(i)); } } printf("%lld ",ans); } } system("pause"); return 0; }