题目概述

本题需要找出平面上 $N$ 个点之间曼哈顿距离最小的前 $K$ 条边。由于 $N$ 可达 $250,000$，直接计算所有 $O(N^2)$ 对距离是不可行的。

核心思路

1. 曼哈顿距离转切比雪夫距离

通过坐标变换：

p[i].x = x + y, p[i].y = y - x;

将曼哈顿距离 $|x_1-x_2| + |y_1-y_2|$ 转换为切比雪夫距离 $\max(|x_1'-x_2'|, |y_1'-y_2'|)$，其中：

• $x' = x + y$
• $y' = y - x$

2. 二分答案 + 扫描线计数

二分框架：

i64 l = 0, r = 5e9;
while (l < r) {
    i64 m = l + r >> 1;
    if (calcul_count(m) < K) {
        l = m + 1;
    } else {
        r = m;
    }
}

二分寻找第 $K$ 小的距离值 $d$。

3. 距离计数函数 calcul_count

关键步骤：

1. 预处理纵坐标范围：

   void init_range(i64 d) {
       // 计算每个点在纵坐标方向上的有效范围 [yl[i], yr[i]]
   }
   

2. 扫描线计数：

   • 按变换后的 $x$ 坐标排序
   • 维护滑动窗口，保证窗口内点的 $x$ 坐标差不超过 $d$
   • 使用树状数组统计纵坐标在有效范围内的点对数量

算法详解

坐标变换的意义

原始曼哈顿距离：

变换后坐标 $(x+y, y-x)$ 下的切比雪夫距离：

由于 $|Δx+Δy|$ 和 $|Δy-Δx|$ 至少有一个等于 $|Δx|+|Δy|$，因此：

距离计数优化

对于固定的距离 $d$，点 $i$ 和 $j$ 满足距离 $\leq d$ 的条件是：

• $|x_i' - x_j'| \leq d$
• $|y_i' - y_j'| \leq d$

这转化为二维矩形区域查询问题，可以用扫描线 + 树状数组高效解决。

复杂度分析

• 坐标变换：$O(N)$
• 排序：$O(N \log N)$
• 二分答案：$O(\log (5\times 10^9)) \approx 32$ 次
• 每次计数：$O(N \log N)$
• 总复杂度：$O(N \log N \log \text{MAX})$，可接受

关键优化技巧

1. 坐标离散化：将纵坐标映射到 $[1, Y]$ 的整数范围
2. 滑动窗口：利用 $x$ 坐标的单调性
3. 平衡树查询：使用 set 高效查询纵坐标范围内的点
4. 提前终止：计数达到 $K$ 时立即返回

总结

该解法通过坐标变换将曼哈顿距离问题转化为更易处理的切比雪夫距离问题，结合二分答案和扫描线技术，在 $O(N \log N \log \text{MAX})$ 的时间内高效解决了大规模Top-K曼哈顿距离查询问题。