题意:
n个电台,每个电台有三个属性xi, ri, fi。分别代表电台的坐标,电台的播报范围,以及播报的频率。
对于一对电台i, j,若min(ri, rj) >= |xi - xj|,那么他们彼此可达。
对于一对电台i, j,他们彼此可达,且当i < j, 若|fi - fj| <= k, 则这一对为关系为bad。
现在给出n个电台的信息,以及k的大小,问bad对的数目。
不存在不同的电台占据同一个位置的数据。
1 <= n <= 1e5, 0 <= k <= 10,1 <= xi,ri <= 1e9, 1 <= fi <= 1e4。
分析:
我们按照r从大到小排序,那么限制条件就变成了对于一个i,找它前面出现的点j的个数,满足xi-ri<=xj<=xi+ri且fi-k<=fj<=fi+k
也就是求平面上矩形区域内点的个数,这明显就是个cdq分治处理三维偏序
这里求矩形区域内的个数就是相当于四个矩形加加减减
对于每个点拆成5个点,分别是一个插入点(flag=0),四个询问点(flag=1或-1)
cdq分治时候,只有flag=0的点才能更新树状数组,只有flag=1或-1的点才能从树状数组中get到答案
还有一点要注意,要注意多关键字排序时候的顺序
对于一组点的5个分点,flag=0的点一定要放到最后面,因为如果放前面,可能这个点对自身的询问造成贡献
时间复杂度O(nlog^2n)