「棋盘游戏」题解

问题分析

我们有一个 $N \times M$ 的巨大棋盘（$N,M$ 可达 $10^9$），上面有 $P$ 个矩形障碍物（$P \leq 10^5$）。障碍物互不相交且不接触。所有非障碍物格子构成一个连通区域。

需要计算所有无序格子对 $(X,Y)$ 之间的最短路径长度之和。

关键点：

1. 棋盘极大，无法逐个格子计算
2. 障碍物以矩形形式给出，且互不相交
3. 路径是曼哈顿距离（因为只能上下左右移动，且无障碍物阻挡时最短路径就是曼哈顿距离）

核心观察

1. 曼哈顿距离的性质

在网格图中，两点 $(x_1,y_1)$ 和 $(x_2,y_2)$ 之间的曼哈顿距离为：

$$d = |x_1-x_2| + |y_1-y_2|$$

2. 无障碍物时的总距离和

如果没有障碍物，所有格子对的总曼哈顿距离和可以通过公式计算：

对于 $x$ 坐标的贡献：

• 对于每一对行 $i,j$，有 $M$ 列，贡献为 $M \times |i-j|$
• 总 $x$ 坐标贡献：$M^2 \times \sum_{i=1}^N \sum_{j=1}^N |i-j| = M^2 \times \frac{N(N^2-1)}{3}$

类似地，$y$ 坐标贡献：$N^2 \times \frac{M(M^2-1)}{3}$

总距离和：$M^2 \times \frac{N(N^2-1)}{3} + N^2 \times \frac{M(M^2-1)}{3}$

3. 有障碍物的情况

当有障碍物时，有些格子不可用。我们需要计算所有可用格子对的曼哈顿距离和。

设总可用格子数为 $K$。障碍物将棋盘分割成若干连通区域，但由于题目保证所有非障碍物格子连通，所以只有一个连通区域。

问题转化

我们需要计算：

$$\sum_{i<j} (|x_i-x_j| + |y_i-y_j|) = \sum_{i<j} |x_i-x_j| + \sum_{i<j} |y_i-y_j| $$

因此可以分开计算 $x$ 坐标贡献和 $y$ 坐标贡献。

计算 $\sum |x_i-x_j|$

设所有可用格子的 $x$ 坐标集合为 $X$（可能有重复，因为同一行可能有多个可用格子）。

如果我们将 $x$ 坐标排序：$x_1 \leq x_2 \leq \cdots \leq x_K$，那么：

$$\sum_{i<j} |x_i-x_j| = \sum_{i=1}^K (2i-K-1) \cdot x_i $$

这是因为对于每个 $x_i$，比它小的有 $i-1$ 个，比它大的有 $K-i$ 个，所以总贡献为 $[(i-1) - (K-i)] \cdot x_i = (2i-K-1) \cdot x_i$。

因此，我们只需要知道每一行有多少个可用格子，以及这些行的 $x$ 坐标。

矩形障碍物的影响

每个矩形障碍物 $(U,D,L,R)$ 覆盖了行 $[U,D]$，列 $[L,R]$ 的区域。由于障碍物互不相交，我们可以将棋盘按行和列分割。

算法框架

步骤1：计算总可用格子数 $K$

总格子数：$N \times M$ 障碍物覆盖的格子数：$\sum_{i=1}^P (D_i-U_i+1) \times (R_i-L_i+1)$ 但需要注意障碍物可能重叠？题目说互不相交，所以直接求和即可。

因此：$K = N \times M - \sum_{i=1}^P (D_i-U_i+1) \times (R_i-L_i+1)$

步骤2：计算 $x$ 坐标贡献

我们需要统计每一行的可用格子数。

关键观察：由于障碍物是矩形且互不相交，每一行的可用格子模式很简单。实际上，由于障碍物互不相交（行和列都不相交），每一行要么完全被某个障碍物覆盖一部分，要么完全空闲。

更精确地说：对于行 $r$，如果它被某个障碍物 $i$ 覆盖（即 $U_i \leq r \leq D_i$），那么这一行的 $[L_i, R_i]$ 列不可用，其他列可用。

由于障碍物在列方向上也不相交，对于行 $r$，所有覆盖该行的障碍物的列区间也不相交。

因此，对于行 $r$，可用格子数 = $M - \sum_{\text{覆盖行r的障碍物i}} (R_i-L_i+1)$

步骤3：高效计算

由于 $N$ 可达 $10^9$，我们不能遍历所有行。但 $P \leq 10^5$，障碍物将行分成若干段。

行分段： 障碍物的行区间将 $[1,N]$ 分成若干段：

• 类型1：完全不被任何障碍物覆盖的行段
• 类型2：被一个或多个障碍物覆盖的行段（但由于行不相交，同一行段最多被一个障碍物覆盖？）

实际上，由于障碍物的行区间不相交（$D_i+1 < U_j$ 或 $D_j+1 < U_i$），所以：

1. 障碍物的行区间是分离的，不重叠也不相邻
2. 因此，行被分成：空闲段 - 障碍段 - 空闲段 - 障碍段 - ...

所以我们可以按行段处理。

步骤4：按行段处理

设行段为 $[l,r]$，这个行段要么完全空闲（没有障碍物），要么完全被某个障碍物覆盖（该障碍物覆盖的行区间完全包含这个行段）。

情况1：完全空闲的行段 对于行 $i \in [l,r]$，可用格子数都是 $M$（整行都可用）。

情况2：被障碍物覆盖的行段 对于行 $i \in [l,r]$，可用格子数都是 $M - (R-L+1)$，其中 $(U,D,L,R)$ 是覆盖该行段的障碍物。

因此，在每个行段内，所有行的可用格子数相同！

步骤5：计算 $\sum |x_i-x_j|$

设第 $i$ 行的可用格子数为 $c_i$（注意 $i$ 是行号）。

我们需要计算：

$$\sum_{i=1}^N \sum_{j=1}^N c_i \cdot c_j \cdot |i-j| $$

这可以重写为：

$$\sum_{i=1}^N c_i \left( \sum_{j=1}^{i-1} c_j \cdot (i-j) + \sum_{j=i+1}^N c_j \cdot (j-i) \right) $$

我们可以使用前缀和优化：

令：

• $S_i = \sum_{j=1}^i c_j$（数量前缀和）
• $T_i = \sum_{j=1}^i c_j \cdot j$（加权前缀和）

则对于行 $i$：

• 左边贡献：$\sum_{j=1}^{i-1} c_j \cdot (i-j) = i \cdot S_{i-1} - T_{i-1}$
• 右边贡献：$\sum_{j=i+1}^N c_j \cdot (j-i) = (T_N - T_i) - i \cdot (S_N - S_i)$

总贡献：$c_i \times [i \cdot S_{i-1} - T_{i-1} + (T_N - T_i) - i \cdot (S_N - S_i)]$

但由于 $N$ 很大，我们不能直接遍历所有行。不过，由于行被分成段，每段内 $c_i$ 相同，我们可以批量计算。

步骤6：批量计算行段贡献

设有一个行段 $[l,r]$，其中每行的可用格子数为 $c$。

对于这个行段的所有行，我们需要计算它们与所有行的贡献。

更高效的方法是：计算这个行段内部的对，以及这个行段与外部行的对。

行段内部贡献： 行段 $[l,r]$ 有 $len = r-l+1$ 行，每行有 $c$ 个格子。 这 $len$ 行之间的 $x$ 坐标贡献为：

$$c^2 \times \sum_{i=l}^r \sum_{j=l}^r |i-j| = c^2 \times \frac{len(len^2-1)}{3} $$

行段与前面行段的贡献： 设前面所有行的加权和为 $T_{prev}$，数量为 $S_{prev}$。 那么行段 $[l,r]$ 与前面行的贡献为：

$$c \times \sum_{i=l}^r [i \cdot S_{prev} - T_{prev}] = c \times [S_{prev} \cdot \frac{(l+r)len}{2} - T_{prev} \cdot len] $$

行段与后面行段的贡献： 类似，但需要知道后面的信息。我们可以先计算所有行的总 $S_N$ 和 $T_N$，然后减去前面的。

步骤7：计算 $y$ 坐标贡献

类似地，我们需要计算 $\sum |y_i-y_j|$。

对于列的处理与行类似，但由于每个矩形障碍物覆盖连续的列区间，列也被分成段。

关键：对于每个行段，该段内所有行的可用列模式相同，但不同行段的可用列模式可能不同。

因此，计算 $y$ 坐标贡献更复杂：需要知道每个格子具体的 $y$ 坐标。

更简单的方法

实际上，由于障碍物互不相交，棋盘被分割成若干矩形区域（空闲区域）。但题目保证所有非障碍物格子连通，所以这些空闲区域实际上是通过边界连通的。

观察：曼哈顿距离的可加性

总曼哈顿距离和 = 所有格子对的 $x$ 坐标差之和 + 所有格子对的 $y$ 坐标差之和。

而 $x$ 坐标差之和只依赖于每行的格子数，$y$ 坐标差之和只依赖于每列的格子数。

因此，我们可以：

1. 统计每行的可用格子数
2. 统计每列的可用格子数
3. 分别计算 $x$ 和 $y$ 的贡献

统计每行的可用格子数

如上所述，行被障碍物分成段。对于每个行段 $[l,r]$：

• 如果是不被障碍物覆盖的段：每行有 $M$ 个可用格子
• 如果被障碍物 $i$ 覆盖：每行有 $M - (R_i-L_i+1)$ 个可用格子

统计每列的可用格子数

类似地，列也被障碍物分成段。对于每个列段 $[l,r]$：

• 如果是不被障碍物覆盖的段：每列有 $N$ 个可用格子
• 如果被障碍物 $i$ 覆盖：每列有 $N - (D_i-U_i+1)$ 个可用格子

高效计算行列统计

由于 $P \leq 10^5$，行列都被分成 $O(P)$ 段。

我们可以：

1. 收集所有障碍物的行区间边界
2. 将行分成 $O(P)$ 段
3. 对每个行段，确定其类型（空闲或被哪个障碍物覆盖）
4. 批量计算贡献

类似地处理列。

算法步骤

步骤1：处理行

1. 收集所有关键行：$1$, $N+1$（结束），以及每个障碍物的 $U_i$ 和 $D_i+1$
2. 排序去重，得到行分段点
3. 对于每个行段 $[l,r)$（注意是左闭右开）：
   • 确定这个行段是否被某个障碍物覆盖
   • 计算该段的格子数：$c = (r-l) \times$（每行可用格子数）
   • 记录该段的加权信息用于后续计算

步骤2：计算 $x$ 坐标贡献

使用之前的前缀和方法，但批量处理行段：

设行段按顺序为 $seg_1, seg_2, ..., seg_m$ 每个段 $seg_k$ 有：

• 行范围 $[l_k, r_k)$，长度 $len_k = r_k - l_k$
• 每行可用格子数 $c_k$

我们需要计算：

$$X_{total} = \sum_{k=1}^m \left( \text{段内贡献}_k + \sum_{j<k} \text{段间贡献}_{j,k} \right) $$

段内贡献：

$$c_k^2 \times \frac{len_k(len_k^2-1)}{3}$$

段间贡献（段 $j$ 和段 $k$，$j<k$）： 段 $j$ 的每行有 $c_j$ 个格子，段 $k$ 的每行有 $c_k$ 个格子。 设段 $j$ 的行号为 $a_1,...,a_{len_j}$，段 $k$ 的行号为 $b_1,...,b_{len_k}$。 贡献为：

$$c_j c_k \times \sum_{p=1}^{len_j} \sum_{q=1}^{len_k} (b_q - a_p) \quad (\text{因为 } b_q > a_p) $$$$= c_j c_k \times \left( len_j \cdot \sum_{q=1}^{len_k} b_q - len_k \cdot \sum_{p=1}^{len_j} a_p \right) $$$$= c_j c_k \times \left( len_j \cdot len_k \cdot \frac{l_k + r_k - 1}{2} - len_k \cdot len_j \cdot \frac{l_j + r_j - 1}{2} \right) $$$$= c_j c_k \cdot len_j \cdot len_k \cdot \frac{(l_k + r_k - 1) - (l_j + r_j - 1)}{2} $$$$= c_j c_k \cdot len_j \cdot len_k \cdot \frac{(l_k + r_k) - (l_j + r_j)}{2} $$

这可以高效计算。

步骤3：计算 $y$ 坐标贡献

完全类似，处理列段。

步骤4：总答案

总答案 = $X_{total} + Y_{total}$，取模 $10^9+7$。

复杂度分析

• 处理行段：$O(P \log P)$ 排序
• 处理列段：$O(P \log P)$ 排序
• 计算贡献：$O(P^2)$ 如果直接枚举段对，但 $P \leq 10^5$，$O(P^2)$ 不可行

优化段间贡献计算

注意到段间贡献公式： 对于行段 $j$ 和 $k$（$j<k$），贡献为：

$$c_j c_k \cdot len_j \cdot len_k \cdot \frac{(l_k + r_k) - (l_j + r_j)}{2} $$

这可以重写为：

$$\frac{1}{2} \cdot \left[ (l_k + r_k) \cdot (c_k \cdot len_k) \cdot \sum_{j<k} (c_j \cdot len_j) - \sum_{j<k} (l_j + r_j) \cdot (c_j \cdot len_j) \cdot (c_k \cdot len_k) \right] $$

因此，我们可以维护前缀和：

• $A = \sum_{j<k} (c_j \cdot len_j)$
• $B = \sum_{j<k} (l_j + r_j) \cdot (c_j \cdot len_j)$

对于每个段 $k$，贡献为：

$$\frac{1}{2} \cdot (c_k \cdot len_k) \cdot \left[ (l_k + r_k) \cdot A - B \right] $$

这样可以在 $O(m)$ 时间内计算所有段间贡献，其中 $m = O(P)$。

最终算法

1. 计算行段：

   • 收集关键点：$1$, $N+1$, 所有 $U_i$, $D_i+1$
   • 排序得到分段点 $p_1 < p_2 < ... < p_t$
   • 对于每个段 $[p_i, p_{i+1})$，确定其类型（是否被障碍物覆盖）

2. 计算 $x$ 坐标贡献：

   • 对于每个行段，计算 $len_i$, $c_i$, $mid_i = \frac{l_i + r_i}{2}$
   • 计算段内贡献
   • 使用前缀和计算段间贡献

3. 计算列段：类似处理

4. 总答案：$X_{total} + Y_{total} \mod 10^9+7$

注意事项

1. 模运算：所有计算在模 $10^9+7$ 下进行
2. 除法：需要计算模逆元
3. 大数：$N,M$ 可达 $10^9$，注意乘法溢出
4. 坐标处理：行号和列号从1开始

总结

本题的核心是将曼哈顿距离和分解为 $x$ 和 $y$ 坐标贡献，然后利用障碍物的矩形且互不相交的性质，将行列分成段，批量计算贡献。通过前缀和优化，将复杂度从 $O(P^2)$ 降为 $O(P \log P)$，适合 $P \leq 10^5$ 的数据范围。