DDOSvoid's Blog

Luogu P4169 [Violet]天使玩偶/SJY摆棋子

发表于 更新于 分类于
本文字数： 2.1k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P4169

简要题意：给定 $n$ 个二维点，现在有 $m$ 次操作，操作有两种，第一种操作是加入一个二维点 $(x_i,y_i)$；第二种操作给定一个二维点 $(x_i,y_i)$ 求离它最近的点与它的距离

$n\le 3\times 10^5$

Solution

变换坐标后做四次 $cdq$ 分治就行了

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 300010
#define maxk 1000010
#define cQ const Query
#define lowbit(i) ((i) & (-i))
#define INF 1000000000
using namespace std;

int n, m; 

struct Query {
    int x, y, z, id;

    friend bool operator < (cQ &u, cQ &v) { return u.x < v.x; } 
} Q[2 * maxn];
bool cmp(cQ &u, cQ &v) { return u.z < v.z; }

int Bit[maxk], N;
void add(int i, int v) { while (i <= N) Bit[i] = max(Bit[i], v), i += lowbit(i); }

void clear(int i) { while (i <= N) Bit[i] = -1, i += lowbit(i); } 

int query(int i) {
    int s = -1;
    while (i) s = max(s, Bit[i]), i -= lowbit(i);
    return s;
}

int ans[maxn];
void cdq(int l, int r) {
    if (l == r) return ; int m = l + r >> 1, j = l - 1;
    cdq(l, m); cdq(m + 1, r);
    for (int i = m + 1; i <= r; ++i) {
        int x = Q[i].x, y = Q[i].y, id = Q[i].id; if (!id) continue; 
        while (j < m && Q[j + 1].x <= x) ++j, !Q[j].id && (add(Q[j].y, Q[j].x + Q[j].y), 1);
        int v = query(y); ~v && (ans[id] = min(ans[id], x + y - v)); 
    }
    for (int i = l; i <= j; ++i) clear(Q[i].y); 
    inplace_merge(Q + l, Q + m + 1, Q + r + 1);
}

int cans;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> Q[i].x >> Q[i].y; Q[i].z = i; ++Q[i].y;
        N = max(N, Q[i].x); N = max(N, Q[i].y); 
    } 
    for (int i = 1; i <= m; ++i) {
        cin >> Q[i + n].id >> Q[i + n].x >> Q[i + n].y;
        ++Q[i + n].y; Q[i + n].z = i + n; --Q[i + n].id;
        if (Q[i + n].id) Q[i + n].id = ++cans;
        N = max(N, Q[i + n].x); N = max(N, Q[i + n].y);
    } ++N; m += n;
    for (int i = 1; i <= n; ++i) ans[i] = INF; 
    cdq(1, m);
    for (int i = 1; i <= m; ++i) Q[i].x = N - Q[i].x;
    sort(Q + 1, Q + m + 1, cmp); cdq(1, m); 
    for (int i = 1; i <= m; ++i) Q[i].y = N - Q[i].y;
    sort(Q + 1, Q + m + 1, cmp); cdq(1, m);
    for (int i = 1; i <= m; ++i) Q[i].x = N - Q[i].x;
    sort(Q + 1, Q + m + 1, cmp); cdq(1, m);
    for (int i = 1; i <= cans; ++i) cout << ans[i] << "\n"; 
    return 0;
}