【题解】P9062

· · 题解

考虑套用平面最近点对的网格化做法。在平面最近点对中，每次选取当前答案 d 作为边长，将平面划分为每一格大小为 d \times d 的网格，然后每个网格中只会有 O(1) 个点，只需要枚举相邻（至少有一个公共点）的两个网格计算贡献即可。

考虑拓展上述做法，实际上只需要关心 d 的选取。注意到在之前的算法中选取 d 的常数倍并不会造成影响，因此考虑取若干个 d，能够覆盖到所有可能存在的 d 的常数倍。显然 2^0, 2^1, \dots, 2^{\lceil \log \max\{x_i, y_i\}\rceil} 满足要求。

于是枚举 k = 0 \sim \lceil \log \max\{x_i, y_i\}\rceil，将平面划分为大小为 2^k \times 2^k 的网格，在此基础上开始考虑贡献。

对于每一块，只需要按编号排序，然后取相邻的计算贡献即可覆盖全部。对于相邻的两块，将两块的点同时按编号排序，可以发现有贡献的点对在排序后的序列上距离 O(1)，因此只需要枚举相邻的 O(1) 个点对计算贡献即可覆盖全部。

此时问题转化为 O(n \log \max\{x_i, y_i\}) 次单点修改，q 次矩形查询，直接套用扫描线 + 分块的 O(n \log \max\{x_i, y_i\} + q \sqrt n) 做法即可。这里采用分块是因为修改次数过多，直接使用 O((n \log \max\{x_i, y_i\} + q)\log n) 的做法在实际运行中速度更慢。

实现时取相邻的 O(1) 大概需要取 10 个，但是常数过大。可以在初始对所有的点整体随机平移一次/随机扰动每一格的边长以改变网格图的划分，然后只需要取 3 个点左右就足以覆盖所有有贡献的点对。

代码：

#include <bits/stdc++.h>
int read (void)
{
    int x = 0; char ch = getchar();
    while (ch < '0' or ch > '9') ch = getchar();
    while (ch >= '0' and ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    return x;
}
const int maxn = 1 << 18;
int n, q, S, bl[maxn], x[maxn], y[maxn], p[maxn]; std::vector<int> A[maxn];
long long t1[maxn], t2[maxn], ans[maxn]; std::vector<std::pair<int, int>> Q[maxn];
std::unordered_map<long long, std::pair<int, int>> pos;
long long id (int x, int y) {return x * (1LL << 30) + y;}
long long dis (int u, int v) {return 1LL * (x[u] - x[v]) * (x[u] - x[v]) + 1LL * (y[u] - y[v]) * (y[u] - y[v]);}
void add (int x, long long y) {t1[x] = std::min(t1[x], y); t2[bl[x]] = std::min(t2[bl[x]], y);}
long long ask (int x)
{
    long long w = 1LL << 60;
    for (int i = x; bl[i] == bl[x]; i++) w = std::min(w, t1[i]);
    for (int i = bl[x] + 1; i <= bl[n]; i++) w = std::min(w, t2[i]);
    return w;
}
signed main ()
{
    n = read(); q = read(); S = sqrt(n);
    for (int i = 1; i <= n; i++) x[i] = read(), y[i] = read(), bl[i] = (i - 1) / S + 1;
    for (int i = 1, l, r; i <= q; i++) l = read(), r = read(), Q[r].push_back({l, i}), ans[i] = 1LL << 60;
    for (int k = 0; k <= 27; k++)
    {
        std::iota(p + 1, p + n + 1, 1);
        std::sort(p + 1, p + n + 1, [&] (const int &a, const int &b) {return (x[a] >> k) == (x[b] >> k) ? (y[a] >> k) < (y[b] >> k) : (x[a] >> k) < (x[b] >> k);});
        for (int l = 1, r; l <= n; l = r + 1)
        {
            for (r = l; r < n and (x[p[r + 1]] >> k) == (x[p[l]] >> k) and (y[p[r + 1]] >> k) == (y[p[l]] >> k); r++) ;
            std::sort(p + l, p + r + 1); pos[id(x[p[l]] >> k, y[p[l]] >> k)] = {l, r};
            for (int i = l; i <= r; i++) for (int j = i + 1; j <= i + 3 and j <= r; j++) A[p[j]].push_back(p[i]);
        }
        for (int l = 1, r; l <= n; l = r + 1)
        {
            for (r = l; r < n and (x[p[r + 1]] >> k) == (x[p[l]] >> k) and (y[p[r + 1]] >> k) == (y[p[l]] >> k); r++) ;
            std::vector<int> vec;
            int px = x[p[l]] >> k, py = y[p[l]] >> k;
            std::vector<std::pair<int, int>> P = {{-1, 1}, {0, 1}, {1, 1}, {1, 0}};
            for (auto [dx, dy]: P) if (pos.count(id(px + dx, py + dy)))
            {
                auto [pl, pr] = pos[id(px + dx, py + dy)];
                std::vector<int> vec;
                vec.insert(vec.end(), p + l, p + r + 1);
                vec.insert(vec.end(), p + pl, p + pr + 1);
                std::inplace_merge(vec.begin(), vec.begin() + r - l + 1, vec.end());
                for (int i = 0; i < (int)vec.size(); i++) for (int j = i + 1; j <= i + 3 and  j < (int)vec.size(); j++) A[vec[j]].push_back(vec[i]);
            }
        }
        std::unordered_map<long long, std::pair<int, int>>().swap(pos);
    }
    for (int i = 1; i <= n; i++) t1[i] = t2[i] = 1LL << 60;
    for (int i = 1; i <= n; i++)
    {
        for (int p: A[i]) add(p, dis(p, i));
        for (auto [p, id]: Q[i]) ans[id] = std::min(ans[id], ask(p));
    }
    for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
    return 0;
}