首页 > 代码库 > hdu5618(cdq分治求三维偏序)

hdu5618(cdq分治求三维偏序)

题意:给n(n<=100000)个点,坐标为(xi,yi,zi)(1<=xi,yi,zi<=100000),定义一个点A比一个点B小,当且仅当xA<=xB,yA<=yB,zA<=zB。求对于每个点,有多少个点比它小。

分析:

   首先肯定按照x递增顺序排个序

   接下来就是每次往平面插入一个点,求这个点左下方已经有多少个点,这可以用二维树状数组来搞,但是很明显会爆空间,不可以接受(当然树套树也是不可以的)

   可以考虑对第二维cdq分治

   对于一个区间[l,r],先递归区间[l,mid],再整体考虑[l,mid]对[mid+1,r]的贡献,再递归[mid+1,r]

   重要考虑[l,mid]对[mid+1,r]的贡献

   因为[l,mid]中的x都小于等于[mid+1,r]中的x,那么可以不考虑x了,直接考虑第二维y

   将两个区间分别按照y从小到大排序

   弄两个指针分别从左端开始移动,对于[l,mid]中的y<=[mid+1,r]中的y,那么就把对应的z丢到树状数组中

   那么对于[mid+1,r]中的每个位置,在相应的时间就可以计算[l,mid]中的点对此位置的贡献

   时间复杂度O(nlog^2n)

   一维排序,二维cdq,三维数据结构,考虑左区间的修改对于右区间查询的影响

  

hdu5618(cdq分治求三维偏序)