【算法笔记】CDQ分治

· · 算法·理论

从归并排序谈起

首先让我们回顾归并排序，主要的思想就是“分而治之”，从而做到 O(n\log n) 的时间复杂度，如图。

在这一过程中，我们可以得到这个数列的逆序对。

如图，在分治出的两个块中，左边块的序号必定小于右边块的序号，所以我们就把逆序对这个二维偏序问题转化成了一个普通的一维偏序问题。

究其原理，实际上就是计算左边块对右边块的贡献，这种就是 CDQ 分治思想的一种体现。

//归并排序求逆序对
void merge(int l,int r){
    if(l==r) return;
    int mid=(l+r)/2;
    merge(l,mid),merge(mid+1,r);
    int len=l,j=l;
    for(int i=mid+1;i<=r;i++){
        while(j<=mid&&a[j]<=a[i]) tmp[len++]=a[j++];
        tmp[len++]=a[i];
        ans+=mid-j+1;//计算左边对右边的贡献
    }
    while(j<=mid) tmp[len++]=a[j++];
    for(int i=l;i<=r;i++) a[i]=tmp[i]; 
}

P1908 逆序对

CDQ 分治与其说是一种算法，不如说是一种思想，其本质就是通过分治，把动态问题转化成离线问题，把高维问题转化成低维问题，把复杂问题转化成简单问题。

本文将介绍 CDQ 分治的几种简单应用，以加强对 CDQ 分治的理解。

偏序问题

如上文所说，CDQ 分治一个主要应用就是“把高维问题转化成低维问题”，也就是偏序问题。

（事实上，前文提到的逆序对问题就是一种二维偏序，即 i<j,a_i>a_j）。

我们暂时不讨论三维偏序以及更高维的偏序问题，先看二位偏序。

以数星星一题为例，大意是对每个 (a,b)，定义其等级为 x\le a,y\le b 的数对 (x,y) 的个数，求每一个等级的数量。

注意到 x\le a,y\le b 就是一个典型的二维偏序。

对于这种问题，我们的一贯思路是从高维向低维转化，首先按照 x 坐标排序，而后问题就转化成了求 i<j,a_i<a_j 的个数，i,j 以排好序，于是直接套用 CDQ 分治即可。

对于更高维度的偏序问题，我们的考虑方式也是尽量消去维度，如三维偏序，就是先排序消去一维，用 CDQ 分治消去一维，剩下的再用数据结构维护（或也可用 CDQ 分治嵌套）。

//二维偏序问题
void merge(int l,int r){
    //核心代码
    if(l==r)return;
    int mid=(l+r)>>1;
    merge(l,mid),merge(mid+1,r);
    int j=l,len=l;
    for(int i=mid+1;i<=r;i++){
        while(j<=mid&&a[i].y>=a[j].y){
            if(a[j].x==a[i].x&&a[j].y==a[i].y) break;
            j++;
        }
        a[i].num+=j-l;
    }
    sort(a+l,a+1+r,cmp);
}

注：这份代码中在 CDQ 分治的最后排序，多了一个 \log 的复杂度，若想去掉，改成归并排序式的合并即可。

对前缀和 CDQ 分治

P5459 回转寿司

题意是求使得 \sum_l^r a_i\in [L,R] 的区间 [l,r] 个数。

考虑前缀和，设 S_i 为 a_i 的前缀和，于是问题转化为：求 L \le S[r]-S[l-1]\le R 的 l,r 个数。

再考虑一个经典的前缀和式的转化，我们求 S[r]-S[l-1]>R 的个数再减去 S[r]-S[l-1] \ge L 的个数。

考虑分治，原序号关系是单调的，另一组约束就是 S[i]-S[j]\ge L，这两组约束同样构成二维偏序，于是 CDQ 分治即可。

//核心代码
void merge(int l,int r){
    if(l==r) return;
    int mid=(l+r)/2;
    merge(l,mid),merge(mid+1,r);
    for(int j=l,i=mid+1;i<=r;i++){
        while(j<=mid&&sum[i]-sum[j]>=L) j++;
        ans+=j-l;
    }
    for(int j=l,i=mid+1;i<=r;i++){
        while(j<=mid&&sum[i]-sum[j]>R) j++;
        ans-=j-l;
    } 
    sort(sum+l,sum+1+r);
}

值得注意的是，调用 merge 函数时应从 0 开始，因为它是对前缀和数组分治的。

Code

动态问题：把时间戳看做偏序

以树状数组1为例，题目要求单点修改，区间求和。

前文说过，CDQ 分治的主要思想是，计算前面对后面的影响，对于像本题这种修改查询问题，我们在分治的过程中，只计算 前面修改对后面查询的贡献。

方便起见，我们把一个查询 [l,r] 分成 [1,r] 和 [1,l-1] 两个查询的差。

这样，每一个操作（不管是修改或是查询）就都有了两个属性，一个是时间戳 t，一个是在原数列中的位置 x。

考虑每一次分治过程，遍历时间戳，这样就保证了 t 有序，分治 x ，保证前面修改对后面查询的贡献，这实际上就是一个 CDQ 分治的过程。

（实际上，这就是 x 和 t 构成的二维偏序，这样就把高维问题（动态问题）转化成了低维问题（静态问题））。

//核心代码
void merge(int l,int r){
    if(l==r) return;
    int mid=(l+r)/2;
    merge(l,mid),merge(mid+1,r);
    int sum=0,len=l;
    for(int j=l,i=mid+1;i<=r;i++){
        if(que[i].type==1) continue; 
        while(j<=mid&&que[j].x<=que[i].x){
            if(que[j].type==1) sum+=que[j].c;//对于前面的修改，直接累加在后面的查询中
            j++;
        }
        Ans[que[i].q]+=sum*que[i].c;//这里que[i].c表示应该加上或减去
    }   
   //归并的过程，也可以使用sort实现，但那样会多出一个log，而本题数据范围为5e5
   //值得注意的是，这个归并不能在前面的处理过程中一起实现，continue会跳过一些东西
    int j=l;
    for(int i=mid+1;i<=r;i++){
        while(j<=mid&&que[i].x>=que[j].x){
            tmp[len++]=que[j++];
        }
        tmp[len++]=que[i];
    }
    while(j<=mid) tmp[len++]=que[j++];
    for(int i=l;i<=r;i++) que[i]=tmp[i];
}

sort代码（70pts）

归并代码（100pts）

思考

如何用 CDQ 分治实现 区间修改，单点查询。

提示：差分

再思考

如何实现 区间修改，区间查询。

三维偏序

（暂时咕了）

板题

CDQ 分治优化 DP

首先介绍 CDQ 分治优化一维 DP 的转移（可能叫线性 DP。

以最长上升子序列一题为例，原题为 n\le 5000，假若我们有一题数据范围为 n\le 10^5 再来考虑这道题。

首先，这题的转移式为

dp[i]=\min(dp[j]+1) (j<i,a_j<a_i)

复杂度为 O(n^2) ，考虑优化。

注意到条件 j<i,a_j<a_i 是一个偏序的形式，自然考虑 CDQ 分治。

每次分治时，首先递归左边，此时左边的 DP 值是正确的，但右边的只能算是“临时“的 DP 值，于是需要处理左边转移对右边的影响（CDQ 分治经典思想），而后再去更新右边的 DP 值。

似乎这个方式与我们之前所讲的 CDQ 分治有所不同，但这是必然之举，DP 转移与偏序不同，要求有序，所以 j\in [\mathrm l,\mathrm{mid]} 和 i\in[\mathrm{mid+1},r] 这两段的转移需要单独处理。

（这个过程似乎不太好理解，较详细的是OIwiki上的证明）。

//转移过程
void merge(int l,int r){
    if(l==r){
        if(l==1) a[1].dp=1;//需要注意的：dp[1] 的初始化，CDQ转移过程值会乱
        return;
    }
    int mid=(l+r)/2;
    merge(l,mid);
    sort(a+mid+1,a+r+1,cmp);
    int maxx=0;
    for(int j=l,i=mid+1;i<=r;i++){
        while(j<=mid&&a[i].x>=a[j].x)
                maxx=max(a[j++].dp,maxx);
        a[i].dp=max(a[i].dp,maxx+1);
    }
    sort(a+mid+1,a+r+1,cmp2);//cmp2按原序号排序：递归右边前需要把 DP 值恢复原样（想一想为什么
    merge(mid+1,r);
    sort(a+l,a+r+1,cmp);
}

Code

思考

CDQ 分治能优化一维 DP 的条件是什么？

（什么样的一维 DP 能用 CDQ 分治优化？）

CDQ 分治与斜率优化 DP

一些斜率优化 DP 的题目不满足决策单调性，可以用 CDQ 分治辅助（如任务安排2一题）

（咕咕咕）

CDQ 嵌套 CDQ