题解：P9062 [Ynoi2002] Adaptive Hsearch&Lsearch

· · 题解

问题即求所有满足二维偏序的二元组的权值 \max，自然地，考虑缩减 (x,y) 对数。

仿照平面最近点对的 O(n) 做法划分网格。由于序列顺序的限制，我们必须按编号从左往右依次加点，那也就不能分析期望复杂度，不能动态重构划分方案。

考虑取若干阈值 b 划分，还是只考虑距离 <b_k 的点对。每次加入一个点 i，显然也是只需考虑周围的九宫格，问题在于同一格内可能有很多点。类似的，距离 <b_{k-1} 的点对无需在此考虑。

只考虑 \mathrm{dis}(p,i)\ge b_{i-1} 的 p，可以发现，若一格内有很多点，一定存在 p<q 使得 (p,q) 距离比 (p,i) 小，此时 (p,q) 偏序了 (p,i)，p 对于 i 就是无用的。去掉这些点后显然两两距离 \ge \mathrm{dis}(p,i)\ge b_{i-1}，那么点数是 O((\dfrac{b_i}{b_{i-1}})^2) 的。

所以只要在加入 q 时删除掉 p 即可，也就是每次加入时先遍历所有点与 i 构成对更新答案，然后删除所有距离 <b_{i-1} 的点。可以发现令 b_i=B^i 最优。使用 \mathrm{BIT} 维护答案，复杂度 O(nB^2\log_BV\log n)。

具体常数大概是 9(B+1)^2\log_BV，取 B=2 即可轻松通过。

#include <bits/stdc++.h>
using namespace std;
const int dx[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1}, dy[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1}, mod = 1 << 20, M = mod - 1;
struct node {
    long long x, y;
}a[250005];
int n, m, cnt;
long long ans[250005];
vector<int> v[250005];
vector<node> b[250005], q[250005];
struct Htable {
    pair<long long, int> a[mod];
    auto &operator [] (long long x) {
        for(uint p = x * 10815553818077224714ull >> 44;; ++p &= M)
            if(!a[p].first || a[p].first == x)
                return a[p];
    }
    void clear() {
        return fill(a, a + mod, make_pair(0, 0));
    }
}mp;
long long f(long long x) {
    return x * x;
}
long long dis(node a, node b) {
    return f(a.x - b.x) + f(a.y - b.y);
}
struct BIT {
    long long t[250005];
    BIT() {
        memset(t, 0x3f, sizeof(t));
    }
    int lowbit(int x) {
        return x & -x;
    }
    void update(int x, long long v) {
        while(x)
            t[x] = min(t[x], v), x -= lowbit(x);
        return;
    }
    long long query(int x) {
        long long s = 1e18;
        while(x <= n)
            s = min(s, t[x]), x += lowbit(x);
        return s;
    }
}T;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].y;
    for(int i = 1, l, r; i <= m; i++)
        cin >> l >> r, q[r].push_back({l, i});
    for(int k = 1; k < 27; k++) {
        cnt = 0, mp.clear();
        for(int i = 1; i <= n; i++) {
            int x = a[i].x >> k, y = a[i].y >> k;
            x++, y++;
            for(int l = 0; l < 9; l++) {
                int nx = x + dx[l], ny = y + dy[l];
                auto &t = mp[nx * (1ll << 27) | ny];
                if(t.first) {
                    vector<int> tmp;
                    for(int j : v[t.second]) {
                        auto d = dis(a[i], a[j]);
                        b[i].push_back({j, d});
                        if(d >= (1ll << (k - 1 << 1)))
                            tmp.push_back(j);
                    }
                    v[t.second] = tmp;
                }
            }
            auto &t = mp[{x * (1ll << 27) | y}];
            if(!t.first)
                t.second = ++cnt;
            t.first = x * (1ll << 27) | y, v[t.second].push_back(i);
        }
        for(int i = 1; i <= cnt; i++)
            v[i].clear();
    }
    for(int i = 1; i <= n; i++) {
        for(auto j : b[i])
            T.update(j.x, j.y);
        for(auto j : q[i])
            ans[j.y] = T.query(j.x);
    }
    for(int i = 1; i <= m; i++)
        cout << ans[i] << '\n';
    return 0;
}