题目链接
题意分析
一开始看的时候以为就是一道普通的二维数点问题
但是后来一看发现不是那么回事 因为ri的原因 存在我看得见你而你看不见我的情况
所以我们可以将这些点按照ri降序排序 这样后面的点如果可以看见前面的点 前面的点一定可以看见后面的点
这样的话就是二维数点问题了 但是我们发现这里的k很小
所以我们可以直接使用动态开点线段树来解决
CODE
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define N 5008611
#define INF 1000000000
using namespace std;
int n,m,tot,cnt;
int res[N];
int root[N],lson[N],rson[N],sum[N];
struct Node
{
int xi,ri,qi;
friend bool operator <(const Node &A,const Node &B)
{return A.ri>B.ri;}
}e[N];
long long ans;
void insert(int &now,int lenow,int rinow,int pos)
{
if(!now) now=++cnt;
sum[now]++;
if(lenow==rinow) return;
int mid=(lenow+rinow)>>1;
if(pos<=mid) insert(lson[now],lenow,mid,pos);
else insert(rson[now],mid+1,rinow,pos);
}
int qury(int now,int lenow,int rinow,int le,int ri)
{
if(!now) return 0;
if(le<=lenow&&rinow<=ri) return sum[now];
int mid=(lenow+rinow)>>1,tmp=0;
if(le<=mid) tmp+=qury(lson[now],lenow,mid,le,ri);
if(mid<ri) tmp+=qury(rson[now],mid+1,rinow,le,ri);
return tmp;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%d%d%d",&e[i].xi,&e[i].ri,&e[i].qi);
res[i]=e[i].qi;
}
sort(e+1,e+n+1);
sort(res+1,res+n+1);tot=unique(res+1,res+n+1)-res-1;
for(int i=1;i<=n;++i)
{
for(int j=max(0,e[i].qi-m);j<=min(INF,e[i].qi+m);++j)
{//对于第二维直接枚举
int pos=lower_bound(res+1,res+tot+1,j)-res;
if(res[pos]!=j) continue;
ans+=qury(root[pos],0,INF,max(0,e[i].xi-e[i].ri),min(INF,e[i].xi+e[i].ri));
}
int pos=lower_bound(res+1,res+tot+1,e[i].qi)-res;
insert(root[pos],0,INF,e[i].xi);
}
printf("%lld\n",ans);
return 0;
}