题目链接：http://codeforces.com/problemset/problem/762/E
题目大意：
一共有 n 个电台，对于每个电台 i 有三个参数：
\(x_i\), \(r_i\), \(f_i\),分别指它的一维坐标、作用半径和频率。如果两个电台的频率差值在 k 内，并且它们的作用范围都能覆盖到彼此，那么就称这两个电台相互干扰。问这 n 个站台中相互干扰的站台有多少对。
解题思路：
完全参考资料 陈麒安大佬的博客
核心思路是把问题转换成：
- \(r_i \le r_j\)
- \(|x_i - x_j| \le r_i\)
- \(|f_i - f_j| \le k\)
使用 CDQ分治解决。
示例程序：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int tr[maxn<<2];
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
void push_up(int rt) {
tr[rt] = tr[rt<<1] + tr[rt<<1|1];
}
void add(int p, int x, int l, int r, int rt) {
if (l == r) {
tr[rt] += x;
return;
}
int mid = (l + r) / 2;
(p <= mid) ? add(p, x, lson) : add(p, x, rson);
push_up(rt);
}
int query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) return tr[rt];
int res = 0, mid = (l + r) / 2;
if (L <= mid) res += query(L, R, lson);
if (R > mid) res += query(L, R, rson);
return res;
}
int n, K;
long long ans;
struct Node {
int x, r, f;
} a[maxn];
bool cmp1(Node a, Node b) {
return a.r < b.r || a.r == b.r && a.f < b.f;
}
bool cmp2(Node a, Node b) {
return a.f < b.f;
}
int x[maxn];
void cdq(int l, int r) {
if (l >= r) return;
int mid = (l + r) / 2;
cdq(l, mid);
cdq(mid+1, r);
sort(a+l, a+mid+1, cmp2);
sort(a+mid+1, a+r+1, cmp2);
for (int i = l; i <= r; i++)
x[i] = a[i].x;
sort(x+l, x+r+1);
int j = mid+1, k = mid+1;
for (int i = l; i <= mid; i++) {
while (j <= r && a[j].f - a[i].f <= K) {
int p = lower_bound(x+l, x+r+1, a[j].x) - x;
assert(p >= l && p <= r);
add(p, 1, 1, n, 1);
j++;
}
while (k <= r && a[i].f - a[k].f > K) {
int p = lower_bound(x+l, x+r+1, a[k].x) - x;
assert(p >= l && p <= r);
add(p, -1, 1, n, 1);
k++;
}
int p = lower_bound(x+l, x+r+1, a[i].x - a[i].r) - x,
q = upper_bound(x+l, x+r+1, a[i].x + a[i].r) - x;
assert(p >= l && p <= r);
assert(q >= l && q <= r+1);
ans += query(p, q-1, 1, n, 1);
}
for (int t = k; t < j; t++) {
int p = lower_bound(x+l, x+r+1, a[t].x) - x;
assert(p >= l && p <= r);
add(p, -1, 1, n, 1);
}
}
int main() {
scanf("%d%d", &n, &K);
for (int i = 1; i <= n; i++)
scanf("%d%d%d", &a[i].x, &a[i].r, &a[i].f);
sort(a+1, a+n+1, cmp1);
cdq(1, n);
printf("%lld\n", ans);
return 0;
}