ARC190C 题解

· · 题解

写篇题解，来给 THUWC 攒功德了。

这篇题解给出的做法不需要考虑 h 和 w 之间的大小关系，而且跑得还挺快的。

考虑修改一个点的权值之后整个网格图权值的变化量是什么。

显然，点权修改只会对经过这个点的路径的权值产生影响。

如果我们记 f_{i,j} 表示所有从 (1,1) 走到 (i,j) 的路径权值之和，g_{i,j} 表示所有从 (i,j) 走到 (h,w) 的路径权值之和，则有：

f_{i,j}=(f_{i-1,j}+f_{i,j-1})\times a_{i,j} g_{i,j}=(g_{i+1,j}+g_{i,j+1})\times a_{i,j}

注意特判 f_{1,1}=a_{1,1}，g_{h,w}=a_{h,w}。以上两个式子本质上是 DP。

且经过点 (x,y) 的所有路径的权值之和可以被表示为：

(f_{x-1,y}+f_{x,y-1})\times a_{x,y}\times(g_{x+1,y}+g_{x,y+1})

这个式子的意义是，由于一条路径可以从上方 / 左方进入点 (x,y)，又可以从下方 / 右方离开点 (x,y)，使用乘法原理计算即可。

如果我们以 (1,1) 为左上角，(n,m) 为右下角画出网格图 a，那么，在修改点 (x,y) 的权值之后，所有位于 (x,y) 右下方的 f 值也会被修改；同理，所有位于 (x,y) 左上方的 g 值也会被修改。我们得到的信息只有这些位置的 f 或 g 值需要被修改，至于具体修改为何值，我们目前是不知道的。

对此，我们可以采取如下方法：新建布尔数组 bf、bg 分别记录网格图中每一个位置的 f、g 值是否被修改。

进一步，我们会发现题目中给的限制会带来一个非常好的性质：每次修改的位置是相邻的，这意味着每次修改之后 bf 与 bg 的改动不会很大。

具体地，由于每次修改的位置相邻，于是操作后 bf、bg 中只有一个会被改动，而且它只会有一行或一列会被新赋值为 1。

至于究竟是 bf 还是 bg 会有修改，以及究竟修改一行还是一列，这个只与询问中所给出的 UDLR 有关，读者可以自己尝试画一画、推导结论，因为一一讲述实在很麻烦。

那么到现在，我们只剩下两个问题了。

在处理新的询问时，如果我们需要知道某个点的 f、g 值，而此处的 f、g 值恰好由于之前 a 数组被修改而修改了，应该如何处理？

使用记忆化搜索解决。以 f 为例，查询 f_{x,y} 时，如果 bf_{x,y}=0，那么可以直接调用 f_{x,y}；否则，先递归查询 f_{x-1,y}、f_{x,y-1}，再用新的 f_{x-1,y}、f_{x,y-1} 来更新 f_{x,y}，最后再将 bf_{x,y} 设置为 0。g 同理。注意特判 f_{1,1} 与 g_{h,w} 的处理。

看上去这么暴力的算法，其时间复杂度真的可以接受吗？

在上文的基础上，再加一点点剪枝就可以了。

首先注意到很重要的一点：记忆化搜索的总时间复杂度不会大于修改 bf、bg 的总时间复杂度。这是因为记忆化搜索的时候只会访问 bf、bg 为 1 的位置，并且随即将其清零。

所以不妨计算一下我们对 bf、bg 的总修改次数。到目前为止，每次对 a 的修改会带来在 bf、bg 上的一整行 / 列的修改，单次复杂度可以达到 O(\max(h,w))，总复杂度可以达到 O(q\max(h,w))，不可接受。

考虑剪枝，在修改 bf、bg 时，如果发现某位置 bf、bg 已经为 1 之后，立即结束修改并处理下一个询问。这让询问的单次均摊复杂度变为 O(\frac{hw}{h+w})=O(\min(h,w))\le O(\sqrt{hw})。

于是我们以一个比较水到渠成的思路解决了这道难度评分 3010 的题目。

只可惜因为 f_{1,1}、g_{h,w} 等边界错误调试时间过长，我没有在赛时做出此题。

代码主要在赛时完成，仅供参考。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>

const int N=2e5+10,mod=998244353;

int n,m,Q,x,y,ans;

int dx[200],dy[200];

vector<int> a[N],f[N],g[N];
vector<bool> bf[N],bg[N];

void upf(int i,int j){
    if(i==1&&j==1) f[i][j]=a[i][j];
    else f[i][j]=(f[i-1][j]+f[i][j-1])*a[i][j]%mod;
}

void upg(int i,int j){
    if(i==n&&j==m) g[i][j]=a[i][j];
    else g[i][j]=(g[i+1][j]+g[i][j+1])*a[i][j]%mod;
}

int fet(int i,int j){
    if(i==1&&j==1) return bf[i][j]=0,a[i][j];
    if(!bf[i][j]) return f[i][j];
    bf[i][j]=0;
    return f[i][j]=(fet(i-1,j)+fet(i,j-1))*a[i][j]%mod;
}

int get(int i,int j){
    if(i==n&&j==m) return bg[i][j]=0,a[i][j];
    if(!bg[i][j]) return g[i][j];
    bg[i][j]=0;
    return g[i][j]=(get(i+1,j)+get(i,j+1))*a[i][j]%mod;
}

signed main(){
    ios::sync_with_stdio(false);
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);

    cin>>n>>m;
    dx['U']=-1;
    dx['D']=1;
    dy['L']=-1;
    dy['R']=1;

    for(int i=0;i<=n+1;++i) a[i].resize(m+10),bf[i].resize(m+10),bg[i].resize(m+10),f[i].resize(m+10),g[i].resize(m+10);

    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin>>a[i][j];
            upf(i,j);
        }
    }

    for(int i=n;i;--i){
        for(int j=m;j;--j){
            upg(i,j);
        }
    }

    ans=g[1][1];

    int x,y,v,op;
    char ch;
    cin>>Q>>x>>y;

    for(int i=1;i<=x;++i){
        for(int j=1;j<=y;++j){
            bg[i][j]=1;
        }
    }

    for(int i=x;i<=n;++i){
        for(int j=y;j<=m;++j){
            bf[i][j]=1;
        }
    }

    while(Q--){
        cin>>ch>>v;
        op=(int)ch;
        bf[x][y]=bg[x][y]=1;
        x+=dx[op],y+=dy[op];
        int sf=fet(x-1,y)+fet(x,y-1),sg=get(x+1,y)+get(x,y+1);
        if(x==1&&y==1) sf=1;
        if(x==n&&y==m) sg=1;

        ans=(ans+sf*sg%mod*(v-a[x][y])%mod+mod)%mod;
        a[x][y]=v;
        fet(x,y),get(x,y);

        cout<<ans<<'\n';

        if(dx[op]<0||dy[op]<0){
            for(int i=x,j=y;i<=n&&j<=m;i-=dy[op],j-=dx[op]){
                if(bf[i][j]) break;
                bf[i][j]=1;
            }
        }

        if(dx[op]>0||dy[op]>0){
            for(int i=x,j=y;i&&j;i-=dy[op],j-=dx[op]){
                if(bg[i][j]) break;
                bg[i][j]=1;
            }
        }
    }

    return 0;
}