JOISC 2021 - Road Construction

Created2021-04-10Updated2021-04-11

連結

題意

給nn個二維平面上的點，定義兩點之間的距離為兩點的曼哈頓距離，請輸出前kk小的點對距離

1≤n,k≤2500001 \leq n, k \leq 250000

作法

這題是當初1!唯一有打的一場JOISC，然後開完題目想了半小時就放棄了XD
實在太難orz
而今天閒閒沒事做就來想這題，因為在1!聽別人討論有聽到轉座標這件事
所以就往這方面想，沒多久就想到了www

首先，先把座標轉個45度，也就是將(x,y)(x, y)取代成(x+y,x−y)(x + y, x - y)
這樣一來，會發現兩個點(x1,y1),(x2,y2)(x1, y1), (x2, y2)的曼哈頓距離會變成max(∣x1−x2∣,∣y1−y2∣)max(|x1 - x2|, |y1 - y2|)
啥？你問我為什麼會有人想到這個，窩不知道.jpg

這樣一來，合理的想法是要是我們找到第kk小的距離為xx
那就只要把所有距離<x< x的數值蒐集起來就好

那接著就可以來考慮一下二分搜，假設現在要計算距離≤d\leq d的點對數
那事實上就是∣x1−x2∣≤d,∣y1−y2∣≤d|x1 - x2| \leq d, |y1 - y2| \leq d的對數
可以很合理的想到掃描線 + BIT就能搞定

具體做法是先把點對按照xx座標排序，然後跑到一個點ii，就先把所有x座標<xi−d< x_i - d的點移除掉
接著問題同於找出所有y座標介於yi−dy_i - d和yi+dy_i + d之間的數量，這個用bit就能解決了

二分搜完就再用類似前面的做法，把bit改成set就能跑出所有≤x\leq x的答案
複雜度是O(nlognlogC)\mathcal{O}(nlognlogC)，這題給到10秒所以還算足夠

code

寫得還蠻醜的= =

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define test(x) cout << "Line(" << __LINE__ << ") " #x << ' ' << x << endl
#define printv(x) {\
	for (auto i : x) cout << i << ' ';\
	cout << endl;\
}
#define pii pair <int, int>
#define pll pair <lli, lli>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
template<typename A, typename B>
ostream& operator << (ostream& o, pair<A, B> a){
    return o << a.X << ' ' << a.Y;
}
template<typename A, typename B>
istream& operator >> (istream& o, pair<A, B> &a){
    return o >> a.X >> a.Y;
}
const int mod = 1e9 + 7, abc = 864197532, N = 300001, K = 111;

struct Pt {
    lli x, y, idx;
    Pt (lli _x = 0, lli _y = 0) : x(_x), y(_y) {}
    bool operator < (const Pt &o) const {
        return x < o.x;
    }
};

struct cmp {
    bool operator () (const Pt &a, const Pt &b) const {
        if (a.y == b.y) return a.idx < b.idx;
        return a.y < b.y;
    }
};

int bit[N];

void reset() {
    for (int i = 0; i < N; ++i) bit[i] = 0;
}

void add(int p, int v) {
    for (int i = p; i < N; i += i & (-i)) bit[i] += v;
}

int query(int p) {
    int ans = 0;
    for (int i = p; i > 0; i -= i & (-i)) ans += bit[i];
    return ans;
}

int main () {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector <Pt> a;
    for (int i = 0, x, y; i < n; ++i) {
        cin >> x >> y;
        a.pb(Pt(x + y, x - y));
        a.back().idx = i;
    }
    vector <lli> y_idx;
    for (int i = 0; i < n; ++i) y_idx.pb(a[i].y);
    sort(all(y_idx));
    y_idx.resize(unique(all(y_idx)) - y_idx.begin());
    auto get = [&](lli x) {
        return lower_bound(all(y_idx), x) - y_idx.begin() + 5;
    };
    sort(all(a));
    auto chk = [&](lli d) {
        reset();
        lli ans = 0;
        for (int i = 0, j = 0; i < n; ++i) {
            while (j < n && a[j].x + d < a[i].x) add(get(a[j++].y), -1);
            ans += query(get(a[i].y + d + 1) - 1) - query(get(a[i].y - d) - 1);
            add(get(a[i].y), 1);
        }
        return ans;
    };
    lli l = 0, r = 4e9 + 87;
    while (r - l > 1) {
        ((chk(l + r >> 1)) >= k ? r : l) = l + r >> 1;
    }
    lli d = l;
    vector <lli> ans;
    set <Pt, cmp> s;
    for (int i = 0, j = 0; i < n; ++i) {
        while (j < n && a[j].x + d < a[i].x) s.erase(a[j++]);
        for (auto it = s.lower_bound(Pt(0, a[i].y - d)); it != s.end() && it->y <= a[i].y + d; ++it) {
            ans.pb(max(a[i].x - it->x, abs(it->y - a[i].y)));
        }
        s.insert(a[i]);
    }
    sort(all(ans));
    for (int i = 0; i < k; ++i) {
        if (i < ans.size()) cout << ans[i] << '\n';
        else cout << r << '\n';
    }
}