这篇文章上次修改于 282 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

算法学习笔记(12):CDQ分治

CDQ分治是一种思想，将复杂问题转化为简单问题。多维问题转为降维问题。

偏序问题

以一维二维三维偏序作为例子，可以体现CDQ分治的降维思想。

一维偏序

给n个数x1-n，求出每个元素xi 满足 aj < xi的个数

可以排序轻松得出。

二维偏序

给n个二元组(x1, y1) - (xn, yn)，求出每个元素(xi, yi)满足 (xj, yj) < (xi, yi)的个数

二维问题相对复杂，但依旧可以通过转化思想。降维是第一想法，如果我们将所有的二元组都根据x进行排序，那么在后面的二元组就的x就必定大于前面的，此时得到的y序列，如果有后面的y比前面的y小，就可以说明有这样的一对。

此时一个二元组的偏序问题就变成了一个一维的类似于逆序对的问题。

我们利用一次排序，降低了维度，减少了一个限制条件要求（关于x的），或者说把x的大小转移到了y的顺序上。

逆序对可以使用树状数组来解决。

三维偏序

给n个三元组(x1, y1, z1) - (xn, yn, zn)，求出每个元素(xi, yi, zi)满足 (xj, yj, zj) < (xi, yi, zi)的个数

此处就是CDQ分治的思想体现，利用分治降维。

说到分治，我们先想到最简单的分治体现：归并排序。

归并排序的分治是为了降低排序的难度，从n个变成n/2个直到变成2个或者1个。

再利用了并过程中，只需要不断从两边取出，大大降低比较次数。

这里的分治重于：将复杂简单化，减少要考虑的事情。

回到三维偏序，如果从降维角度分治，我们就要保证，分治可以重于降低题目复杂点，而CDQ分治就是利用分治减去维度。

假如我们首先减去x维度，先对x排序，再根据排序后的顺序，从中间拆开，分成两组，此时我们能保证，后面那一组的x一定会比前面那一组的x大，此时无论后面一组怎么变化顺序，其中的元素x都是比第一组大，此时只需要考虑二维上，后面这一组比前面组的二维偏序数量贡献即可。（对每组的y进行排序，只计算后面组和前面组之间的贡献）

此时两组之间的所有情况都被计算，就变成两个子问题了。

不断分割到剩下一两个便可直接得出。

所以CDQ分治重于去除两个组之间的关系（对于答案的影响贡献）（减少限制条件），再分割为子问题。

code:(from oi.wiki)

#include<bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 10;
const int maxK = 2e5 + 10;

int n, k;

struct Element
{
    int a, b, c;
    int cnt;
    int res;

    bool operator!=(Element other)
    {
        if (a != other.a)
            return true;
        if (b != other.b)
            return true;
        if (c != other.c)
            return true;
        return false;
    }
    static bool cmpA(Element x, Element y)
    {
        if (x.a != y.a)
            return x.a < y.a;
        if (x.b != y.b)
            return x.b < y.b;
        return x.c < y.c;
    }

    static bool cmpB(Element x, Element y)
    {
        if (x.b != y.b)
            return x.b < y.b;
        return x.c < y.c;
    }
};

Element arr[maxN];
Element tmp[maxN];
int m, t;
int res[maxN];

struct BinaryIndexedTree
{
    int node[maxK];

    int lowbit(int x) { return x & -x; }

    void Add(int pos, int val)
    {
        while (pos <= k)
        {
            node[pos] += val;
            pos += lowbit(pos);
        }
        return;
    }

    int Ask(int pos)
    {
        int res = 0;
        while (pos)
        {
            res += node[pos];
            pos -= lowbit(pos);
        }
        return res;
    }
} BIT;

void CDQ(int l, int r)
{
    if (l == r)
        return;
    int mid = (l + r) / 2;
    CDQ(l, mid);
    CDQ(mid + 1, r);

    std::sort(tmp + l, tmp + mid + 1, Element::cmpB);
    std::sort(tmp + mid + 1, tmp + r + 1, Element::cmpB);
    
    int i = l;
    int j = mid + 1;
    while (j <= r){
        while (i <= mid && tmp[i].b <= tmp[j].b){
            BIT.Add(tmp[i].c, tmp[i].cnt);
            i++;
        }
        tmp[j].res += BIT.Ask(tmp[j].c);
        j++;
    }
    for (int k = l; k < i; k++)
        BIT.Add(tmp[k].c, -tmp[k].cnt);
    return;
}

int main()
{

    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &arr[i].a, &arr[i].b, &arr[i].c);

    std::sort(arr + 1, arr + n + 1, Element::cmpA);
    for (int i = 1; i <= n; i++)
    {
        t++;
        if (arr[i] != arr[i + 1])
        {
            m++;
            tmp[m].a = arr[i].a;
            tmp[m].b = arr[i].b;
            tmp[m].c = arr[i].c;
            tmp[m].cnt = t;
            t = 0;
        }
    }
    CDQ(1, m);
    for (int i = 1; i <= m; i++)
        res[tmp[i].res + tmp[i].cnt - 1] += tmp[i].cnt;
    for (int i = 0; i < n; i++)
        printf("%d\\n", res[i]);
    return 0;
}

一维DP优化

这是一种特定优化，通常是一维DP并且状态转移方程是O(N)的

通常有这样的状态转移方程

这样的状态转移有什么能优化的地方，例如对于都满足j1 j2 < i，能否减少ai比较的次数，

比如分别是 1 2 3,1 和2 的最大值已经是2，3就没有和1比较的必要性。

再关注这里的转移条件，是(aj < ai, j<i)，这是一个类似于偏序关系的式子。我们可以利用CDQ减去其中的一维，利用分治减去j<i的判断，从而减少比较次数，进行优化。

code:(from internet)

void CDQ(int left, int right)
{
    if (left == right)
    {
        if (left == 1)
            arr[1].dp = 1;
        return;
    }
    int mid = (left + right) / 2;
    CDQ(left, mid);
    sort(arr + mid + 1, arr + right + 1, cmp);
    int maxx = 0;
    for (int j = left, i = mid + 1; i <= right; i++)
    {
        while (j <= mid && arr[i].x >= a[j].x)
            maxx = max(arr[j++].dp, maxx);
        arr[i].dp = max(arr[i].dp, maxx + 1);
    }
    
    sort(arr + mid + 1, arr + right + 1, cmp2); // 原序号排序
    CDQ(mid + 1, right);
    sort(arr + left, arr + right + 1, cmp);
}

Mai Icy