CDQ分治学习笔记

更好的阅读体验： ljc2002073's blogs

【详细代码见ljc的博客，这里就不贴啦】

数据结构中的一块内容：CDQ分治算法。

这种离线分治算法被算法界称为"**cdq分治**" 我们知道，一个动态的问题一定是由"更改""查询"操作构成的，显然，有些“更改”会改变"查询的结果"，而有些不能。 如果我们合理安排一个次序，把每一个查询分成几个部分，分别计算值，最后合起来就是原来询问的值。 离线算法和在线算法的概念不用过多解释. ### **接下来通过几个例题将基本的$CDQ$分治算法解释明白.** ## A. 从逆序对开始的二维偏序问题 下面将给出逆序对的题目： ------------ 例题 A1： 逆序对的定义是对于序列a[],取第$i$个元素和第$j$个元素,满足$i <j$且$a[l]>a[r]$，对于这样数对$(l,r)$被称为一对逆序对 求解给定序列a中有多少对逆序对，你需要输出对数. 对于100%的数据 $a \leq 5 \times 10^5

我们都知道可以用树状数组和归并排序两种方法做，这里我们只讲归并排序(默认树状数组大家都会)

不断把[l,r]细分，每次取mid=\frac{l+r}{2} 然后指针i和j分别指向区间[l,mid]和[mid+1,r]并且单调

先确定i不动，把j右移归并，如果满足a[i]>a[j]记录逆序对个数加mid-i+1意味着a[i],i \in [i,mid]和 a[j]互成逆序对，跳出把i移动

依次，直到完成所有区间，复杂度O(n log_2 n)

核心代码Code：

void sort(int l,int r,int mid)
{
    for (int i=l;i<=mid;i++) a[i]=t[i];
    for (int i=mid+1;i<=r;i++) b[i]=t[i];
    int i=l,j=mid+1,k=l;
    while (i<=mid&&j<=r) {
        if (a[i]<=b[j]) c[k++]=a[i++];
        else c[k++]=b[j++],ans+=mid-i+1;
        //当前的b中当前的j和剩下的ai都是一对逆序对 
    }
    while (i<=mid) c[k++]=a[i++];
    while (j<=r) c[k++]=b[j++];
    for (int i=l;i<=r;i++) t[i]=c[i]; 
}
void merge_sort(int l,int r)
{
    int mid=(l+r)/2;
    if (l<mid) merge_sort(l,mid);
    if (r>mid) merge_sort(mid+1,r);
    sort(l,r,mid); 
}

然后这个问题反映什么实质呢，显然我们可以造出2个维度记偏序(t,i)表示时间为t，位置为i

由于我们按照顺序读入，那么默认第一维偏序是有序的，便忽略了这一维度的记录和排序。

换句话说，在归并的时候虽然左区间和右区间里面值不一定相等，但是左区间的所有元素都排在右区间前面

这是基于第一维偏序是有序的情况下进行的.

然而，对于有些情况，第一维偏序的记录和第一维偏序的排序是不可省略的！

下面给出树状数组的模板题，请用CDQ分治（二维偏序）方法AC本题。

例题A2：维护含n个元素的原始序列a[]，有m个操作,2种不同格式：

1 x k 含义：将第x个数加上k

2 x y 含义：输出区间[x,y]内每个数的和

请正确输出每一个2操作的答案，不强制在线。

对于100%的数据 n,m \leq 5 \times 10^5

Solution：把原始序列读入操作变化成插入第i个位置上加上对应的值，参与cdq分治。

首先把查询拆成两个,减去x-1的前缀和和加上y的前缀和（前缀和优化的思路）

每一个询问记录4个量type[类型],x,y(两个参数),idx（若是询问操作表示是第几个询问）

时间作为默认有序的第一维度，用cdq分治维护第二维度位置（归并按照位置归并）。

仅考虑左边的更改对右边查询的影响，更改只有在左侧有影响，当 tl\geq mid 且a[tl].x<a[tr].x 同时满足的情况下，将前缀和sum+=y[加上的值]

这个时候第一维已经默认有序了，也就是说明乱序下左边操作的时间一定在右边操作之前，所以更改对右边有影响，影响是sum

同时对于位置归并cdq，虽然打乱了这一部分时间，但是对于大块时间的划分是没有影响的.

我们更新的是处理过[mid,r]这一段的答案，如果tr>r不在这个区间内，需要舍去

一种通俗的写法是，将tr>r的情况归属到更改的影响中，这样不会对答案造成干扰.

这是核心代码Code：

void cdq(int l,int r)
{
    if (l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid); cdq(mid+1,r);
    int tl=l,tr=mid+1,sum=0;
    fp(i,l,r) {
        if ((tl<=mid&&a[tl]<a[tr])||tr>r) {
            if (a[tl].type==1) sum+=a[tl].y;
            b[i]=a[tl++];
        } else {
            if (a[tr].type==2) ans[a[tr].idx]-=sum; //2代表-sum{l-1}
            if (a[tr].type==3) ans[a[tr].idx]+=sum;//3代表+sum{r}
            b[i]=a[tr++];
        }
    }
    fp(i,l,r) a[i]=b[i];
}

B. 从二维偏序到三维偏序

一维偏序直接sort

二维偏序第1维sort，第2维cdq分治

三维偏序第1维sort，第2维cdq分治，第3维 数据结构

下面给出三维偏序问题：

给定n个有序三元组(a,b,c)，求对于每个3元组(a,b,c)，

有多少个3元组(a_i,b_i,c_i)满足a_i<a且b_i<b且c_i<c.

仿造上面的写法，对第1维a排序，对第2维b归并cdq，

对于第3维c,我们借助权值树状数组， 每次从左边取出三元组(a,b,c)，根据c值在树状数组中进行修改

从右边的序列中取出三元组(a,b,c)时，在树状数组中查询c值小于(a,b,c)的三元组的个数

注意，每次使用完树状数组要把树状数组清零

下面我们给出一个例题，即陌上花开是luogu三维偏序的模板题

例题B1：陌上花开

有n个元素，每个元素有a_i,b_i,c_i三种属性，定义两个元素大小比较为：

若a_i>a_j且b_i>b_j且c_i>c_j简记为i>j，对于不同元素i，需要统计他比多少元素大，

就是元素i的权f(i)，问对于 d\in [0,n-1] 有多少x\in [1,n] 的取值f(x)=d 输出一个数组表示 d=0,1,2,3...n-1时的答案

对于100%的数据 n \leq 10^5

Solution：

首先是可能存在一些相同的元素的，我们定义元素相同为三种属性均相同。这样较为难处理，第一步我们把他们合并起来了。

于是对于每种元素，记录了四个参数a,b,c,w,id表示三种属性、数量、他的标号。

然后对其第1维a进行排序[其实在去重这一步我们事实上已经完成了这一操作]

然后对于第2维b进行cdq分治，在每一处分治的时候树状数组维护插入和查询，每次需要插入的时候在值域树状数组维护数量的前缀和，

插入的时候，对于z处加上数量w,update(z,w)，查询的时候，在ans[id]+=query(z)。

然后就可以统计出对于每一朵花有多少元素比他大了，记录在ans[id]中，id \in [1,n]

输出的时候还需要统计，别忘了加上自己的那份w和减去自己的1！

核心代码Code:

/去重操作
    sort(t+1,t+1+n,cmp1);
    int i=1,j; tot=0;
    while (i<=n){
        j=i+1;
        while (j<=n&&same(t[i],t[j])) j++;
        j--;
        a[++tot]=t[i]; a[tot].w=(j-i+1); a[tot].id=tot;
        i=j+1;
    }
void cdq(int l,int r) //cdq分治
{
    if (l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid);cdq(mid+1,r);
    dfn++; //便于去重
    int t1=l,t2=mid+1;
    for (int i=l;i<=r;i++) {
        if ((t1<=mid&&a[t1].y<=a[t2].y)||t2>r) {
            update(a[t1].z,a[t1].w);
            b[i]=a[t1++];
        } else {
            ans[a[t2].id]+=query(a[t2].z);
            b[i]=a[t2++];
        }
    }
    for (int i=l;i<=r;i++) a[i]=b[i];
}

C. 从三维偏序到三维偏序的应用

这一专题我们安排了两道例题，请按照三维偏序的思想和方法，尝试解决。

练习C1：[CQOI2011]动态逆序对

练习C2：[Violet]天使玩偶/SJY摆棋子

下面对于每一个例题讲解：

例题C1：逆序对的定义：对于序列a[],取第i个元素和第j个元素,满足i <j且a[l]>a[r]，对于这样数对(l,r)被称为一对逆序对 ，

给出一个[1,n]的排列，按照顺序依次删除m个数，询问当前逆序对数量.不强制在线。

对于100%的数据 ：N\leq 10^5,M\leq 5\times 10^4

Solution:可以把每次的答案分成两个部分：原先存在的逆序对+加入这个数新产生的逆序对，

那么每次只要算出当前新产生的逆序对，最后算一遍前缀和即可。

考虑逆序对产生方式： 1.位置靠前且值比它大的，2.位置靠后且比它小的。

这个问题在于有插入操作，和删除操作，比较难过

对于逆序对的产生是插入比他前的满足1 or 2两个条件的元素

对于逆序对的删除是删除时间比他后面的，满足1 or 2两个条件的元素。

显然对于把时间作为第1维进行排序是不合适的(时间在前和后有不同的影响)，所以我们考虑把操作的位置作为第1维，进行排序

对于时间这1维度作为第2维度CDQ分治，

设当前删除了第i个元素，那么在[1,i]中比它大的都要减去，在[i+1,N]中比他小的都要减去。

正序循环的时候默认先加入树状数组的元素的位置都是在询问元素的前面的，所以要减去的是比询问元素大的那一个部分 [i+1,n]

倒序循环的时候默认先加入树状数组的元素的位置都是在询问元素后面的，所以要减去的是比询问元素小的那个部分[1,n-1]

同样的考虑影响还是处于左边时间修改对处于右边时间的查询造成的影响，注意同步清空树状数组.

例题C2：定义两点距离为麦哈顿距离 Dist(A,B) = |A_x - B_x|+|A_y-B_y|

给出初始n个点的坐标 (x_i,y_i) 有m个操作，

1 x y : 表示在(x,y)处新增1个点

2 x y : 表示询问所以存在的点到点(x,y)最小距离

对于100%的数据 n,m \leq 3 \times 10^5 , x_i,y_i \leq 10^6

Solution：

如果点都在询问点的左下方就好了...（这样绝对值就直接消掉了）

However，人家有4个方向，怎么办，考虑到对称我们可以把所有点都做一次变换，称为对称

怎么个对称法呢，关于x轴对称，关于y轴对称，关于原点对称，对称的意思是所有点的坐标发生变换，

以原点对称为例，原来A在B的左下方，对称后A就在B的右上方了，那么类似于 按原点B对称的意思。

按照x轴对称，按照y轴对称同理。

接下来我们只讨论点在点左下方的情况（变换以后跑4遍不就好了！）

计算lx，ly表示x，y坐标最大取值+1

把Dist绝对值打开得 Dist(A,B) = |A_x - B_x|+|A_y-B_y| =A_x+A_y-(B_x+B_y)

对于给定的A点，A_x+A_y一定，当 Dist(A,B)取到最小值的时候B_x+B_y最大

所以用树状数组维护前缀最大值就行。

这里时间t是默认有序的作为第1维，然后cdq分治第2维x，然后用树状数组维护一个y,前缀最大值

当分治求答案的时候左边时间早于右边，左边影响右边，第2维x经过归并左边小于右边，所以为了保证在左下方还需y左边小于右边

所以求的时候求y的这个点前缀最大值即可.（注意如果没有请不要更新为0）

D.四维偏序(CDQ套CDQ)

下面给出四维偏序的模板题：

例题D1：现在有n个三元组(a_i,b_i,c_i) 求有多少组三元组对(i,j)满足 i<j, a_i<a_j , b_i<b_j , c_i<c_j

你的程序必须输出三元组对总对数。 数据保证a,b,c三个数组都是[1,n]排列。

对于100%的数据 n \leq 5 \times 10^4

(数据来自ljc20020730)

solution：我们类比二维偏序、三维偏序的方法考虑四维偏序的求解方法

首先把第1维排序，显然是位置（这里没记，原数组就是按照顺序位置排布的）

然后对第2维进行CDQ分治，但是剩下还有2维怎么办。

我们不妨再对第3维进行CDQ分治，然后第4维使用数据结构统计。

显然当我们归并第2维以后数组变成了按照第2维度排序的有序数组但是第1维时间是杂乱无章的。

然而我们只关心第1维是在左边还是右边，并不关心具体值，于是我们可以用Left和Right来标记a值（part）

既然b已经有序在CDQ套的cdq下面（不妨把正式求解的分治算法称之为CDQ，CDQ中套如的子分治算法叫做cdq）

把原来CDQ中第2、3、4维换成之前做过三维偏序的1、2、3维就行了（同时注意更新时判断，对于CDQ是不是完成了左边更改对右边查询的影响）

cdq完成的目的是：在CDQ后前面部分对后面部分的影响。

step 1： 对第一维进行排序。

step 2：对第1维重新标号（left或right），然后对第2维分治，递归解决子问题，按照第2维的顺序合并。此时只是单纯的合并，并不进行统计。

step 3： 把合并后的序列复制一份，在复制的那一份中进行cdq分治。（这时第2维默认有序）即对第3维分治，递归解决子问题，按照第3维的顺序合并。合并过程中用树状数组维护第4维的信息。

void cdq(int l,int r) //对于2,3,4维度重新cdq分治 
{

    if (l==r) return;
    int mid=(l+r)>>1;
    cdq(l,mid); cdq(mid+1,r);
    int i=l,j=mid+1,k=l;
    while (i<=mid&&j<=r) {
        if (t1[i].b<t1[j].b) { //按照第3维归并 
            if (t1[i].part==Left) update(t1[i].c); //更新的前提条件第1维在左边，影响第1维的右边 
            t2[k++]=t1[i++];
        } else {
            if (t1[j].part==Right) ans+=query(t1[j].c); //答案累加的前提条件是第1维在右边受到第1维左边影响 
            t2[k++]=t1[j++];
        }
    }
    while (i<=mid) t2[k++]=t1[i++];
    while (j<=r) {
        if (t1[j].part==Right) ans+=query(t1[j].c);
        t2[k++]=t1[j++];
    }
    fp(i,l,r) {
        if (t2[i].part==Left) clear(t2[i].c);//清空树状数组 
        t1[i]=t2[i]; 
    }
}
void CDQ(int l,int r) //注意此时已经默认第1维有序我们不必记录 
{

    if (l==r) return;
    int mid=(l+r)>>1;
    CDQ(l,mid); CDQ(mid+1,r);
    int i=l,j=mid+1,k=l;
    while (i<=mid&&j<=r) {
        if (a[i].a<a[j].a) {
            a[i].part=Left; //对于第2维度a归并，并记录第1维是左边(left)还是右边(right) 
            t1[k++]=a[i++];
        } else {
            a[j].part=Right;
            t1[k++]=a[j++];
        }
    }
    while (i<=mid) a[i].part=Left,t1[k++]=a[i++];
    while (j<=r)   a[j].part=Right,t1[k++]=a[j++];
    fp(i,l,r) a[i]=t1[i]; //t1就是复制过去的数组 
    cdq(l,r);
}

E. CDQ系列问题时间复杂度分析：

给出 Master 定理：

定义T(n)为算法时间复杂度，对于规模为n的问题可以分为a个规模为\frac{n}{b}的子问题，

在在每一个子问题的解决中，其他运算的时间复杂度是f(n)，c是一个由a,b决定的数

定义T(n)=aT(\frac{n}{b})+f(n) ， 令crit=log_b \ a

f(n)=O(n^c)$且$c<crit$时 ， $T(n)=O(n^{crit}) \exists k \geq 0$使得$f(n)=O(n^{crit} {log_2}^k n)$那么$T(n)=O(n^{crit}{log_2}^{k+1} n)

对于2维偏序问题时间复杂度是O(n log_2 n) 如归并排序求逆序对

对于3维偏序问题由于加上树状数组的维护时间复杂度是O(n {log_2}^2 n) 如陌上花开

对于4维偏序的问题由于CDQ套CDQ还加上了树状数组维护复杂度是O(n {log_2}^3 n) 如偏序[HZOI2016]

对于一般k维偏序问题，利用CDQ套...求解是时间复杂度是O(n {log_2}^{k-1} n)

上述结论可由Master定理求证。

尾声：　　

到此处为止，CDQ分治的算法介绍已经基本完毕。

已经有了离线处理动态问题的思路：把动态问题按照时间、位置分治进行cdq优化

使时间复杂度降低,并且不需要高级数据结构如K-D Tree在线维护，简便快速解决问题。

每降低一维的时间复杂度只需要用log_n的复杂度。

当然，只掌握这些内容是远远不够的，需要强调cdq算法的限制：

1、必须离线操作

2、对区间更新问题解决有困难

3、代码调试细节较多，请积极对拍验证

(The End)