G. 好机器人路径 题解

---

一、题意理解

平面上有 $n$ 个黑色整数坐标点，其余点为白色。机器人每次可向上/下/左/右移动一格。

对于一对黑色点 $(A, B)$，若从 $A$ 到 $B$ 的所有最短路径上的每个整数点都是黑色，则称该点对是"好的"。

求"好的"点对总数（$(A, B)$ 和 $(B, A)$ 视为不同）。

---

二、核心定理

定理：在网格上，$A = (x_a, y_a)$ 与 $B = (x_b, y_b)$ 之间的所有最短路径的并集，恰好是以 $A$ 和 $B$ 为对顶点的矩形（包含边界）内的所有整数点。

证明：

曼哈顿距离为：

$$d = |x_a - x_b| + |y_a - y_b|$$

对矩形内任意点 $P = (x, y)$，其中 $x$ 介于 $x_a$ 与 $x_b$ 之间，$y$ 介于 $y_a$ 与 $y_b$ 之间：

$$\begin{aligned} |P - A| + |B - P| &= (|x - x_a| + |y - y_a|) + (|x_b - x| + |y_b - y|) \\[4pt] &= |x_a - x_b| + |y_a - y_b| = d \end{aligned} $$

因此 $P$ 在某条最短路径上。反之，任何最短路径上的点不可能超出该矩形。$\square$

---

三、问题转化

由上述定理，$(A, B)$ 是"好的"当且仅当以 $A$ 和 $B$ 为对顶点的矩形内所有整数点都是黑色。

这意味着我们需要统计"全黑矩形"的数量，并根据矩形的形状赋予不同权重。

---

3.1 矩形分类

第一类：$1 \times k$ 或 $k \times 1$ 的线段状矩形（$k > 1$）

• 这类矩形退化为水平或竖直的连续黑色线段。
• 每条线段只有 $2$ 个端点可作为路径的起点和终点。
• 贡献：设此类矩形数量为 $R_1$，每个贡献 $2$，总计 $2 \cdot R_1$。

第二类：$k \times l$ 的"真正"矩形（$k, l > 1$）

• 矩形的 $4$ 个角点都可作为路径的起点和终点。
• 贡献：设此类矩形数量为 $R_2$，每个贡献 $4$，总计 $4 \cdot R_2$。

---

四、第一类矩形的计数

在每行和每列上统计连续的黑色点段。

• 对水平方向：将所有点按 $(y, x)$ 排序，对每个 $y$ 收集对应的 $x$，排序后统计连续段。对于长度为 $len$ 的连续段，包含的第一类矩形数为 $\frac{len \cdot (len - 1)}{2}$，每个贡献 $2$。
• 对竖直方向：同理，按 $(x, y)$ 排序统计连续段。

可用有序集合 set 或排序实现，复杂度 $O(n \log n)$。

---

五、第二类矩形的计数

5.1 扫描线 + 高度直方图

采用沿 $y$ 轴从上往下扫描的方法：

1. 将所有点按 $y$ 坐标分组（TreeMap），对同一 $y$ 的 $x$ 排序。

2. 维护字典 $H[x]$：以当前 $y$ 为底，$x$ 列向上连续的黑色点数（高度）。

3. 当 $y$ 不是上一行 $y-1$ 的相邻整数时，清空 $H$（因为不连续）。

4. 对当前 $y$ 的每一列，计算新的高度：

   $$H[x] = H_{\text{prev}}[x] + 1$$

   若该列在上一次扫描中不存在（即 $y+1$ 行没有该 $x$ 的黑色点），则 $H[x] = 1$。

5.2 单调栈维护矩形计数

对于当前 $y$ 上的一个连续 $x$ 段（即 $x$ 连续相邻的列），设其高度数组为 $h_1, h_2, \dots, h_m$。

目标是统计所有以当前 $y$ 为底边的子矩形数量。

使用单调栈维护（高度，计数）对，保持高度非降：

• sum：栈中所有列代表的矩形组合数。
• 当加入新列 $h_i$ 时：
  • 先更新答案：res += (sum1 - sum2 - h_i + 1) * 4（第二类贡献）和 res += (sum2 - 1) * 2（半退化贡献）以及 res += (h_i - 1) * 2（列内纵向贡献）。
  • 弹出栈中比 $h_i$ 高的元素，合并计数。
  • 将 $(h_i, count)$ 压入栈，更新 sum。

关键细节：

• 若相邻两列的 $x$ 不连续（差值 $> 1$），则清空栈。
• $sum1$ = 矩形的上边界组合总数（考虑不同高度），$sum2$ = 当前区间列数。

5.3 贡献计算解释

对于当前行为底、高度 $\geq 2$ 的矩形：

• 横向至少 $2$ 列的矩形有四角选择权：$\times 4$。
• 横向只有 $1$ 列但纵向 $\geq 2$ 的矩形退化为第一类（已被竖直方向计数），但在此处仍需补充：$(h_i - 1) \times 2$。
• 不同高度组合的矩形通过单调栈的 sum1 - sum2 统计。

---

六、标程解析

private fun solveTest() {
    val n = readInt()
    val p = TreeMap<Int, MutableList<Int>>()
    repeat(n) {
        val x = readInt()
        val y = readInt()
        if (!p.containsKey(y)) p[y] = mutableListOf()
        p[y]!!.add(x)
    }
    var lastY = Int.MIN_VALUE
    var lastD = mutableMapOf<Int, Int>()  // 上一行的高度字典
    var res = 0L
    for (y in p.keys) {
        if (y != lastY + 1) lastD.clear()  // 不连续则重置
        var d = mutableMapOf<Int, Int>()   // 当前行的高度字典
        val xx = p[y]!!
        xx.sort()
        var lastX = Int.MIN_VALUE
        val st = mutableListOf<Pair<Int, Int>>()  // 单调栈
        var sum1 = 0L
        var sum2 = 0L
        for (x in xx) {
            val dd = lastD.getOrDefault(x, 0) + 1
            d[x] = dd
            if (x != lastX + 1) {  // x 不连续，重置栈
                st.clear()
                sum1 = 0
                sum2 = 0
            }
            var c = 1
            while (st.isNotEmpty() && st.last().first > dd) {
                c += st.last().second
                sum1 -= st.last().first * st.last().second
                st.removeLast()
            }
            sum1 += c * dd
            st.add(dd to c)
            sum2++
            // 累加答案
            res += (sum1 - sum2 - dd + 1) * 4
            res += (sum2 - 1) * 2
            res += (dd - 1) * 2
            lastX = x
        }
        lastY = y
        lastD = d
    }
    println(res)
}

---

七、复杂度分析

• 每个点参与一次排序，总复杂度 $O(n \log n)$。
• 单调栈部分均摊 $O(n)$。
• 空间复杂度 $O(n)$。
• 所有测试用例 $\sum n \leq 5 \times 10^5$，算法可行。

---

八、代码实现（C++）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve() {
    int n;
    cin >> n;
    map<int, vector<int>> pts;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        pts[y].push_back(x);
    }
    
    ll res = 0;
    int lastY = INT_MIN;
    map<int, int> lastH;  // 上一行的高度
    
    for (auto& [y, xs] : pts) {
        if (y != lastY + 1) lastH.clear();
        
        sort(xs.begin(), xs.end());
        map<int, int> curH;  // 当前行的高度
        
        int lastX = INT_MIN;
        vector<pair<int, int>> st;  // (height, count)
        ll sum1 = 0, sum2 = 0;
        
        for (int x : xs) {
            int h = (lastH.count(x) ? lastH[x] : 0) + 1;
            curH[x] = h;
            
            if (x != lastX + 1) {
                st.clear();
                sum1 = sum2 = 0;
            }
            
            int cnt = 1;
            while (!st.empty() && st.back().first > h) {
                cnt += st.back().second;
                sum1 -= 1LL * st.back().first * st.back().second;
                st.pop_back();
            }
            sum1 += 1LL * cnt * h;
            st.push_back({h, cnt});
            sum2++;
            
            res += (sum1 - sum2 - h + 1) * 4;
            res += (sum2 - 1) * 2;
            res += (h - 1) * 2;
            
            lastX = x;
        }
        
        lastY = y;
        lastH = curH;
    }
    
    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}