自动搬运

查看原文

来自洛谷，原作者为

	LinkCatTree 欢迎【蓝金勾】大佬壶关喵

搬运于2025-08-24 23:07:27，当前版本为作者最后更新于2024-12-24 07:50:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

我们发现判断哪些方格在环内是比较困难的，我们不妨判断哪些方格是“可用的”，这是比较简单的。具体来讲，我们可以从边界开始 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;
}