从偏序问题到CDQ分治

偏序关系

设R是集合A上的一个关系,如果R是自反的、反对称的和可传递的,则称R是集合A的偏序关系,并记作 \(\preceq\) ,序偶 \(<A, \preceq >\) 称作偏序集

简单地说,偏序关系就是集合内只有部分元素之间在这个关系下可以比较,全序关系就是集合内任何一对元素在在这个关系下都相互可比较。

通常,k维偏序问题目标在于统计对于特定的一个k元组,与其满足偏序关系的k元组的个数。

一维偏序问题

一维的偏序问题实质上是全序的,我们只需要排序即可。

二维偏序问题

基本的思路是基于执行顺序,也就是基于时间轴的。

预处理时,按照第一维是第一关键字,第二维是第二关键字排序,而后依次处理每个点。

每次查询在当前这个二元组之前,有多少二元组的第二位小于该二元组第二维。为了做到快速查询,可以使用树状数组,对区间 \([1,i)\) 内的二元组第二维进行统计,对于每一个 \(j \in [1, i)\) ,我们以下标为 \(j\) 的二元组的第二维为索引,向树状数组的该位置对应的值+1.

预处理时间复杂度 \(O(n log n)\)

单次查询时间复杂度 \(O(log n)\)

三维偏序问题

三维偏序问题一般采用 CDQ 分治解决。

首先对全部元素按照第一维升序排序。 每一层 CDQ 中,我们首先递归处理左右区间,然后统计左区间对右区间的贡献(右区间对左区间无贡献,因为右区间的元素的第一维均大于左区间的元素第一维),然后将左右区间排序(按照第二维大小升序排序)。

注意到我们是首先递归左右区间,因此当我们开始处理当前区间中左区间对右区间的贡献时,左右区间均已按照第二维大小升序排列,这样我们枚举右区间的每一个元素,统计左区间中有多少数小于它,使用的方法和树状数组求解二维偏序问题相同。

----- 本文结束 感谢阅读 -----
0%