CF1045G

发表于 | 阅读数

给予$n$个机器人，坐标$x$,观察范围$r$,智商$q$,对于一个机器人，如果有机器人在$[x-r,x+r]$，智商在$[q-k,q+k]$,之间则可以被观察到，问多少对机器人互相观察到。

$(n\leq 10^5,k\leq 20)$

CDQ分治

如果不需要互相看见，直接二维数点，即二维偏序即可。互相看见，只需要让半径小的去看半径大的，如果$r$小的能看见$r$大的，必然也能互相看到。这个时候第一层偏序以$r$排序

  • 做法1：偏序完直接在CDQ分治里做二维偏序的准备工作（常数可能有点大）
  • 做法2:提前做好二维偏序数点准备，第一层偏序以$x$，第二层以$y$偏序，统计有多少$r< R_{query}$。
  • 做法3:观察到$k$很小，可以用单调队列，维护头尾。即可
  • 做法4:若提前处理二维编序，第一层是$r$,则会在是否记录本身这个点上产生模糊不清！无法$AC$
  • 注意，进行CDQ分治的时候注意排序函数需要兼顾所有维度

动态开点线段树

由于$k$小，我们可以在每个$q$,上建立线段树，最后$[-k+q,k+q]$,的线段树。$O(2kq\log n)$,在CF的神奇服务器上卡过

做法1 
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int num, li[N * 5], tr[N * 5];
int lowbit(int x)
{
    return (-x) & x;
}
void update(int x, int w)
{
    while (x <= num)
    {
        tr[x] += w;
        x += lowbit(x);
    }
}
int query(int x)
{
    int res = 0;
    while (x)
    {
        res += tr[x];
        x -= lowbit(x);
    }
    return res;
}
int query(int l, int r)
{
    return query(r) - query(l - 1);
}
struct node
{
    int x, y, r, op;
} e[N * 5], s[N * 5];
bool cmp1(node a, node b)
{
    return a.r > b.r;
}
bool cmp2(node a, node b)
{
    if (a.x != b.x)
        return a.x < b.x;
    if (a.y != b.y)
        return a.y < b.y;
    return a.op < b.op;
}
int n, k;
ll ans;
void cdq(int l, int r)
{
    //cout << l << " " << r << endl;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    // sort(e + l, e + 1 + mid, cmp2);
    // sort(e + 1 + mid, e + 1 + r, cmp2);

    int cnt = 0;
    num = 0;
    for (int i = l; i <= mid; i++)
    {
        int x = e[i].x, y = e[i].y, r = e[i].r;
        s[++cnt] = (node){x, y, 0, -10};
        li[++num] = e[i].y;
    }
    for (int i = mid + 1; i <= r; i++)
    {
        int x = e[i].x, y = e[i].y, r = e[i].r;
        li[++num] = e[i].y + k;
        li[++num] = e[i].y - k - 1;
        s[++cnt] = (node){x + r, y + k, 0, 1};
        s[++cnt] = (node){x - r - 1, y - k - 1, 0, 1};
        s[++cnt] = (node){x + r, y - k - 1, 0, -1};
        s[++cnt] = (node){x - r - 1, y + k, 0, -1};
    }
    sort(1 + li, 1 + li + num);
    num = unique(1 + li, 1 + li + num) - li - 1;
    for (int i = 1; i <= cnt; i++)
        s[i].y = lower_bound(1 + li, 1 + li + num, s[i].y) - li;
    sort(s + 1, s + 1 + cnt, cmp2);
    for (int i = 1; i <= cnt; i++)
    {
        if (s[i].op == -10)
            update(s[i].y, 1);
        else
            ans += s[i].op * query(s[i].y);
    }
    //cout << s[1].x << endl;
    for (int i = 1; i <= cnt; i++)
        if (s[i].op == -10)
            update(s[i].y, -1);
    // cout << cnt << endl;
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        int x, r, q;
        scanf("%d%d%d", &x, &r, &q);
        e[i].x = x;
        e[i].y = q;
        e[i].r = r;
    }

    sort(e + 1, e + 1 + n, cmp1);
    // for (int i = 1; i <= cnt; i++)
    //     cout << e[i].x << " " << e[i].y << endl;
    cdq(1, n);
    printf("%lld\n", ans);
}
做法2 
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
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int n, tr[N * 5];
int lowbit(int x)
{
    return (-x) & x;
}
void update(int x, int w)
{
    while (x <= n)
    {
        tr[x] += w;
        x += lowbit(x);
    }
}
int query(int x)
{
    int res = 0;
    while (x)
    {
        res += tr[x];
        x -= lowbit(x);
    }
    return res;
}
int query(int l, int r)
{
    return query(r) - query(l - 1);
}
struct node
{
    int x, y, r, flag, add;
} e[N * 5], p[N];
bool cmp1(node a, node b)
{
    if (a.x == b.x)
        if (a.y == b.y)
            return a.r < b.r;
        else
            return a.y < b.y;
    else
        return a.x < b.x;
}
bool cmp2(node a, node b)
{
    if (a.y == b.y)
        return a.r < b.r;
    else
        return a.y < b.y;
}
bool cmp3(node a, node b)
{
    return a.r > b.r;
}
int k, cnt;
ll ans;
void cdq(int l, int r)
{
    //cout << l << " " << r << endl;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    sort(e + l, e + 1 + mid, cmp2);
    sort(e + 1 + mid, e + 1 + r, cmp2);
    int j = l;
    for (int i = mid + 1; i <= r; i++)
    {
        while (e[j].y <= e[i].y && j <= mid)
        {
            if (e[j].flag == 0)
                update(e[j].r, 1);
            j++;
        }
        if (e[i].flag == 1)
            ans += e[i].add * query(e[i].r);
    }
    for (int i = l; i < j; i++)
        if (e[i].flag == 0)
            update(e[i].r, -1);
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &p[i].x, &p[i].r, &p[i].y);
    sort(1 + p, 1 + p + n, cmp3);
    for (int i = 1; i <= n; i++)
    {
        int x = p[i].x, r = p[i].r, q = p[i].y;

        e[++cnt] = (node){x + r, q + k, i, 1, 1};
        e[++cnt] = (node){x - r - 1, q - k - 1, i, 1, 1};
        e[++cnt] = (node){x + r, q - k - 1, i, 1, -1};
        e[++cnt] = (node){x - r - 1, q + k, i, 1, -1};
        e[++cnt] = (node){x, q, i + 1, 0, 0};
    }

    sort(e + 1, e + 1 + cnt, cmp1);
    // for (int i = 1; i <= cnt; i++)
    //     cout << e[i].x << " " << e[i].y << endl;
    cdq(1, cnt);
    printf("%lld\n", ans);
}
做法3 
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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int num, li[N * 5], tr[N * 5];
int lowbit(int x)
{
    return (-x) & x;
}
void update(int x, int w)
{
    while (x <= num)
    {
        tr[x] += w;
        x += lowbit(x);
    }
}
int query(int x)
{
    int res = 0;
    while (x)
    {
        res += tr[x];
        x -= lowbit(x);
    }
    return res;
}
int query(int l, int r)
{
    return query(r) - query(l - 1);
}
struct node
{
    int l, r, p, rr, q;
} e[N * 5];
bool cmp1(node a, node b)
{
    return a.rr > b.rr;
}
bool cmp2(node a, node b)
{
    return a.q < b.q;
}
int n, k, cnt;
ll ans;
void cdq(int l, int r)
{
    //cout << l << " " << r << endl;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    cdq(l, mid);
    cdq(mid + 1, r);
    sort(e + l, e + 1 + mid, cmp2);
    sort(e + 1 + mid, e + 1 + r, cmp2);
    int L = l, R = l - 1;
    for (int i = mid + 1; i <= r; i++)
    {
        while (L <= mid && e[i].q - e[L].q > k)
            update(e[L].p, -1), L++;
        while (R + 1 <= mid && e[R + 1].q - e[i].q <= k)
            R++, update(e[R].p, 1);
        ans += query(e[i].r) - query(e[i].l);
    }
    for (int i = L; i <= R; i++)
        update(e[i].p, -1);
}
 
int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
    {
        int x, r, q;
        scanf("%d%d%d", &x, &r, &q);
        e[++cnt] = (node){x - r-1, x+ r , x, r, q};
        li[++num] = x;
        li[++num] = x + r;
        li[++num] = x - r - 1;
    }
    sort(1 + li, 1 + li + num);
    num = unique(1 + li, 1 + li + num) - li - 1;
    for (int i = 1; i <= cnt; i++)
        e[i].l = lower_bound(1 + li, 1 + li + num, e[i].l) - li,
        e[i].r = lower_bound(1 + li, 1 + li + num, e[i].r) - li,
        e[i].p = lower_bound(1 + li, 1 + li + num, e[i].p) - li;
    sort(e + 1, e + 1 + cnt, cmp1);
    // for (int i = 1; i <= cnt; i++)
    //     cout << e[i].x << " " << e[i].y << endl;
    cdq(1, cnt);
    printf("%lld\n", ans);
}