cdq分治

问题引入

陌上花开1

若干个元素有三个属性，问多少对数对满足 $a_i\leq a_j , b_i\leq b_j , c_i\leq c_j$

分析

如此类问题可以视为一个多维偏序问题，偏序即满足自反性，反对称性，传递性。画成拓扑图则可被视为一张DAG。

考虑这个问题的简单版本，如果只有一个属性，可以容易得到；如果有两个属性，常见的解决方案是对其中一维排序后，树状数组维护前缀，按照某一位以每个元素log的复杂度顺序处理。

在维度更高的情况下，cdq分治是简化问题的一个有效手段。

cdq分治的核心思想即以一个log为代价，降低此类多维偏序一个维度。

预备知识

偏序和全序

偏序即满足：自反性，反对称性，传递性的二元关系。
全序即满足：完全性，反对称性，传递性的二元关系。
两者唯一的区别是第一个性质，但是不难发现，自反性即 $\forall x\ \ s.t. \ \ xRx$
完全性即 $\forall x,y\ \ s.t. \ \ xRy$
即偏序只要自己和自己可比即可，全序则是集合内任意两个元素可比。

像我们处理了如例题陌上花开1的多属性比较关系，往往是偏序的，因为可能出现 的情况，两者不可比。而自然数集上的大小关系往往可以被视为全序关系，因为任意两个自然数都可比。

引申一点，在全序关系上我们引入良序的定义：若一个全序集上任意一个非空子集S都有最小元，则称其为良序。

逆序对

求逆序对个数事实上可以被视为一个二位偏序的统计问题。对于序列A上每一个元素 都有两个属性，位置 和大小，把他们全部揪出来可以形成一个偏序集。那么逆序对实质就是要求集合内所有满足如下关系的对的数量: $i<j\ ,\ a_i>a_j$ 也即可比的元素对个数。

两种常见的计算方案如下: 从后往前求维护树状数组求解2，或者归并排序3。

后面我们会讲到，归并排序实质上就是cdq分治在二维偏序上的一种应用。而在更高维的三位偏序上，常常采用cdq分治+树状数组的解法。

CDQ分治

在这里我们忽略一维情形，因为cdq分治的思想就是降维，一维无维可降故忽略。

二维偏序计数

以逆序对问题为例，假定这里读者已经完全掌握了归并排序求逆序对3的算法，我们将在此基础上展开讨论。

问题建模

要统计数对个数，一种不重复不遗漏的方案是穷举数对中的一个元素，判断另一个元素有几种合法。我们不妨假设要统计数对 的个数，那么对于元素 ，我们要找出所有和他可比的元素。

在这里要特别明确一点，本问题中讨论的偏序，指的是各个元素分别满足某种全序关系(在只出现的元素集上满足良序关系)的偏序。比如例题陌上花开1中，各个属性都是正整数，各个属性内部为全序，可排序。

那么 已经确定，我们归并排序对问题进行分治，那么这个 要么和 分在同一组中，要么分在另一组中。在常见的分治问题中，往往只需要处理分在同一种中的情况，cdq分治的特性就是将跨组的影响也计算出来，从而将分治的思想引入到偏序计数的问题中。

此时我们在用数据结构保存偏序集中每个元素时，除了要保存元素本身的属性外，还要保存和该元素有关的有序对的数量。在完成算法后，将他们全部取出来求和就是总对数。

以逆序对问题为例

我们把整个逆序对的元素抽出来，得到一个二维的偏序集，在几何上可以表示为平面上的一堆点。

此时我们使用分治思想，把他们从中间切开，得到左右两部分，如棕色图所示，可以递归处理。我们不妨假设我们此时考虑某个元素 ，那么我们实质上要考虑的是有多少 满足 且 。肉眼观察可得有两个，分别是 和 。

此时 的贡献在分治处理右半边的时候可以得到，所有放心递归即可。而 的贡献还在左半侧，所以需要单独处理。如何处理呢？cdq分治在这里采用的策略就是先排序，后归并。

在两侧分别对元素值排序后，实质上我们要统计跨界贡献的就是粉色区域内元素的个数。这个可以很容易在归并排序时做到。

for(i=l,j=m+1;j<=r;++j){
        while(a[i].y<=a[j].y&&i<=m){
            add(a[i].z);
            ++i;
        }
        a[j].ans+=ask(a[j].z);
    }

在这个过程中，因为在当前排序的这一元素上是全序的，所以可以排序后归并遍历快速得到结果。我们会发现cdq分治带来了两个log，在分治时带来一个log，在统计跨界元素个数时因为要排序又带来一个log。但是因为这两个log时平行的，所以只需要一个log。而在归并排序求逆序对个数这一特殊问题时，因为归并排序本身可以得到子问题的有序形式，所以在实际操作的时候可以免去排序这一步。但是在cdq分治这一算法框架中排序这一步是必要的。在文章最后总结时我还会给出一个完整的框架，但是到目前为止我们应该已经初窥了cdq分治的奇妙而精巧的转化思想。

更暴力的解法

不难发现其实本问题可以转化为一个平面上若干个区域内点计数的问题。一个更加暴力的做法是二维线段树或者树套树维护区间和，暴力查询即可，复杂度

三维偏序计数

本部分内容以例题陌上花开1为例。

问题建模

先考虑我们的老朋友数形结合，不难发现三位偏序可以把他看成一个立体空间里点计数的问题。暴力做法不难想到，可以三维8叉树暴力求解，或者树套树套树把低维数据结构套成高维的。编程复杂度巨大，显然超出一个智力中等水平的大学生的能力范围。

但是因为我们有了cdq分治这一有利武器，我们可以考虑将问题降维。我们对数组进行如下三步操作：

Step1：按某一维排序
Step2：分治解决子问题
Step3：解决跨界问题，累计贡献

这也是cdq分治的基本框架。我们可以看到，在离线处理答案的时候，是以贡献累计的方式累加到答案上去的，所以这对问题有一个要求：可独立的叠加和累计。不难发现，计数问题是满足这个条件的，在每个点之间可以互相独立的累计到一起。

算法流程

首先按照a轴从小到大排序，这一就得到了一个类似于逆序对的形式：一维有序，另外两维度乱七八糟。现在我们考虑每一个元素作为右元形成的数对，显然只有他左边的点才可能产生贡献，如此我们我们只要统计两部分内容：和他分在一组的和在他左边组的。

和他一组的很好处理，直接递归求解即可。
和他不一组的则需要另行处理，这是整个cdq分治中最需要动脑子的部分。

那么怎么处理呢？一个平凡的想法是直接把左半部用二维线段树/树套数维护，右半部分查询。或者各自排序再归并，这样保证第一维有序(因为跨过中线，所以就算重排之后a仍然有序)。并且归并第二维也有序，此时直接使用树状数组维护前缀即可。

此处给出例题陌上花开1的AC代码，结合代码进一步讲解。

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

const int maxn=1e5+5;

struct node{
    int x,y,z,w,ans;
}a[maxn],b[maxn];

int ans[maxn];
int n,k,nn;
map<node,int> mp;

bool cmpx(node a,node b){
    if(a.x==b.x&&a.y==b.y)return a.z<b.z;
    if(a.x==b.x)return a.y<b.y;
    return a.x<b.x;
}

bool cmpy(node a,node b){
    return a.y==b.y?(a.z<b.z):(a.y<b.y);
}

struct FWT{
    const static int N=maxn<<1;
    int a[N];
    void add(int x,int d){
        while(x<N){
            a[x]+=d;
            x+=x&(-x);
        }
    }
    int ask(int x){
        int res=0;
        while(x){
            res+=a[x];
            x-=x&(-x);
        }
        return res;
    }
}fwt;

void cdq(int l,int r){
    if(l==r)return;
    int m=(l+r)>>1;
    cdq(l,m);
    cdq(m+1,r);
    sort(a+l,a+m+1,cmpy);
    sort(a+m+1,a+r+1,cmpy);
    int i,j;
    for(i=l,j=m+1;j<=r;++j){
        while(a[i].y<=a[j].y&&i<=m){
            fwt.add(a[i].z,a[i].w);
            ++i;
        }
        a[j].ans+=fwt.ask(a[j].z);
    }
    for(j=l;j<i;++j)fwt.add(a[j].z,-a[j].w);
}

int main(){
    ios::sync_with_stdio(0);
    cin>>n>>k;
    for(int i=0;i<n;++i){
        cin>>b[i].x>>b[i].y>>b[i].z;
    }
    sort(b,b+n,cmpx);
    for(int i=0,c=0;i<n;++i){
        ++c;
        if(b[i].x!=b[i+1].x||b[i].y!=b[i+1].y||b[i].z!=b[i+1].z){
            a[nn]=b[i];
            a[nn].w=c;
            ++nn;
            c=0;
        }
    }
    cdq(0,nn-1);
    for(int i=0;i<nn;++i){
        ans[a[i].ans+a[i].w-1]+=a[i].w;
    }
    for(int i=0;i<n;++i){
        cout<<ans[i]<<endl;
    }
}

主函数内的内容是一些去重的预处理操作，注意cdq分治无法处理有重复元素的问题，原因是在进行不当的划分之后可能漏判一些情况。限于篇幅此处不表，读者可以自行在低维情况下手玩验证。在一般的套路中，其他的操作可视题目情况而定，但是对第一维排序必不可少即可，即Step1。

for(int i=0;i<n;++i){
    cin>>b[i].x>>b[i].y>>b[i].z;
}
sort(b,b+n,cmpx);

排序后，则可调用cdq分治，核心代码如下：

void cdq(int l,int r){
    if(l==r)return;
    int m=(l+r)>>1;
    cdq(l,m);
    cdq(m+1,r);
    sort(a+l,a+m+1,cmpy);
    sort(a+m+1,a+r+1,cmpy);
    int i,j;
    for(i=l,j=m+1;j<=r;++j){
        while(a[i].y<=a[j].y&&i<=m){
            fwt.add(a[i].z,a[i].w);
            ++i;
        }
        a[j].ans+=fwt.ask(a[j].z);
    }
    for(j=l;j<i;++j)fwt.add(a[j].z,-a[j].w);
}

其中，若某一时刻当前区间大小为1(代码中均采用闭区间)，那么该空间内部不会产生任何贡献，可以直接return，此为递归的终止边界。由此可见cdq分治是有穷的。

若区间大小不为1，那么必定可以得到两个子问题，直接分治解决即可，此为Step2。

其后则要对跨界内容进行处理，即Step3，首先分别排序，这样在归并时得到的序列在第二维上就是有序的了。此时我们要计算左半边对右半边的贡献，那么第一维度左边总是在右边的左边，分别排序后不会影响此性质，第一维度也相对有序。

这样看似是降低了两个维度，但是其实只降低了一个。我们考虑用树状数组求逆序对的过程，事实上我们是将下标视为时间维度，按照时间顺序维护树状数组和统计答案。对于其他任意的二维偏序问题，我们常见的处理方法是先对其中一维排序，视为时间序，再用树状数组等数据结构维护时间前缀上的信息。而在cdq分治中，我们在分治时保证第一维有序，分别排序保证第二维有序，于是我们按照第二维归并处理时，实质上是按照第二维时间序在操作。通过把点分为两部分，计算左边对右边的贡献，实质上我们在忽略第一维度的情况下得到了第二维的时间序，所以对原问题来说是降低了一个维度。

cdq分治的极限

各个属性分别满足全序关系的偏序二元对计数问题，我们上面对cdq分治使用的限制条件似乎太过于苛刻了，是否能够将其拓展，使得更多的问题可以由cdq分治解决呢？

答案是肯定的。不难发现，cdq分治是一种时间换维度的算法，而其中必须要满足全序关系的属性其实有且仅有Step1中被排序的一维。换一个角度看，其实cdq分治做的事情是：用一个log的复杂度，将原问题中的时间维消除，转化为一组元素对另一组元素的贡献计数问题。在此基础上，我们再进行归并排序，实质上是再构造一个时间维，而这并不是不可或缺的。

比如在陌上花开1中，我们完全可以先使用cdq分治之后再对左半部分用二维线段树建树，再用右半部分的每个数对二位线段树逐个查询区间和累计答案。这样实质上我们做到了将8叉树(三维线段树)降维到了4叉树(二维线段树)。

而对于其他的问题，其实可以考虑很多种不同的算法和数据结构来维护跨区间的贡献，而他们很多是不要求满足偏序/全序关系的，甚至不需要有“序”这个概念，比如有多少对gcd不为1之类。这和很多人提到的cdq分治是在“序”上乱搞的概念不太一样。cdq分治不在序上乱搞，而是消灭一组全序属性。

拓展问题

偏序+全序

考虑如下问题，给出若干个元素，每个元素有属性a,b，问有多少对数对 满足 $a_i\leq a_j 且 b_i|b_j$
其中 表示 是 的因子。

解决方案比较容易想到，先按照a排序，然后cdq分治。接下来问题就变成如下问题：给定一个集合，里面若干个元素，每个元素有一个属性 , 若干次查询，问集合中有多少个数是查询数的因子。

暴力一点就左边维护一个hash，右边枚举因子。如果有现成的数据结构和算法也可以很轻松套上去。

求和+全序

考虑如下问题，给出若干个元素，每个元素有属性a,b，问有多少对数对 满足 $a_i\leq a_j 且 b_i+b_j=K$

解决方案比较容易想到，先按照a排序，然后cdq分治。接下来问题就变成如下问题：给定一个集合，里面若干个元素，每个元素有一个属性 , 若干次查询，查询数为 ，问集合中有多少元素等于 。

这样问题就变得非常简单，hash即可。

应用场景

根据上述两个随手捏的例题，不难得出使用cdq分治的情景：

• 求解合法二元对个数(如果是更多元的话分治时需要更多分类讨论，并不实用，故此处认定只适合二元情形)
• 有至少一个属性的排序条件为全序关系，或者分段全序(只要满足能够分治且左右两边单向有序即可)
• 维度较高，简单的数据结构难以维护高维信息

总结

cdq分治的思想

把高维偏序问题降低一个维度，以一个log为代价。

cdq分治的套路

先对一个维度排序，接下来分治处理贡献：分治解决同块贡献；完事后因为第一维度在分治之后已经保证有序，接下来就变成在左边上统计右边的情况。如果是三维的，那么直接排序+归并即可再减掉一维，这一就减掉了两维，非常轻松的解决掉3维偏序的情况。如果是4维，可以无脑再套一个树套树。据说还可以cdq套cdq，但是目前还没有想明白怎么搞，先咕。