送外卖

https://www.matiji.net/exam/dohomework/8695/5

题干

小码哥正在学校里送外卖。学校由一个 $n \times n$ 的网格构成，里面包含 $n$ 栋教学楼，第 $i$ 栋位于 $(x_i, y_i)$ 的位置。在每分钟，小码哥可以从当前他在的位置移动到 8 个相邻的格子中的任意一个中，无论这个格子是教学楼还是空地。

从第 $i$ 栋教学楼移动至第 $j$ 栋教学楼时，小码哥总是沿着最短路径移动。

现在请你帮助他找到在两两教学楼之间的最短路径中的第 $k$ 短是多少。

第一行包含两个整数 $n (2 \leq n \leq 10^5), k (1 \leq k \leq \frac{n(n-1)}{2})$。

随后 $n$ 行，每行包含两个整数 $x_i, y_i (1 \leq x_i, y_i \leq 10^5)$，表示一栋教学楼的位置。

需要注意的是，教学楼可能重叠，两栋重叠的教学楼之间的距离为 0 。

输出仅包含一个整数，表示两两教学楼之间第 $k$ 短路的距离。

思路

复杂度显然是要我们做分治，而分治的测试变量应当是第 $k$ 大的距离。我们就是要二分答案然后做测试，直到找到结果位置。

做测试的复杂度要在 $O(n)$ 左右。测试即是计算有多少个点对小于测试据距离。

做一下小结：我们确定了要使用二分搜寻法，且测试距离已经给出。现在要给定任意测试距离，在 $O(n)$ 左右求出小与测试距离的点对个数。

这个计数算法类似于之前对 09 社团活动。给定一个条件，利用线段树找另一个条件满足的元素个数。可以用 multiset ，但是会超时…… 可以换 Fenwick 树或线段树。

因为距离函数是，

$$\max(|x_1 - x_2|, |y_1 - y_2|)$$

要在平面上寻找满足距离小于给定测试值的点对数目，要保证，

$$|x_1 - x_2| \leq d \land |y_1 - y_2| \leq d$$

对于任何一个点，满足要求的点首先要在 $x_i - d$ 到 $x_i + d$ 之间。然后要在这个区间内找到 $y_j$ 满足 $|y_j - y_i| \leq d$。

动态有重叠的区间应该想滑窗，首先要按 $x$ 排序，然后维护窗口内点的 $y$ 值。之后逐个滑窗即可。计数注意要 -n （去掉自己和自己），/2 （去重）。

代码

#include <vector>
#include <iostream>
#include <algorithm>

typedef long long ll;

using namespace std;

struct Fenwick {
    int n;
    vector<int> tree;
    Fenwick(int n) : n(n), tree(n + 1, 0) {}
#define LB(x) ((x)&(-x))
    void update(int idx, int delta) {
        ++idx;
        for(; idx <= n; idx += LB(idx)) {
            tree[idx] += delta;
        }
    }

    int query(int idx) {
        ++idx;
        int sum = 0;
        for(; idx > 0; idx -= LB(idx)) {
            sum += tree[idx];
        }
        return sum;
    }

#undef LB
};

struct Point {
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y) {}
    bool operator<(const Point& other) const {
        return x < other.x || (x == other.x && y < other.y);
    }
};

int main() {
    int n;
    ll k;
    cin >> n >> k;
    vector<Point> points(n);
    for (int i = 0; i < n; ++i) {
        cin >> points[i].x >> points[i].y;
    }
    sort(points.begin(), points.end());

    // Collect all y coordinates for discretization
    vector<int> all_ys;
    for (const Point& p : points) {
        all_ys.push_back(p.y);
    }
    sort(all_ys.begin(), all_ys.end());
    all_ys.erase(unique(all_ys.begin(), all_ys.end()), all_ys.end());
    int m = all_ys.size();

    vector<int> y_indices(n);
    for (int i = 0; i < n; ++i) {
        y_indices[i] = lower_bound(all_ys.begin(), all_ys.end(), points[i].y) - all_ys.begin();
    }

    // Compute initial max_d
    int min_x = points[0].x, max_x = points[0].x;
    int min_y = points[0].y, max_y = points[0].y;
    for (const Point& p : points) {
        min_x = min(min_x, p.x);
        max_x = max(max_x, p.x);
        min_y = min(min_y, p.y);
        max_y = max(max_y, p.y);
    }
    ll max_d = max(max_x - min_x, max_y - min_y);

    ll left = 0;
    ll right = max_d;
    ll answer = right;

    while (left <= right) {
        ll mid = (left + right) / 2;
        Fenwick fenwick(m);
        ll count = 0;
        int l = 0;
        int r = 0;

        for (int i = 0; i < n; ++i) {
            const int x_i = points[i].x;
            const int y_i = points[i].y;

            // Expand r to include points with x <= x_i + mid
            while (r < n && points[r].x <= x_i + mid) {
                fenwick.update(y_indices[r], 1);
                ++r;
            }

            // Move l to exclude points with x < x_i - mid
            while (l < i && points[l].x < x_i - mid) {
                fenwick.update(y_indices[l], -1);
                ++l;
            }

            // Calculate y range [y_i - mid, y_i + mid]
            int y_low = y_i - mid;
            int y_high = y_i + mid;

            auto left_it = lower_bound(all_ys.begin(), all_ys.end(), y_low);
            auto right_it = upper_bound(all_ys.begin(), all_ys.end(), y_high);

            int left_idx = left_it - all_ys.begin();
            int right_idx = right_it - all_ys.begin() - 1;

            if (left_idx > right_idx) {
                continue;
            }

            int current = fenwick.query(right_idx);
            if (left_idx > 0) {
                current -= fenwick.query(left_idx - 1);
            }
            count += current;
        }

        ll total_pairs = (count - n) / 2;

        if (total_pairs >= k) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << answer << endl;

    return 0;
}