题解：P11454 [USACO24DEC] 2D Conveyer Belt S

· · 题解

这题一眼和连通性相关，就是看能不能连到矩阵外。

我们发现 Farmer John 的一次操作代表着将一个点的 4 连通变成了 1 连通，也就是说我们删掉了与一个点相连的 3 条边。

然后我们发现连通性和删边这一组关键词似曾相识。

于是我们想到了[JSOI2008] 星球大战的做法，开始挥舞造物主的魔法棒时光倒流。

具体来说，我们可以求出将所有操作处理完后的答案，再一步一步的将操作倒过来进行。

这样，我们就可以把删边改成加边，就可以好维护一些。

我们首先考虑如何求出所有操作完后的答案。

我们可以对于边界上的点看看能不能连出边界，如果可以就以它为起点，dfs 遍历所有能到达它的点，并打上标记，打过标记的点就不用遍历了。

然后等于询问的时光倒流，我们就看解放的那个点周围有没有可以走到外界的点（即之前打过标记的点）或是否在边界，如果有，那么这个点与所有能到达它的点都能走到外界。

时间复杂度 \mathcal{O}(m+n)。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Q=2e5+10;
int n,m,sum;
int ans[Q];
char s[1010][1010];
int v[1010][1010];
int to[1010][1010][4];
struct Qu{
    int x,y;
    char ch;
}r[Q];
const int dx[]={0,0,-1,1};
const int dy[]={-1,1,0,0};
void dfs(int x,int y){
    v[x][y]=1,sum++;
    for(int i=0;i<4;++i){
        int xx=x+dx[i],yy=y+dy[i];
        if(xx<1||xx>n||yy<1||yy>n||v[xx][yy]) continue;
        if(!to[xx][yy][i^1]) continue;//左^1为右，其他同理，处理能达到x点的点
        dfs(xx,yy);
    }
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) s[i][j]='?';//一开始全部为？
    for(int i=1;i<=m;i++){
        cin>>r[i].x>>r[i].y>>r[i].ch;
        s[r[i].x][r[i].y]=r[i].ch;//m次操作后的矩阵
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){//处理出每个点是否能向每个方向走
            //0代表左，1代表右，2代表上，3代表下
            if(s[i][j]=='?'||s[i][j]=='L') to[i][j][0]=1;
            if(s[i][j]=='?'||s[i][j]=='R') to[i][j][1]=1;
            if(s[i][j]=='?'||s[i][j]=='U') to[i][j][2]=1;
            if(s[i][j]=='?'||s[i][j]=='D') to[i][j][3]=1;
        }
    }
    for(int i=1;i<=n;i++){//处理第一行
        if(v[1][i]||!to[1][i][2]) continue;
        dfs(1,i);
    }
    for(int i=1;i<=n;i++){//处理第n行
        if(v[n][i]||!to[n][i][3]) continue;
        dfs(n,i);
    }
    for(int i=1;i<=n;i++){//处理第一列
        if(v[i][1]||!to[i][1][0]) continue;
        dfs(i,1);
    }
    for(int i=1;i<=n;i++){//处理第n列
        if(v[i][n]||!to[i][n][1]) continue;
        dfs(i,n);
    }
    for(int w=m;w>=1;w--){
        ans[w]=sum;
        int x=r[w].x,y=r[w].y;
        s[x][y]='?';
        for(int i=0;i<4;i++) to[x][y][i]=1;//解放这个点
        if(v[x][y]) continue;
        int p=0;
        for(int i=0;i<4;i++){//看看周围有没有已解放的点或是否在边界
            int xx=x+dx[i],yy=y+dy[i];
            if(xx<1||xx>n||yy<1||yy>n) {p=1;break;}
            if(v[xx][yy]) {p=1;break;}
        }
        if(!p) continue;
        dfs(x,y);//以这个点为起点dfs
    }
    for(int i=1;i<=m;i++) cout<<n*n-ans[i]<<"\n";//sum记录的是能走出去的点，所以要用总点数减去
    return 0;
}