P9062 Ynoi2002 区间平面最近点对

· · 题解

2.10

看题。

容易发现这个题是在询问一个区间内的点集里的平面最近点对。

2.11

15 分：暴力，O(qn^2)。

平面最近点对有一些很优秀的算法，随便选一些出来用就好了。O(qn\log n)，（还是 15 分）。

因为是 Ynoi，而且时限很宽松，所以不考虑分治这种 polylog 的结构，发现有一些依赖于排序，且正确性很高的随机化算法可以用，即按照某种策略排序后取排好的序列里面相近的 \log 级别的项作为备选答案。好像不能分块，但是可以莫队，用平衡树维护一个有序的序列即可，但是这个东西有 chkmin，所以不好删除，回滚一下就好了，O(n\sqrt q\log^2n)，还是 15 分。

换一个比较厉害的平衡树，比如 Trie（好像有人叫它多叉线段树？），于是有一个 \log n 变成了 \log_{64} n，而且常数小了很多，可以拿 40 分。

用一些奇技淫巧，又通过了 case 9,15,16,17，有 60 分。此时似乎把所有还没通过的人的解缝合起来，就可以解决所有测试点了。

今天就摆到这里吧，剩下的明天想。

2.12

考虑平面最近点对的一个线性做法，即划分方格。常规全局做法是：random_shuffle 整个点集，然后将整个平面划分成若干个 t\times t 的方格，用 hash_map 维护每个方格的点集，其中 t 是第 1,2 个点的距离，然后向后扫描，对于每个插入的 i，只需要扫描其所属的方格及周围八个方向的方格即可，若答案 t 更新则重新划分。插入点时，由于答案是 t，每个点之间的距离不会小于 t，所以一个方格至多有 4 个点在里面，是 O(1) 的；每个点 i 插入时重新划分的概率是 O(\frac{1}{i}) 的，重构是 O(i) 的，所以期望 O(n)。

以下内容经大佬指点。

在不考虑复杂度的前提下，维护固定边长 \frac{\sqrt 2}{4}t 的方格适用于所有的距离不超过 t 的点的情况（连接相邻两个方格的顶点距离不超过 t），此时插入一个点然后查找周围点更新等于在做暴力。

怎么优化呢？只要先维护小方格，然后维护大方格的时候可以去掉小方格里包含的情况，即：小方格里相邻的贡献已经统计过了，此时再维护不会更优。

考虑维护长度 2^0,2^1,2^2...2^{\lfloor\log V\rfloor} 的情况，它们足以覆盖所有查询范围。

枚举次数 t，插入一个点 i 时，删掉相邻方格里所有 dis(i,j)\lt 2^{t-1} 的 j，此时每个方格维护点数依然是 O(1)。

查询的话，因为每次都是在前缀上插入一个点，可以像扫描线一样去做。每个点维护的信息是它后面的点与它构成的最小距离，查询区间最小值即可，由于我们有 O(n\log V) 次单点修改，但是只有 q 次询问，考虑用分块平衡一下复杂度，可以做到 O(n\log V+q\sqrt n)。

实现的话，不算很卡常，不手写任何数据结构可以过，如果你感觉过不去，考虑手写哈希即可。下面代码保留了一部分卡常的内容，这样才知道你做的是 Ynoi，注意洛谷的评测姬波动已经达到了一个点 1s，所以你就算手写哈希也有可能过不了。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#define mp MP[s]
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
const int N = 2.5e5 + 5, V = 1e8, dx[] = {1, 1, 1, -1, -1, -1, 0, 0, 0}, dy[] = {1, 0, -1, 1, 0, -1, 1, 0, -1};
int _x[N], _y[N], bx[N], by[N], n, Q, bel[N];
ll v1[N], v2[N], ans[N];
inline void chkmin(ll &x, ll y) {
    x = min(x, y);
}
inline void chkmax(ll &x, ll y) {
    x = max(x, y);
}
inline ll uid(int x, int y) {
    return 10ll * x * V + y;
}
inline ll dis(int i, int j) {
    return 1ll * (_x[i] - _x[j]) * (_x[i] - _x[j]) + 1ll * (_y[i] - _y[j]) * (_y[i] - _y[j]);
}
inline void modify(int x, ll k) {
    chkmin(v1[x], k);
    chkmin(v2[bel[x]], k);
}
inline ll query(int l, int r) {
    int bl = bel[l], br = bel[r];
    ll res = 1e18;
    if (bl == br) {
        for (int i = l; i <= r; i++)
            chkmin(res, v1[i]);
        return res;
    } else {
        for (int i = l; bel[i] == bl; i++)
            chkmin(res, v1[i]);
        for (int i = bl + 1; i <= br; i++)
            chkmin(res, v2[i]);
    }
    return res;
}
vector<int> point[N * 30];
vector<pair<int, int>> q[N];
gp_hash_table<ll, int> MP[30];
signed main() {
//  freopen("test.in", "r", stdin);
//  freopen("test.out", "w", stdout);
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> Q;
    for (int i = 1; i <= n; i++)
        cin >> _x[i] >> _y[i];
    const int sq = sqrt(n);
    for (int i = 1; i <= n; i++)
        bel[i] = (i - 1) / sq + 1;
    for (int i = 1; i <= Q; i++) {
        int l, r;
        cin >> l >> r;
        q[r].emplace_back(make_pair(l, i));
    }
    for (int i = 1; i <= n; i++)
        v1[i] = v2[i] = 1e18;
    for (int i = 1; i <= Q; i++)
        ans[i] = 1e18;
    int idx = 0;
    for (int i = 1; i <= n; i++) {
        for (int s = 1; (1 << s) <= V; s++) {
            int x = _x[i] >> s, y = _y[i] >> s;
            if (mp.find(uid(x, y)) == mp.end()) {
                mp[uid(x, y)] = ++idx;
                point[idx].clear();
            }
            for (int j = 0; j < 9; j++) {
                int nx = x + dx[j], ny = y + dy[j];
                if (nx < 0 || ny < 0 || nx > (V >> s) || ny > (V >> s))
                    continue;
                if (mp.find(uid(nx, ny)) != mp.end()) {
                    int pid = mp[uid(nx, ny)];
                    vector<int> tmp;
                    for (int k : point[pid]) {
                        ll dik = dis(i, k);
                        modify(k, dik);
                        if (dik >= (1ll << (s + s - 2)))
                            tmp.emplace_back(k);
                    }
                    point[pid] = tmp;
                    if (j == 7)
                        point[pid].emplace_back(i);
                }
            }
        }
        for (auto &[l, id] : q[i])
            ans[id] = query(l, i);
    }
    for (int i = 1; i <= Q; i++)
        cout << ans[i] << '\n';
    return 0;
}