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

· · 题解

首先考虑什么样的方格是“不可用的”。显然有两种情况：在一个传送带构成的环上或在一个传送带构成的环内。

我们发现判断哪些方格在环内是比较困难的，我们不妨判断哪些方格是“可用的”，这是比较简单的。具体来讲，我们可以从边界开始 DFS，所有可以遍历到的方格都是“可用的”，其中能够遍历到的方格必须是 ? 或传送带方向与遍历的方向相反（比如方格 A 是“可用的”，而其左边的方格 B 上的传送带方向为 L，那么方格 B 也是“可用的”）。通过 DFS 可以 \mathcal{O}(n^2) 求出所有“可用的”方格，进而求出“不可用”的方格数量。

但是如果对于每一个询问都进行 DFS，显然会 TLE。我们正难则反，考虑对于最终情况先 DFS 求出最终的答案，再回溯，每次删掉某个传送带。

我们对删掉的传送带分类讨论：

  1. 若删掉的传送带本身就是“可用的”，删去后它还是“可用的”，对答案没有影响。

  2. 若删掉的传送带本身“不可用”：

    • 若删掉的传送带上下左右有至少一个方格是“可用的”，那么显然这个传送带也会变得“可用”，可以通过 DFS 来求出随之变得“可用的”方格数量，方法同上。

    • 否则，这个传送带肯定依旧是“不可用的”。可以手动模拟几组数据发现规律我们考虑如何证明。

      • 如果这个方格在某个环内，那么它无论怎么变必然出不去这个环，说明它是“不可用的”。

      • 如果这个方格在某个环上，那么与其相邻的四个方格中至少有一个是在这个环外的，而这个（些）点也是“不可用的”，说明这些点也在环内或环上，这个方格无论往哪个方向走都给必然会到某个环上或环内。说明它是“不可用的”。

      • 一种也许更加方便的证明方法是：因为四周都是“不可用的”，所以没法 DFS 到该点，所以这个点也是“不可用的”。

由于每个“可用的”点最多仅会遍历一次，那么总时间复杂度就为 \mathcal{O}(n^2+q)。

const int N=1005,Q=2e5+5;
int n,q,mp[N][N],g[N][N],cnt;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
struct change {
    int x,y,t,ans;
    change()=default;
    change(int x,int y,int t):x(x),y(y),t(t) {}
} c[Q];

inline int check(int x,int y) {
    if(x<0||x>n+1||y<0||y>n+1) return 0;
    if(!x||!y||x>n||y>n) return -1;
    return 1;
}
void spread(int x,int y,int t) {
    if(!g[x][y]) cnt++;
    g[x][y]=1;
    for(int d=0;d<4;d++) {
        int px=x+dx[d],py=y+dy[d];
        if(!check(px,py)||g[px][py]) continue ;
        if(~mp[px][py]&&mp[px][py]!=d) continue ;
        spread(px,py,t);
    }
    return ;
}

int main() {
    n=read(),q=read();
    memset(mp,-1,sizeof(mp));
    for(int i=1;i<=q;i++) {
        c[i].x=read(),c[i].y=read();
        char dire[5];
        scanf("%s",dire+1);
        if(dire[1]=='L') c[i].t=0;
        if(dire[1]=='R') c[i].t=1;
        if(dire[1]=='U') c[i].t=2;
        if(dire[1]=='D') c[i].t=3;
        mp[c[i].x][c[i].y]=c[i].t;
    }
    spread(0,0,q);
    c[q].ans=(n+2)*(n+2)-cnt;
    for(int i=q;i>1;i--) {
        mp[c[i].x][c[i].y]=-1;
        if(!g[c[i].x][c[i].y]) {
            int flag=0;
            for(int d=0;d<4;d++) flag|=g[c[i].x+dx[d]][c[i].y+dy[d]];
            if(flag) spread(c[i].x,c[i].y,i);
        }
        c[i-1].ans=(n+2)*(n+2)-cnt;
    }
    for(int i=1;i<=q;i++) printf("%d\n",c[i].ans);
    return 0;
}