题解：P5620 [DBOI2019] 捡币

ivyjiao · 2024-11-18 08:42:55 · 题解

做捡币题就是持矢。——1jia1

二维分块板子，好题无人啊。

感觉这个科技还没普及的样子。

二维分块跟普通分块没差多少，如果参考我之前的分块学习笔记，会发现本题无非就是操作 1+ 查询 1,2 而已，只不过边界的处理变得麻烦了。

看以下的图，我们如果把整块剔除出去，那么剩下的就是边的部分（彩色部分）。

直接套用两层一维分块的循环是不行的，这样只能查到角落部分（参见这个讨论），我们需要每次查到一个角落 + 一个大边，上图就是一种处理方式，局部代码如下（解法不唯一）：

for(int i=x1;i<=R[bel[x1]];i++) for(int j=y1;j<=L[bel[y2]]-1;j++) ans+=a[i][j]+lz[bel[i]][bel[j]];
for(int i=L[bel[x2]];i<=x2;i++) for(int j=R[bel[y1]]+1;j<=y2;j++) ans+=a[i][j]+lz[bel[i]][bel[j]];
for(int i=x1;i<=L[bel[x2]]-1;i++) for(int j=L[bel[y2]];j<=y2;j++) ans+=a[i][j]+lz[bel[i]][bel[j]];
for(int i=R[bel[x1]]+1;i<=x2;i++) for(int j=y1;j<=R[bel[y1]];j++) ans+=a[i][j]+lz[bel[i]][bel[j]];

这样前三个操作就完事了，时间复杂度 O(qn\sqrt n)，瓶颈在于处理边的时候需要 O(n\sqrt n) 的循环。至于捡币操作，由于只有一次，所以直接 O(n^2) DP 即可。

总的时间复杂度为 O(qn\sqrt n+n^2)，可以通过。

完整代码如下：

#include<bits/stdc++.h>
#define int long long
#define y1 IAKIOI
using namespace std;
const int N=1001;
int n,m,q,op,x1,y1,x2,y2,blo,cnt,L[N],R[N],bel[N],a[N][N],lz[N][N],b[N][N],c[N][N],dp[N][N],sb;
void build(){
    blo=sqrt(n);
    cnt=(n+blo-1)/blo;
    for(int i=1;i<=cnt;i++){
        L[i]=R[i-1]+1;
        R[i]=i*blo;
    }
    R[cnt]=n;
    for(int i=1;i<=n;i++) bel[i]=(i-1)/blo+1;
}
void add(int x1,int y1,int x2,int y2,int k){
    if(bel[x1]==bel[x2]||bel[y1]==bel[y2]){
        for(int i=x1;i<=x2;i++){
            for(int j=y1;j<=y2;j++){
                a[i][j]+=k;
                b[bel[i]][bel[j]]+=k;
                c[bel[i]][bel[j]]=max(c[bel[i]][bel[j]],a[i][j]+lz[bel[i]][bel[j]]);
            }
        }
        return;
    }
    for(int i=x1;i<=R[bel[x1]];i++){
        for(int j=y1;j<=L[bel[y2]]-1;j++){
            a[i][j]+=k;
            b[bel[i]][bel[j]]+=k;
            c[bel[i]][bel[j]]=max(c[bel[i]][bel[j]],a[i][j]+lz[bel[i]][bel[j]]);
        }
    }
    for(int i=L[bel[x2]];i<=x2;i++){
        for(int j=R[bel[y1]]+1;j<=y2;j++){
            a[i][j]+=k;
            b[bel[i]][bel[j]]+=k;
            c[bel[i]][bel[j]]=max(c[bel[i]][bel[j]],a[i][j]+lz[bel[i]][bel[j]]);
        }
    }
    for(int i=x1;i<=L[bel[x2]]-1;i++){
        for(int j=L[bel[y2]];j<=y2;j++){
            a[i][j]+=k;
            b[bel[i]][bel[j]]+=k;
            c[bel[i]][bel[j]]=max(c[bel[i]][bel[j]],a[i][j]+lz[bel[i]][bel[j]]);
        }
    }
    for(int i=R[bel[x1]]+1;i<=x2;i++){
        for(int j=y1;j<=R[bel[y1]];j++){
            a[i][j]+=k;
            b[bel[i]][bel[j]]+=k;
            c[bel[i]][bel[j]]=max(c[bel[i]][bel[j]],a[i][j]+lz[bel[i]][bel[j]]);
        }
    }
    for(int i=bel[x1]+1;i<bel[x2];i++){
        for(int j=bel[y1]+1;j<bel[y2];j++){
            lz[i][j]+=k;
            b[i][j]+=k*blo*blo;
            c[i][j]+=k;
        }
    }
}
int qsum(int x1,int y1,int x2,int y2){
    int ans=0;
    if(bel[x1]==bel[x2]||bel[y1]==bel[y2]){
        for(int i=x1;i<=x2;i++) for(int j=y1;j<=y2;j++) ans+=a[i][j]+lz[bel[i]][bel[j]];
        return ans;
    }
    for(int i=x1;i<=R[bel[x1]];i++) for(int j=y1;j<=L[bel[y2]]-1;j++) ans+=a[i][j]+lz[bel[i]][bel[j]];
    for(int i=L[bel[x2]];i<=x2;i++) for(int j=R[bel[y1]]+1;j<=y2;j++) ans+=a[i][j]+lz[bel[i]][bel[j]];
    for(int i=x1;i<=L[bel[x2]]-1;i++) for(int j=L[bel[y2]];j<=y2;j++) ans+=a[i][j]+lz[bel[i]][bel[j]];
    for(int i=R[bel[x1]]+1;i<=x2;i++) for(int j=y1;j<=R[bel[y1]];j++) ans+=a[i][j]+lz[bel[i]][bel[j]];
    for(int i=bel[x1]+1;i<bel[x2];i++) for(int j=bel[y1]+1;j<bel[y2];j++) ans+=b[i][j];
    return ans;
}
int qmax(int x1,int y1,int x2,int y2){
    int ans=0;
    if(bel[x1]==bel[x2]||bel[y1]==bel[y2]){
        for(int i=x1;i<=x2;i++) for(int j=y1;j<=y2;j++) ans=max(ans,a[i][j]+lz[bel[i]][bel[j]]);
        return ans;
    }
    for(int i=x1;i<=R[bel[x1]];i++) for(int j=y1;j<=L[bel[y2]]-1;j++) ans=max(ans,a[i][j]+lz[bel[i]][bel[j]]);
    for(int i=L[bel[x2]];i<=x2;i++) for(int j=R[bel[y1]]+1;j<=y2;j++) ans=max(ans,a[i][j]+lz[bel[i]][bel[j]]);
    for(int i=x1;i<=L[bel[x2]]-1;i++) for(int j=L[bel[y2]];j<=y2;j++) ans=max(ans,a[i][j]+lz[bel[i]][bel[j]]);
    for(int i=R[bel[x1]]+1;i<=x2;i++) for(int j=y1;j<=R[bel[y1]];j++) ans=max(ans,a[i][j]+lz[bel[i]][bel[j]]);
    for(int i=bel[x1]+1;i<bel[x2];i++) for(int j=bel[y1]+1;j<bel[y2];j++) ans=max(ans,c[i][j]);
    return ans;
}
signed main(){
    cin>>n>>m>>q;
    build();
    while(q--){
        cin>>op>>x1>>y1>>x2>>y2;
        if(op>0){
            sb++;
            add(x1,y1,x2,y2,op);
            if(sb==m) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j]+lz[bel[i]][bel[j]];
        }
        else if(!op) cout<<qmax(x1,y1,x2,y2)<<endl;
        else cout<<qsum(x1,y1,x2,y2)<<endl;
    }
    cout<<dp[n][n];
}