http://www.lydsy.com/JudgeOnline/problem.php?id=2388
带区间加修改，求区间内的最大前缀和。
设sum[i]代表i的前缀和，tag[i][j]代表i到j位置上每个数字都加上了tag[i][j],add[i][j]代表i到j位置上每个位置的前缀和都加上了add[i][j]。
对于区间[l,r]，设最大答案为ans，ans=max{add[l][r]+tag[l][r]×(i-l+1)+sum[i]|l≤i≤r}。
设x=(i-l+1),y=sum[i]，则有ans=add[l][r]+tag[l][r]×x+y，可以化简为y=-tag[l][r]×x+ans-add[l][r]，就是给定一些点，要最大化过某个点且斜率给定的直线的截距，维护上凸壳即可。
所以我们分块，对于每一块维护上凸壳，查询操作O(√nlog(n)),修改O(√n)。
注意重建某一块的上凸壳之前要标记下传。
#include<bits/stdc++.h> const int maxn=100015,maxb=415; typedef long long int64; using namespace std; int n,m,num,siz,idx[maxn]; int64 sum[maxn]; struct Tblock{ static const int maxsiz=415; static const double eps=1e-9; int l,r,top;int64 add,tag; struct Tpoint{int64 x,y;}stk[maxsiz]; void modify(int64 _add,int64 _tag){add+=_add;tag+=_tag;} double slope(Tpoint a,Tpoint b){return 1.0*(b.y-a.y)/(b.x-a.x);} void push_down(){for (int i=l;i<=r;++i) sum[i]+=tag*(i-l+1)+add;tag=add=0;} void rebuild(){ top=0; for (int i=l;i<=r;++i){ Tpoint cur=(Tpoint){i-l+1,sum[i]}; while (top>1&&slope(stk[top-1],stk[top])+eps<slope(stk[top],cur)) --top; stk[++top]=cur; } stk[0]=(Tpoint){stk[1].x-1,(int64)-1e18}; stk[top+1]=(Tpoint){stk[top].x+1,(int64)-1e18}; } int64 query(){ double k=-tag;int l=1,r=top; while (1){ int mid=(l+r)>>1; double lk=slope(stk[mid-1],stk[mid]),rk=slope(stk[mid],stk[mid+1]); if (lk+eps>=k&&rk<=eps+k) return stk[mid].y+tag*stk[mid].x+add; else if (rk>eps+k) l=mid+1;else r=mid-1; } } }block[maxb]; void init_block(){ siz=sqrt(n); for (int j,i=1;i<=n;i=j){ for (++num,j=i;j-i+1<=siz&&j<=n;++j) idx[j]=num; block[num].l=i;block[num].r=j-1;block[num].rebuild(); } } void init(){ scanf("%d",&n); for (int i=1;i<=n;++i){scanf("%lld",&sum[i]);sum[i]+=sum[i-1];} init_block(); } void modify(int l,int r,int64 v){ if (idx[l]==idx[r]){ block[idx[l]].push_down(); for (int i=l;i<=r;++i) sum[i]+=v*(i-l+1); for (int i=r+1;i<=block[idx[r]].r;++i) sum[i]+=v*(r-l+1); block[idx[l]].rebuild(); for (int i=idx[l]+1;i<=num;++i) block[i].modify(v*(r-l+1),0); } else{ block[idx[l]].push_down();block[idx[r]].push_down(); for (int i=l;i<=block[idx[l]].r;++i) sum[i]+=v*(i-l+1); for (int i=block[idx[r]].l;i<=r;++i) sum[i]+=v*(i-l+1); for (int i=r+1;i<=block[idx[r]].r;++i) sum[i]+=v*(r-l+1); block[idx[l]].rebuild();block[idx[r]].rebuild(); for (int i=idx[l]+1;i<=idx[r]-1;++i) block[i].modify(v*(block[idx[l]].r-l+1+siz*(i-idx[l]-1)),v); for (int i=idx[r]+1;i<=num;++i) block[i].modify(v*(r-l+1),0); } } int64 query(int l,int r){ int64 res=-1e18; if (idx[l]==idx[r]) for (int i=l;i<=r;++i) res=max(res,sum[i]+block[idx[i]].add+block[idx[i]].tag*(i-block[idx[i]].l+1)); else{ for (int i=l;i<=block[idx[l]].r;++i) res=max(res,sum[i]+block[idx[i]].add+block[idx[i]].tag*(i-block[idx[i]].l+1)); for (int i=block[idx[r]].l;i<=r;++i) res=max(res,sum[i]+block[idx[i]].add+block[idx[i]].tag*(i-block[idx[i]].l+1)); for (int i=idx[l]+1;i<=idx[r]-1;++i) res=max(res,block[i].query()); } return res; } void work(){ scanf("%d",&m); for (int i=1;i<=m;++i){ int t,l,r;int64 v; scanf("%d%d%d",&t,&l,&r); switch (t){ case 0:scanf("%lld",&v);modify(l,r,v);break; case 1:printf("%lld ",query(l,r));break; } } } int main(){ init(); work(); return 0; }