文章目录
题意
有 n n n个电台，对于每个电台 i i i有三个参数 x i , r i , f i x_i,r_i,f_i xi,ri,fi，分别指他们的坐标、作用半径、频率。如果两个电台频率差值在 k k k以内，并且他们的作用范围都能覆盖到彼此，那么称这两个电台互相干扰，问这 n n n个站台中互相干扰的站台有多少对。
$1\le n\le1e5,0\le k\le 10,1\le x_i,r_i\le 1e9,1\le f_i\le 1e4 $
思路：
首先将问题简化一下，题面无非就是求满足以下两个条件的对数：
( 1 ) ∣ x i − x j ∣ ≤ m i n ( r i , r j ) (1)|x_i-x_j|\le min(r_i,r_j) (1)∣xi−xj∣≤min(ri,rj)
( 2 ) ∣ f i − f j ∣ ≤ k (2)|f_i-f_j|\le k (2)∣fi−fj∣≤k
看起来很 c d q cdq cdq，考虑怎么分三维。
首先绝对值和取 m i n min min肯定是要优先考虑的，并且如果我们确定了 r r r的话，这个貌似就变成了个区间查询的问题，所以我们第一维按照 r r r从大到小排序，这样 r r r的值 [ l , m i d ] > [ m i d + 1 , r ] [l,mid]>[mid+1,r] [l,mid]>[mid+1,r]，算左区间对右区间的贡献的时候，左区间的 x i x_i xi直接加入答案中，右区间貌似直接查询一下 [ x j − r j , x j + r j ] [x_j-r_j,x_j+r_j] [xj−rj,xj+rj]区间内的个数即可，离散化+树状数组完全可以解决，这样我们就定下来了第三维。那么第二维就剩下 f f f了，我们在第三维查询区间内个数的时候，需要满足 ∣ f i − f j ∣ ≤ k |f_i-f_j|\le k ∣fi−fj∣≤k，也就是说树状数组存下来的需要是合法的 f f f，所以我们考虑整个指针代表的左区间 [ x , i ] [x,i] [x,i]，由于第二维 f i < f j f_i<f_j fi<fj成立，所以对于 f j f_j fj我们需要保证 f x + k > = f j f_x+k>=f_j fx+k>=fj最小的 x x x即可，显然这个具有单调性，动态维护一下。
但是很快你就会发现不对劲，因为 ∣ f i − f j ∣ ≤ k |f_i-f_j|\le k ∣fi−fj∣≤k是带绝对值的！所以你只考虑左边 ≤ f j \le f_j ≤fj是不对的，你还需要维护一个指针 y y y，这个需要找到 f y − k < = f j f_y-k<=f_j fy−k<=fj的最大的 y y y位置。之后就得到了区间 [ x , y ] [x,y] [x,y]，现在就可以查询啦~
由于第二维保证有序，所以 j j j右移的时候， x , y x,y x,y也是单调不减的，可以保证复杂度。
还有要注意，离散化的时候，离散化得到的 l , r l,r l,r需要跟 i i i下表绑定，也就是放到结构体里面，闲的没事开了个数组存，结果 c d q cdq cdq的时候改变了顺序 w a wa wa了半天。。。
复杂度 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)
// Problem: E. Radio stations
// Contest: Codeforces - Educational Codeforces Round 17
// URL: https://codeforces.com/problemset/problem/762/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
//#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
#define lowbit(x) (x&(-x))
using namespace std;
//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); }
//void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); }
//void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f;
const double eps=1e-6;
int n,k;
PII p[N];
int tr[N],se;
LL ans;
struct Node {
int x,y,z,l,r;
bool operator < (const Node &W) const {
return mk(-x,mk(y,z))<mk(-W.x,mk(W.y,W.z));
}
}q[N],a[N];
vector<int>v;
int find(int x) {
return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void add(int x,int c) {
for(int i=x;i<=se;i+=lowbit(i)) tr[i]+=c;
}
int sum(int x) {
int ans=0;
for(int i=x;i;i-=lowbit(i)) ans+=tr[i];
return ans;
}
bool cmp(Node a,Node b) {
return a.y<b.y;
}
void cdq(int l,int r) {
if(l>=r) return;
int mid=(l+r)>>1;
cdq(l,mid); cdq(mid+1,r);
int ls=l,rs=l;
for(int i=mid+1;i<=r;i++) {
while(ls<=mid&&q[ls].y+k<q[i].y) add(q[ls].z,-1),ls++;
while(rs<=mid&&q[rs].y-k<=q[i].y) add(q[rs].z,1),rs++;
ans+=sum(q[i].r)-sum(q[i].l-1);
}
while(ls<rs) add(q[ls].z,-1),ls++;
int i=l,j=mid+1,cnt=0;
while(i<=mid&&j<=r) {
if(q[i].y<=q[j].y) a[++cnt]=q[i++];
else a[++cnt]=q[j++];
}
while(i<=mid) a[++cnt]=q[i++];
while(j<=r) a[++cnt]=q[j++];
for(int i=1;i<=cnt;i++) q[l+i-1]=a[i];
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) {
int x,y,z; scanf("%d%d%d",&x,&y,&z);
q[i]={y,z,x};
v.pb(x-y); v.pb(x+y); v.pb(x);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
se=v.size();
sort(q+1,q+1+n);
for(int i=2;i<=n;i++) if(q[i].x==q[i-1].x&&q[i].y==q[i-1].y&&q[i].z==q[i-1].z) while(1);
for(int i=1;i<=n;i++) {
q[i].l=find(q[i].z-q[i].x),q[i].r=find(q[i].z+q[i].x);
q[i].z=find(q[i].z);
}
cdq(1,n);
cout<<ans<<endl;
return 0;
}
/*
k=1
r f x
x y z
10 8 4
3 10 1
2 5 3
1 2 0**
1 3 1**
4 5 1**
1 5 3**
*/
// #include <bits/stdc++.h>
// using namespace std;
// typedef long long ll;
// #define rep(i, a, b) for(int i=(a), i##up=(b); i<=i##up; ++i)
// #define repf(i, a) for(int i=1, i##up=(a); i<=i##up; ++i)
// #define rrep(i, a, b) for(int i=(a), i##dn=(b); i>=i##dn; --i)
// #define repe(e, u) for(int e=head[u]; e; e=nxt[e])
//
// int read() {
// int t=0, f=1; char c;
// while(!isdigit(c=getchar())) f=c^45;
// while(isdigit(c)) t=(t<<1)+(t<<3)+(c^48), c=getchar();
// return f? t: -t;
// }
//
// const int N=1e5+10, inf=1e9;
//
// int n, k;
// ll ans;
//
// struct BIT {
// #define lb(x) ((x)&-(x))
// static const int X=3e5;
// int c[X+10], tik[X+10], tim;
// inline void modify(int x, int v=1) {
// for(; x<=X; x+=lb(x)) if(tik[x]==tim) c[x]+=v; else tik[x]=tim, c[x]=v;
// }
// inline int query(int x, int v=0) {
// for(; x; x^=lb(x)) if(tik[x]==tim) v+=c[x]; else tik[x]=tim, c[x]=0;
// return v;
// }
// inline void clear() { tim++; }
// }tre;
//
// int px[N*3], siz;
// inline int find(int x) {
// return lower_bound(px+1, px+1+siz, x)-px;
// }
// struct state {
// int x, r, f, le, ri;
// state() {}
// state(int a, int b, int c): x(a), r(b), f(c) {}
// inline void get() {
// x=read(), r=read(), f=read();
// le=x-r, ri=x+r;
// px[++siz]=x, px[++siz]=le, px[++siz]=ri;
// }
// inline void reset() {
// x=find(x), le=find(le), ri=find(ri);
// }
// }st[N];
// bool cmpr(state a, state b) {
// if(a.r==b.r) return a.f<b.f||a.f==b.f&&a.x<b.x;
// return a.r>b.r;
// }
// bool cmpf(state a, state b) {
// return a.f<b.f;
// }
//
// void sol(int le, int ri) {
// if(le==ri) return;
// int mid=le+ri>>1;
// sol(le, mid), sol(mid+1, ri), tre.clear();
// sort(st+le, st+mid+1, cmpf), sort(st+mid+1, st+ri+1, cmpf);
// int pi_dn=le, pi_up=le, pj=mid+1;
// while(pj<=ri) {
// while(st[pj].f-st[pi_dn].f>k&&pi_dn<=mid) tre.modify(st[pi_dn++].x, -1);
// while(st[pi_up].f-st[pj].f<=k&&pi_up<=mid) tre.modify(st[pi_up++].x);
// ans+=tre.query(st[pj].ri)-tre.query(st[pj].le-1), pj++;
// }
// }
//
// int main() {
// n=read(), k=read();
// repf(i, n) st[i].get();
// sort(px+1, px+1+siz), siz=unique(px+1, px+1+siz)-px-1;
// repf(i, n) st[i].reset();
// sort(st+1, st+1+n, cmpr);
// sol(1, n);
// printf("%lld", ans);
// }