CDQ分治。

Table of Contents

  1. Description
  2. Solution

Description

火星上有$N$个机器人排成一行，第$i$个机器人的位置为$x_{i}$，视野为$r_{i}$，智商为$q_{i}$。我们认为第ii个机器人可以看到的位置是$[x_{i}-r_{i},x_{i}+r_{i}]$。

如果一对机器人相互可以看到，且它们的智商$q_{i}$的差距不大于$K$，那么它们会开始聊天。 为了防止它们吵起来，请计算有多少对机器人可能会聊天。

Solution

其实可以把问题抽象成一个二维平面, 查询$[x_l, x_r]$, $[y_l, y_r]$子平面内的点数.

树套树是不会写的, 这辈子都不会写的, 又没写过二维数据结构, K-D Tree也不会写, 只能看看大佬, 打打CDQ这样子. CDQ代码又少, 读起来又容易, 我超喜欢在这里!

大概就就是用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
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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e+5 + 5;

struct robo
{
	int x, r, q;
}ro[maxn];
struct opt
{
	int tim, x, y, l, r, typ;
}q[maxn * 3];
int tot, n, k, cpy[maxn], ptr, len;
std::map<int, int> mp;
ll ans;

struct BIT
{
	int b[maxn];
	BIT(){memset(b, 0, sizeof b);}
	inline void add(int x, int c) {for(; x <= len; x += (x & -x)) b[x] += c;}
	inline int query(int x){int ret = 0; for(; x >= 1; x -= (x & -x)) ret += b[x]; return ret;}
}b;

bool cmp_time(opt lhs, opt rhs)
{
	return lhs.tim < rhs.tim;
}
bool cmp_pos(opt lhs, opt rhs)
{
	return (lhs.x == rhs.x) ? (lhs.typ == 0) : (lhs.x < rhs.x);
}
bool cmp_rob(robo lhs, robo rhs)
{
	return lhs.r > rhs.r;
}

void CDQ(int l, int r)
{
	if(l >= r) return;
	int mid = (l + r) >> 1;
	//cerr << l << " " << r << endl;
	CDQ(l, mid);
	sort(q + l, q + 1 + mid, cmp_pos);
	sort(q + 1 + mid, q + 1 + r, cmp_pos);
	//cerr << "sort" << endl;
	int i = l, j = mid + 1;
	while(i <= mid && j <= r)
	{
		if(q[i].x <= q[j].x)
		{
			if(q[i].typ == 0)
				b.add(q[i].y, 1);
			++i;
		}
		else
		{
			if(q[j].typ != 0)
				ans += q[j].typ * (b.query(q[j].l) - b.query(q[j].r-1));
			++j;
		}
	}
	//cerr << "merge" << endl;
	for(int k = j; k <= r; ++k) ans += q[k].typ * (b.query(q[k].l) - b.query(q[k].r-1));
	for(int k = l; k < i; ++k)
		if(q[k].typ == 0) b.add(q[k].y, -1);
	sort(q + mid + 1, q + r + 1, cmp_time);
	CDQ(mid + 1, r);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	typedef map<int, int>::iterator iter;

	cin >> n >> k;
	for(int i = 1; i <= n; ++i)
	{
		cin >> ro[i].x >> ro[i].r >> ro[i].q;
		cpy[i] = ro[i].q;
	}
	sort(cpy + 1, cpy + 1 + n);
	len = unique(cpy + 1, cpy + 1 + n) - (cpy + 1);
	for(int i = 1; i <= len; ++i) mp[cpy[i]] = i;
	mp[0x3f3f3f3f] = 1;
	sort(ro + 1, ro + 1 + n, cmp_rob);
	for(int i = 1; i <= n; ++i)
	{
		iter l = mp.upper_bound(ro[i].q + k); --l;
		iter r = mp.lower_bound(ro[i].q - k);
		++ptr; q[ptr] = (opt){ptr, ro[i].x - ro[i].r - 1, 0, l->second, r->second, -1};
		++ptr; q[ptr] = (opt){ptr, ro[i].x + ro[i].r, 0, l->second, r->second, 1};
		++ptr; q[ptr] = (opt){ptr, ro[i].x, mp[ro[i].q], 0, 0, 0};
	}
	//cerr << "bgn" << endl;
	CDQ(1, ptr);

	cout << ans << endl;
	return 0;
}