首页 > 代码库 > 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分治求三维偏序)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。