题意
给定 $n$ 个点 $\left(x_i, y_i\right)$，求曼哈顿距离下前 $k$ 小的点对。输出他们的距离。
$2 \leq n \leq 2.5 \times 10^5$，时限 $9$ 秒。
题解
做法 1
暴力的做法是维护一个堆，枚举点 $u$，再枚举 $v$，然后计算 $u$ 到 $v$ 的距离，插入到堆中，并且始终保持堆的大小在 $k$ 以内。
考虑用 K-D Tree 优化这个过程。如果堆的大小已经达到 $k$，并且 $u$ 到 $v$ 的距离大于堆中的最大元素，那么 $\left(u,v\right)$ 就必然不会是答案。
2-D Tree 上一个结点代表某个矩形以及这个矩形中按某一维排序的中位点。考虑将枚举 $v$ 的过程改成在 2-D Tree 上 DFS。如果我们发现当前 DFS 到的矩形的四个角与 $u$ 的距离的最小值大于堆中的最大元素（且堆的大小为 $k$）那么我们就可以直接回溯了。
算法复杂度未知。
能过，而且跑得飞快，甚至拿到了次优解。（2022/07/23）
代码
// Please submit with C++14!
#include <algorithm>
#include <array>
#include <cmath>
#include <cstdint>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <unordered_map>
#include <utility>
#include <vector>
#define ra _Read()
using tp = long long;
tp _Read() {
bool __neg = 0;
char __c = getchar();
tp __val = 0;
for (; __c < 48 || __c > 57; __c = getchar()) {
__neg = __c == 45;
}
for (; __c > 47 && __c < 58; __c = getchar()) {
__val = __val * 10 + (__c & 15);
}
return __neg ? ~__val + 1 : __val;
}
using namespace std;
constexpr tp Hat_N = 2.5e5 + 3;
struct Loc {
tp x, y;
};
tp k, root;
array<Loc, Hat_N> p;
array<tp, Hat_N> ls, rs, lx, rx, ly, ry;
bool Lcomp_x(const Loc& x, const Loc& y) {
if (x.x != y.x) {
return x.x < y.x;
}
return x.y < y.y;
}
bool Lcomp_y(const Loc& x, const Loc& y) {
if (x.y != y.y) {
return x.y < y.y;
}
return x.x < y.x;
}
void maintain(tp x, tp y) {
lx[x] = min(lx[x], lx[y]);
rx[x] = max(rx[x], rx[y]);
ly[x] = min(ly[x], ly[y]);
ry[x] = max(ry[x], ry[y]);
}
tp build(tp l, tp r, bool xy = 1) {
if (l > r) {
return 0;
} else {
tp c = l + r >> 1;
nth_element(&p[l], &p[c], &p[r + 1], xy ? Lcomp_x : Lcomp_y);
lx[c] = rx[c] = p[c].x;
ly[c] = ry[c] = p[c].y;
if (ls[c] = build(l, c - 1, !xy)) {
maintain(c, ls[c]);
}
if (rs[c] = build(c + 1, r, !xy)) {
maintain(c, rs[c]);
}
return c;
}
}
tp dist(tp x, tp y) {
tp dx, dy;
dx = p[x].x < lx[y] ? lx[y] - p[x].x : p[x].x > rx[y] ? p[x].x - rx[y] : 0;
dy = p[x].y < ly[y] ? ly[y] - p[x].y : p[x].y > ry[y] ? p[x].y - ry[y] : 0;
return dx + dy;
}
struct K_heap {
priority_queue<tp> mink;
void push(tp x, tp y) {
tp dist = abs(p[x].x - p[y].x) + abs(p[x].y - p[y].y);
if (mink.size() == k) {
if (mink.top() > dist) {
mink.pop();
mink.push(dist);
}
} else {
mink.push(dist);
}
}
bool abandon(tp d) { return mink.size() == k && mink.top() <= d; }
void print() {
list<tp> r;
while (mink.size()) {
r.push_front(mink.top());
mink.pop();
}
for (auto&& i : r) {
printf("%lld\n", i);
}
}
} khp;
void calc(tp x, tp y) {
if (y && !khp.abandon(dist(x, y))) {
if (x < y) {
khp.push(x, y);
}
calc(x, ls[y]);
calc(x, rs[y]);
}
}
void dfs(tp x) {
if (x) {
calc(x, root);
dfs(ls[x]);
dfs(rs[x]);
}
}
signed main() {
tp n = ra;
k = ra;
for (tp i = 1; i <= n; ++i) {
p[i].x = ra;
p[i].y = ra;
}
dfs(root = build(1, n));
khp.print();
return EXIT_SUCCESS;
}
/*#################################################################
#.................................................................#
#............................This.Code.Was.Created.By.RBTree......#
#.............#......#...............Limiting-Factor..............#
#............#.#....#.#.................Soul-Code.................#
#.............########............................................#
#............#........#..##############################...........#
#...........#..V....V......#..#........................#..#...#...#
#............#........#....#..........###..###..........#..#.#.#..#
#............#..X##X..#..#............#....#.#...........#..#...#.#
#...........#...N##N...#..#...........###..###..........#.........#
#.......MOE..#..@.....#....#.#.#.#...................#.#..........#
#.............########.....#.#.#.##############.#.#..#.#..........#
#..........................#.#.#.#.............#.#.#.#.#..........#
#......#########...........#.#.#.#.................#.#.#..........#
#.....#.........#..........#.#.#.#.................#.#.#..........#
#.#.#.#G#R#A#S#S#.#.#......#.#.#.#.................#.#.#..........#
#.###################......#.#.#.#.................#.#.#..........#
#...........................#.#.#...................#.#...........#
#.................................................................#
#################################################################*/做法 2
把曼哈顿距离转成切比雪夫距离，然后二分。问题可以转化为求方形内的点数，可以二维数点。
复杂度 $\mathcal O\left(n \log^2 n\right)$
代码
口糊的，没有代码。