题意回顾

• $N \times M$ 网格，从 $(1,1)$ 出发，只能向南或向东走到 $(N,M)$
• 某些格子有家具（$C_{i,j}=1$），不能经过
• 初始时存在至少一条可行路径
• $Q$ 次操作，每次尝试在 $(X_k,Y_k)$ 放新家具
• 如果放完后仍然存在可行路径，则放置并输出 1，否则输出 0

关键观察

在 $(x,y)$ 放家具会阻断路径，当且仅当 $(x,y)$ 位于所有可行路径上。

换句话说：

• 如果存在另一条不经过 $(x,y)$ 的路径，那么可以放置
• 如果所有路径都必须经过 $(x,y)$，那么不能放置

核心思路

我们需要判断一个格子 $(x,y)$ 是否是必经点。

方法：

1. 计算 from_start[i][j]：从 $(1,1)$ 到 $(i,j)$ 是否可达
2. 计算 to_end[i][j]：从 $(i,j)$ 到 $(N,M)$ 是否可达
3. 对于格子 $(x,y)$，如果 from_start[x][y] && to_end[x][y]，说明它在某条可行路径上
4. 但要判断是否是所有路径的必经点，需要更精细的方法

必经点判断技巧

定理：在只能向右/下走的网格中，$(x,y)$ 是所有路径的必经点，当且仅当：

• 从 $(1,1)$ 到 $(x,y)$ 的路径数 × 从 $(x,y)$ 到 $(N,M)$ 的路径数 = 从 $(1,1)$ 到 $(N,M)$ 的总路径数

但由于路径数可能很大，我们改用动态规划时记录两种不同的走法：

定义：

• dp1[i][j] = 从 $(1,1)$ 到 $(i,j)$ 是否可达（正常DP）
• dp2[i][j] = 从 $(i,j)$ 到 $(N,M)$ 是否可达（反向DP）

如果 dp1[x][y] && dp2[x][y]，说明 $(x,y)$ 在某条路径上。

但要判断是否是所有路径的必经点，一个经典方法是：

• 先从 $(1,1)$ 正常 DP 一次
• 改变行走顺序（比如先尽量向右再向下 vs 先尽量向下再向右）
• 如果两种不同的走法都经过 $(x,y)$，那么 $(x,y)$ 就是必经点

标准解法

实际比赛中常用的方法是：

1. 第一次DP：从 $(1,1)$ 出发，优先向右走（在多个选择时）
2. 第二次DP：从 $(1,1)$ 出发，优先向下走
3. 第三次DP：从 $(N,M)$ 反向，优先向左走
4. 第四次DP：从 $(N,M)$ 反向，优先向上走

如果某个格子 $(x,y)$ 在第一次和第三次DP中都可达，并且在第二次和第四次DP中都可达，那么它就是所有路径的必经点。

算法步骤

1. 预处理四种DP：

   • f1[i][j]: 从起点优先向右走是否可达
   • f2[i][j]: 从起点优先向下走是否可达
   • g1[i][j]: 从终点优先向左走是否可达
   • g2[i][j]: 从终点优先向上走是否可达

2. 对于查询 $(x,y)$：

   • 如果 (f1[x][y] && g1[x][y]) && (f2[x][y] && g2[x][y])，说明 $(x,y)$ 是所有路径必经点，输出 0
   • 否则输出 1

复杂度分析

• 预处理：$O(NM)$
• 每次查询：$O(1)$
• 总复杂度：$O(NM + Q)$，可以通过