cdq分治解决三维偏序

问题背景

在三维坐标系中有n个点,坐标为(xi,yi,zi). 定义一个点A比一个点B小,当且仅当xA<=xB,yA<=yB,zA<=zB。问对于每个点,有多少个点比它小。(n小于等于e5)

其实就是离散数学里的偏序的概念啦,只不过是到了三维。回顾一下偏序的概念:

偏序关系:自反,反对称且传递,相当于<

然后先考虑一下二维偏序吧。可以用最长上升子序列LIS来做,然后我们今天讨论一种特殊分治的做法,这种算法是由08年集训队的陈丹琦提出来的,因此叫cdq分治。

主要思想就是先按照第一维排序。然后遍历每一个点,此时我们要统计的就是前面的点中比这个点的y坐标要小的点的个数。我们用一个树状数组来维护y坐标这个信息,于是就只要得到getsum(y)就行了。

三维的CDQ分治呢,做法如下:

第一维排序,第二维CDQ分治,第三维树状数组。

第一维比如先按照x坐标排序。在第二维的CDQ分治时,我们对每一个自区间,先按照y排序,计算左边对右边的影响的时候:

  1. 左边的x都小于右边

  2. 在每一边y也是依次递增的

  3. 我们只要扫描右边,把左边y小于等于当前的y坐标的z坐标更新到树状数组,统计目前树状数组z坐标小于自己的就是偏序<的点的个数。

复杂度分析

根据主定理:

T(n)=2T(n2)+O(kn)=O(knlogn)T(n)=2T(n2)+O(kn)=O(knlogn)

T(n)=2T(n2)+O(knlogn)=O(knlog^2 n)

例题

BZOJ 3262 陌上花开

牛客网的一套题

后面这个题虽然是个裸三维偏序,不过也可以转化成三个二维偏序。

另附一个BZOJ3262的别人的代码,可做模板。

总结

从二维偏序出发,了解了三维偏序的CDQ分治做法。

在这类问题中通常将时间(操作序列)作为第一维,剩下的二维问题使用CDQCDQ分治和数据结构。

这种问题也可以用树套树做,据说很烦,树状数组套个什么Treap啥的,总之比这个CDQ要难写很多。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注