P5897 题解

Problem Links

题目大意

给定一个 $n\times m$ 的网格图，边有边权，移动时只能向左右或下方移动，支持如下两种操作。

• 修改某条边变的边权，共 $C$ 次。
• 询问从 $(1,x)\to (n,y)$ 的最短路，共 $Q$ 次。

数据范围：$n\le 5000,m\le 200,C\le 500,Q\le 2\times 10^5$。

思路分析

显然考虑矩阵线段树维护，线段树上每个矩阵维护 $f_{i,j}$ 表示 $(l,i)\to (r,j)$ 的最短路，合并时做 $(\min,+)$ 矩阵乘法。

但这样预处理复杂度就是 $\mathcal O(nm^3\log n)$ 的，考虑优化，注意到 $f_{i,j}=\min\{fl_{i,k}+fr_{k,j}\}$，而转移式中的 $k$ 具有决策单调性，记最优的 $k$ 为 $o_{i,j}$，则有 $o_{i-1,j}\le o_{i,j}\le o_{i,j+1}$，此时矩阵乘法复杂度被优化到了 $\mathcal O(m^2)$。

但此时空间复杂度也是 $\mathcal O(nm^2)$ 的，无法接受，考虑分块以平衡，把连续 $B$ 行的状态压缩到线段树的一个叶子上，每次更新时用 $\mathcal O(Bm^2)$ 的暴力 dp 处理。

时间复杂度 $\mathcal O(nm^2\log n+C\times m^2(B+\log \dfrac nB)+Q)$，空间复杂度 $\mathcal O(\dfrac{nm^2}B)$。

取 $B=10\sim 20$ 均可。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005,MAXM=205;
int n,m,q,Wrow[MAXN][MAXM],Wcol[MAXN][MAXM];
struct Info {
    int f[MAXM][MAXM];
    inline void Merge(const Info &X,const Info &Y) {
        static int o[MAXM][MAXM];
        memset(o,0,sizeof(o)),memset(f,0x3f,sizeof(f));
        for(int l=1;l<=m;++l) for(int r=m;r>=1;--r) {
            int L=o[l-1][r]?o[l-1][r]:1,R=o[l][r+1]?o[l][r+1]:m;
            for(int i=L;i<=R;++i) if(X.f[l][i]+Y.f[i][r]<f[l][r]) {
                f[l][r]=X.f[l][i]+Y.f[i][r],o[l][r]=i;
            }
        }
    }
    inline void Init(int x,int y) {
        for(int i=1;i<=m;++i) {
            for(int j=i,sum=0;j<=m;++j) f[i][j]=sum,sum+=Wcol[x][j];
            for(int j=i,sum=0;j>=1;--j) f[i][j]=sum,sum+=Wcol[x][j-1];
            for(int j=1;j<=m;++j) f[i][j]+=Wrow[x][j];
            for(int k=x+1;k<=y;++k) {
                for(int j=2;j<=m;++j) f[i][j]=min(f[i][j],f[i][j-1]+Wcol[k][j-1]);
                for(int j=m-1;j>=1;--j) f[i][j]=min(f[i][j],f[i][j+1]+Wcol[k][j]);
                for(int j=1;j<=m;++j) f[i][j]+=Wrow[k][j];
            }
        }
    }
};
const int B=10,MAXS=1005;
int siz=0,rt,ls[MAXS],rs[MAXS]; //segment Tree
Info tr[MAXS];
int bel[MAXN],lp[MAXN],rp[MAXN],cnt; //blocks
inline void Build(int l,int r,int &p) {
    p=++siz;
    if(l==r) return tr[p].Init(lp[l],rp[r]);
    int mid=(l+r)>>1;
    Build(l,mid,ls[p]),Build(mid+1,r,rs[p]);
    tr[p].Merge(tr[ls[p]],tr[rs[p]]);
}
inline void Modify(int u,int l,int r,int p) {
    if(l==r) return tr[p].Init(lp[u],rp[u]);
    int mid=(l+r)>>1;
    if(u<=mid) Modify(u,l,mid,ls[p]);
    else Modify(u,mid+1,r,rs[p]);
    tr[p].Merge(tr[ls[p]],tr[rs[p]]);
}
signed main() {
    freopen("kangaroo.in","r",stdin);
    freopen("kangaroo.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) for(int j=1;j<m;++j) scanf("%d",&Wcol[i][j]);
    for(int i=1;i<n;++i) for(int j=1;j<=m;++j) scanf("%d",&Wrow[i][j]);
    cnt=(n+B-1)/B;
    fill(lp+1,lp+cnt+1,n+1),fill(rp+1,rp+cnt+1,0);
    for(int i=1;i<=n;++i) {
        bel[i]=(i+B-1)/B;
        lp[bel[i]]=min(lp[bel[i]],i),rp[bel[i]]=max(rp[bel[i]],i);
    }
    Build(1,cnt,rt);
    scanf("%d",&q);
    while(q--) {
        int opt;
        scanf("%d",&opt);
        if(opt==1) {
            int i,j,v;
            scanf("%d%d%d",&i,&j,&v),++i,++j;
            Wcol[i][j]=v;
            Modify(bel[i],1,cnt,rt);
        }
        if(opt==2) {
            int i,j,v;
            scanf("%d%d%d",&i,&j,&v),++i,++j;
            Wrow[i][j]=v;
            Modify(bel[i],1,cnt,rt);
        }
        if(opt==3) {
            int x,y;
            scanf("%d%d",&x,&y),++x,++y;
            printf("%d\n",tr[1].f[x][y]);
        }
    }
    return 0;
}