Cdq分治

Published: by Creative Commons Licence

  • Tags:

CDQ分治

CDQ分治是一种基于分治的解题思路。

假设在三维空间存在点集$P={p_1,p_2,\ldots,p_n}$,对于每个点$p_i=(x_i,y_i,z_i)$,问点集中有多少点落在以$(0,0,0)$与$(x_i,y_i,z_i)$确定的三维矩形中,换言之,有多少点$p_j=(x_j,y_j,z_j)$满足$x_i\leq x_j\land y_i\leq y_j \land z_i\leq z_j$。

最简单的方式是嵌套for循环,时间复杂度为$O(n^2)$。CDQ分治可以以$O(n(\log_2n)^2)$的时间复杂度内解决三维偏序问题。

下面说一下解决的流程。首先我们可以先将点集去重,保证所有顶点都互不重复。之后我们对点集按照$x,y,z$坐标值按照字典序从小到大排序(保证只有左边的点能对右边的点贡献)。之后我们进入分治流程,其中$solve(l,r)$表示计算第$l$到$r$个顶点之间的偏序关系。在完成了$solve(l,m)$和$solve(m+1,r)$后,我们要计算区间$[l,m]$对区间$[m+1,r]$的贡献,由于已知$[l,m]$中的点的$x$值必定小于$[m+1,r]$中的点,因此我们这时候只需要考虑二维偏序的问题。

要解决二维偏序的问题,我们可以对两个区间分别按照y左边进行从小到大排序,之后利用树状数组或线段树记录点数目。这个过程的时间复杂度是$O((r-l+1)\log_2(r-l+1))$。

整体的时间复杂度为$T(n)=2T(\frac{n}{2})+n\log_2n=O(n(log_2n)^2)$。

要解决三维偏序问题,你也可以选择使用线段树套线段树,利用惰性创建结点也可以以$O(n(\log_2n)^2)$的时间复杂度和空间复杂度解决三维偏序问题。但是CDQ分治的时间空间复杂度仅为$O(n)$,要优于线段树套线段树。并且我们还注意到时间复杂度中带有$(\log_2n)^2$,这意味着平衡树的查询更新操作的常数$c$将会变成$c^2$,这时候常数就很重要了,而树状数组的常数是非常小的,比较线段树等其它平衡树优势非常巨大。

void solve(Point[] points, int l, int r)
{
    if(l == r)
    {
        points[l].count += 1;
        return;
    }
    int m = (l + r) / 2;
    solve(points, l, m);
    solve(points, m + 1, r);
    sort(points, l, m);
    sort(points, m + 1, r);
    for(int i = m + 1, j = l; i <= r; i++)
    {
        for(; j <= m && points[j].y <= points[i].y; j++)
        {
            bit.update(points[j].z, 1);
        }
        points[i].count += bit.query(points[i].z);
    }
}

Codeforces 1139F

题目

https://codeforces.com/contest/1139/problem/F

题解

可以先将问题转换到几何上,把盘子和人都抽象为二维平面上的点,可以发现问题实际上是三维偏序问题,cdq分治即可。