题解：P4513 小白逛公园

· · 题解

补一个分块做法。

题意简化一下就是单点修改和找区间最大子段和。由于是分块，无法像线段树一样合并，并且值会有负数，所以使用动规。

另外维护了 $maxl,maxr,maxk,ans$ 四个数组，分别表示每个块从左端点开始最大子段和，从右端点开始最大子段和，块中最大子段和以及块中所有数的和。 考虑如何转移，首先 $dp_{i,0}$ 有三种情况：不包含第 $i$ 个块，第 $i$ 个块与前面的块连接或只包含第 $i$ 个块。第一种情况就是直接取 $dp_{i-1,1}$，而第二种情况因为要与前面的块连接，所以必须要取到左端点，即 $dp_{i-1,1} + maxl_{i}$，对于第三种情况，取当前块内的最大子区间和 $maxk_{i}$。 由于 $dp_{i,1}$ 代表的是与下一个块连接是的最大子段和，所以必须取到右端点，这里有两种情况：只与下一个块连接或将上一个块与下一个块相连。分别表示为 $maxr_{i}$ 和 $dp_{i-1,1} + ans_{j}$。 整理一下即可得到如下转移方程： $\begin{cases}dp_{i,0}=max(dp_{i-1,1},max(dp_{i-1,1}+maxl_{i},maxk_{i}))\\dp_{i,1}=max(maxr_{i},dp_{i-1,1}+ans_{i})\end{cases}

至于单点修改操作以及其它数组的维护不多赘述，只讲一下如何维护 maxk 数组。

这里用到了前缀和求最大子段和，即对于每一个前缀和 qzh_{i}， 用它减去前面的最小前缀和，最后将这些值取最大即可得到最大子段和。

注意每次单点修改时要一同修改 qzh,maxl,maxr,maxk 数组，为降低修改前缀和数组的时间复杂度，开的是二维数组，每个块单独对应一维。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
    char ch=getchar();
    int r=0,w=1;
    while(ch<'0'||ch>'9') w=ch=='-'?-1:w,ch=getchar();
    while(ch>='0'&&ch<='9') r=r*10+ch-'0',ch=getchar();
    return r*w;
}
void write(long long n){
    if(n<0) putchar('-'),n*=-1;
    if(n>9) write(n/10);
    putchar(n%10+'0');
}
const int N=5e5+1,M=sqrt(5e5+1)*2;
int n,m,cnt,maxx,k,l,r,p,s,ll,rr,lk,rk;
int xl[N],maxl[M],maxr[M],maxk[M];
int ans[M],qzh[M][M],AC[N],cc[N];
int x[M],y[M],fk[N],dp[M][2];
signed main(){
    cin>>n>>m;
    cnt=sqrt(n);
    for(int i=1;i<=cnt;i++){
        x[i]=y[i-1]+1;
        y[i]=x[i]+cnt-1;
        for(int j=x[i];j<=y[i];j++){
            fk[j]=i;
        }
    } 
    if(y[cnt]<n){
        cnt++;
        x[cnt]=y[cnt-1]+1;
        y[cnt]=n;
        for(int i=x[cnt];i<=n;i++){
            fk[i]=cnt;
        }
    }
    for(int i=1;i<=n;i++){
        cin>>xl[i];
        ans[fk[i]]+=xl[i];
    }
    for(int i=1;i<=fk[n];i++){
        for(int j=x[i];j<=y[i];j++){
            qzh[i][j-x[i]+1]=qzh[i][j-x[i]]+xl[j];
        }
    }
    for(int i=1;i<=fk[n];i++){
        maxl[i]=maxr[i]=-LLONG_MAX;
        cnt=0;
        for(int j=x[i];j<=y[i];j++){
            cnt+=xl[j];
            maxl[i]=max(maxl[i],cnt);
        }
        cnt=0;
        for(int j=y[i];j>=x[i];j--){
            cnt+=xl[j];
            maxr[i]=max(maxr[i],cnt);
        }
        AC[x[i]]=cnt=qzh[i][1];
        for(int j=x[i]+1;j<=y[i];j++){
            cnt=min(cnt,qzh[i][j-x[i]+1]);
            AC[j]=cnt;
        }
        maxk[i]=qzh[i][1];
        for(int j=x[i]+1;j<=y[i];j++){
            maxk[i]=max(maxk[i],max(qzh[i][j-x[i]+1],qzh[i][j-x[i]+1]-AC[j-1]));
        }
    }
    for(int i=1;i<=m;i++){
        cin>>k;
        if(k==1){
            cin>>l>>r;
            if(l>r){
                swap(l,r);
            }
            ll=rr=-LLONG_MAX;
            cnt=0;
            for(int j=min(r,y[fk[l]]);j>=l;j--){
                cnt+=xl[j];
                ll=max(ll,cnt);
            }
            cc[0]=0;
            for(int j=l;j<=min(r,y[fk[l]]);j++){
                cc[j-l+1]=cc[j-l]+xl[j];
            }
            AC[l]=cnt=cc[1];
            for(int j=l+1;j<=min(r,y[fk[l]]);j++){
                cnt=min(cnt,cc[j-l+1]);
                AC[j]=cnt;
            }
            lk=cc[1];
            for(int j=l+1;j<=min(r,y[fk[l]]);j++){
                lk=max(lk,max(cc[j-l+1],cc[j-l+1]-AC[j-1]));
            }
            if(fk[l]!=fk[r]){
                cnt=0;
                for(int j=x[fk[r]];j<=r;j++){
                    cnt+=xl[j];
                    rr=max(rr,cnt);
                }
                AC[x[fk[r]]]=cnt=qzh[fk[r]][1];
                for(int j=x[fk[r]]+1;j<=r;j++){
                    cnt=min(cnt,qzh[fk[r]][j-x[fk[r]]+1]);
                    AC[j]=cnt;
                }
                rk=qzh[fk[r]][1];
                for(int j=x[fk[r]]+1;j<=r;j++){
                    rk=max(rk,max(qzh[fk[r]][j-x[fk[r]]+1],qzh[fk[r]][j-x[fk[r]]+1]-AC[j-1]));
                }   
            }
            else{
                cout<<lk<<endl;
                continue;
            }
            cnt=max(lk,rk);
            dp[fk[l]][1]=ll;
            for(int j=fk[l]+1;j<fk[r];j++){
                dp[j][0]=max(dp[j-1][1],max(dp[j-1][1]+maxl[j],maxk[j]));
                dp[j][1]=max(maxr[j],dp[j-1][1]+ans[j]);
            }
            dp[fk[r]][0]=max(dp[fk[r]-1][1],dp[fk[r]-1][1]+rr);
            for(int j=fk[l]+1;j<=fk[r];j++){
                cnt=max(cnt,dp[j][0]);
            }
            cout<<cnt<<endl;
        }
        else{
            cin>>p>>s;
            ans[fk[p]]-=xl[p];
            xl[p]=s;
            ans[fk[p]]+=xl[p];
            for(int j=x[fk[p]];j<=y[fk[p]];j++){
                qzh[fk[p]][j-x[fk[p]]+1]=qzh[fk[p]][j-x[fk[p]]]+xl[j];
            }
            maxl[fk[p]]=maxr[fk[p]]=-LLONG_MAX;
            cnt=0;
            for(int j=x[fk[p]];j<=y[fk[p]];j++){
                cnt+=xl[j];
                maxl[fk[p]]=max(maxl[fk[p]],cnt);
            }
            cnt=0;
            for(int j=y[fk[p]];j>=x[fk[p]];j--){
                cnt+=xl[j];
                maxr[fk[p]]=max(maxr[fk[p]],cnt);
            }
            AC[x[fk[p]]]=cnt=qzh[fk[p]][1];
            for(int j=x[fk[p]]+1;j<=y[fk[p]];j++){
                cnt=min(cnt,qzh[fk[p]][j-x[fk[p]]+1]);
                AC[j]=cnt;
            }
            maxk[fk[p]]=qzh[fk[p]][1];
            for(int j=x[fk[p]]+1;j<=y[fk[p]];j++){
                maxk[fk[p]]=max(maxk[fk[p]],max(qzh[fk[p]][j-x[fk[p]]+1],qzh[fk[p]][j-x[fk[p]]+1]-AC[j-1]));
            }
        }
    }
    return 0;
}