codeforces 762E(cdq分治)

题意:

  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)

原文地址:https://www.cnblogs.com/wmrv587/p/6745358.html