假設所有操作都是對整個序列的。考慮每個子區間，區間和與其被加的值構成一次函數關系。最大子段和相當于多個子區間取最大值，答案顯然就在這些一次函數構成的下凸殼上。如果預處理出凸殼，只要在凸殼上暴力跳就可以回答詢問了，因為加的都是正數，并且斜率不同的一次函數數量是O(n)的。暴力建凸殼的復雜度是O(n²)的。

　　那么考慮分塊。每個塊預處理出凸殼。區間加時，對于整塊在凸殼上暴跳，零散部分暴力重構。查詢時合并區間，類似于單點加的線段樹做法，維護塊內最大前綴和、最大后綴和。塊大小取n^1/3時最優。

　　造凸殼寫掛調了1h，退役了。

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 50010 #define NUM 2000 #define BLOCK 100 #define inf 10000000000000000ll char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() {int x=0,f=1;char c=getchar();while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();return x*f; } int n,m,pos[N],num,block; ll a[N],tmp[N],PRE[N],SUF[N]; struct line {ll k,b;ll f(ll x){return k*x+b;} }; ll cross(line x,line y){return (x.b-y.b-1)/(y.k-x.k)+1;} struct hull {line a[BLOCK];int cnt,cur;void ins(line x){while (cnt&&x.b>=a[cnt].b||cnt>1&&x.f(cross(a[cnt],a[cnt-1]))>a[cnt].f(cross(a[cnt],a[cnt-1]))) cnt--;a[++cnt]=x;}void clear(){cnt=0,cur=1,ins((line){0,0});}void jump(ll x){while (cur<cnt&&a[cur].f(x)<a[cur+1].f(x)) cur++;}ll get(ll x){return a[cur].f(x);} }; struct data {hull pre,suf,seq;int L,R;ll lazy,sum;void build(){for (int i=L;i<=R;i++) a[i]+=lazy;lazy=0;sum=0;for (int i=L;i<=R;i++) sum+=a[i];ll x=0;pre.clear();for (int i=L;i<=R;i++) pre.ins((line){i-L+1,x+=a[i]});x=0;suf.clear();for (int i=R;i>=L;i--) suf.ins((line){R-i+1,x+=a[i]});seq.clear();for (int k=1;k<=R-L+1;k++){ll s=-inf;x=0;for (int i=L;i<=L+k-1;i++) x+=a[i];for (int i=L+k-1;i<=R;i++) s=max(s,x),x+=a[i+1]-a[i-k+1];seq.ins((line){k,s});}}void add(int x){sum+=1ll*(R-L+1)*x,lazy+=x,pre.jump(lazy),suf.jump(lazy),seq.jump(lazy);}ll maxpre(){return pre.get(lazy);}ll maxsuf(){return suf.get(lazy);}ll maxseq(){return seq.get(lazy);} }f[NUM]; ll getseq(int l,int r) {ll s=0,ans=0;for (int i=l;i<=r;i++){s+=tmp[i];if (s<0) s=0;ans=max(ans,s);}return ans; } int main() { #ifndef ONLINE_JUDGEfreopen("bzoj5089.in","r",stdin);freopen("bzoj5089.out","w",stdout);const char LL[]="%I64d\n"; #elseconst char LL[]="%lld\n"; #endifn=read(),m=read();block=2*pow(n,1.0/3)+1;num=(n-1)/block+1;for (int i=1;i<=n;i++) a[i]=read();for (int i=1;i<=num;i++){f[i].L=f[i-1].R+1,f[i].R=min(n,f[i].L+block-1);for (int j=f[i].L;j<=f[i].R;j++) pos[j]=i;f[i].build();}while (m--){char c=getc();if (c=='A'){int l=read(),r=read(),x=read();if (pos[l]==pos[r]){for (int i=l;i<=r;i++) a[i]+=x;f[pos[l]].build();}else{for (int i=pos[l]+1;i<pos[r];i++) f[i].add(x);for (int i=l;i<=f[pos[l]].R;i++) a[i]+=x;f[pos[l]].build();for (int i=f[pos[r]].L;i<=r;i++) a[i]+=x;f[pos[r]].build();}}else{int l=read(),r=read();if (pos[l]==pos[r]){for (int i=l;i<=r;i++) tmp[i]=a[i]+f[pos[l]].lazy;printf(LL,getseq(l,r));}else{for (int i=l;i<=f[pos[l]].R;i++) tmp[i]=a[i]+f[pos[l]].lazy;for (int i=f[pos[r]].L;i<=r;i++) tmp[i]=a[i]+f[pos[r]].lazy;ll ans=max(getseq(l,f[pos[l]].R),getseq(f[pos[r]].L,r)),s;for (int i=pos[l]+1;i<pos[r];i++) ans=max(ans,f[i].maxseq());for (int i=pos[l];i<=pos[r];i++) PRE[i]=SUF[i]=0;s=0;for (int i=f[pos[l]].R;i>=l;i--) s+=tmp[i],SUF[pos[l]]=max(SUF[pos[l]],s);s=0;for (int i=f[pos[r]].L;i<=r;i++) s+=tmp[i],PRE[pos[r]]=max(PRE[pos[r]],s);for (int i=pos[l]+1;i<pos[r];i++) SUF[i]=max(f[i].maxsuf(),SUF[i-1]+f[i].sum);for (int i=pos[r]-1;i>pos[l];i--) PRE[i]=max(f[i].maxpre(),PRE[i+1]+f[i].sum);for (int i=pos[l];i<pos[r];i++) ans=max(ans,SUF[i]+PRE[i+1]);printf(LL,ans);}}}return 0; }

?

轉載于:https://www.cnblogs.com/Gloid/p/10073408.html

總結

以上是生活随笔為你收集整理的BZOJ5089 最大连续子段和（分块）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。