专题：CDQ 分治

本页面将完整介绍 CDQ 分治。

简介

CDQ 分治是一种思想而不是具体的算法，与动态规划类似。目前这个思想的拓展十分广泛，依原理与写法的不同，大致分为三类：

• 解决和点对有关的问题。
• 1D 动态规划的优化与转移。
• 通过 CDQ 分治，将一些动态问题转化为静态问题。

CDQ 分治的思想最早由 IOI2008 金牌得主陈丹琦在高中时整理并总结，它也因此得名。

解决和点对有关的问题

这类问题多数类似于「给定一个长度为nn的序列，统计有一些特性的点对(i,j)(i,j)的数量/找到一对点(i,j)(i,j)使得一些函数的值最大」。

CDQ 分治解决这类问题的算法流程如下：

1. 找到这个序列的中点 ；
2. 将所有点对(i,j)(i,j)划分为33类：
   • 1≤i≤mid，1≤j≤mid的点对；
   • 1≤i≤mid，mid+1≤j≤n的点对；
   • mid+1≤i≤n，mid+1≤j≤n的点对。
3. 将(1,n)(1,n)这个序列拆成两个序列(1,mid)(1,mid)和(mid+1,n)(mid+1,n)。此时第一类点对和第三类点对都在这两个序列之中；
4. 递归地处理这两类点对；
5. 设法处理第二类点对。

可以看到 CDQ 分治的思想就是不断地把点对通过递归的方式分给左右两个区间。

在实际应用时，我们通常使用一个函数solve(l,r)处理l≤i≤r，l≤j≤r的点对。上述算法流 程中的递归部分便是通过solve(l,mid)与solve(mid,r)来实现的。剩下的第二类点对则需要额外设计算法解决。

典型例题1：LOJ112/洛谷P3810 三维偏序（陌上开花）

分析：

三维偏序（陌上开花）是 CDQ 分治的经典问题。

假设我们现在写好了solve (l, r)，并且通过递归搞定了solve (l, mid)和solve(mid+1,r)。现在我们要做的，就是统计满足l≤i服务器托管网≤mid，mid+1≤j≤r的点对(i, j)(i,j)中，有多个点对还满足i，ai​aj​，bi​bj​的限制条件。

稍微思考一下就会发现，那个ij的限制条件没啥用了：既然i比mid小，j比mid大，那i肯定比j要小。 现在还剩下两个限制条件:ai​aj​与bi​bj​, 根据这个限制条件我们就可以枚举j, 求出有多少个满足条件的i。

为了方便枚举，我们把(l,mid)和(mid+1,r)中的点全部按照a的值从小到大排个序。之后我们依次枚举每一 个j, 把所有ai​aj​的点i全部揷入到某种数据结构里（这里我们选择树状数组）。此时只要查询树状数组里有多少个点的b值是小于bj​的，我们就求出了对于这个点j，有多少个ii可以合法匹配它了。

当我们揷入一个b值等于xx的点时，我们就令树状数组的xx这个位置单点+1+1，而查询树状数组里有多少个点小于xx的操作实际上就是在求前缀和，只要我们事先对于所有的bb值做了离散化，我们的复杂度就是对的。

对于每一个j，我们都需要将所有ai​aj​的点i揷入树状数组中。由于所有的i和j都已事先按照aa值排好序， 这样的话只要以双指针的方式在树状数组里揷入点，则对树状数组的揷入操作就能从O(n2)次降到O(n)次。

通过这样一个算法流程，我们就用O(nlogn)的时间处理完了关于第二类点对的信息了。此时算法的时间复杂度 是T(n)= T( n/2 ) + T( n/2 ) + O( nlogn )=O(nlog2n)。

【三维偏序（陌上开花）-参考代码-CDQ分治】

#include 
using namespace std;

typedef long long ll;
const int N=200005;
int n,k,m;

struct node
{
    int x,y,z,id,w;
    bool operator const node &A)const{
        if(A.x==x && A.y==y) return z  A.z;
        else if(A.x==x) return y  A.y;
        return x  A.x;
    }
}a[N],b[N],d[N];

int ans[N],c[N],cnt[N];
vector int> v1,v2[N] ;

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

void add(int x,int v)
{
    for(int i=x;iv;
}

int query(int x)
{
    int ans=0;
    for(int i=x;i;i-=lowbit(i)) ans+=c[i];
    return ans;
}

void cdq(int l,int r)
{
    if(l==r) return ;
    int mid=(l+r)>>1;
    cdq(l,mid),cdq(mid+1,r);
    int t1=l,t2=mid+1;
    for(int i=l;i)
    {
        if((t1r)
        {
            add(a[t1].z,a[t1].w);
            b[i]=a[t1++];
        }
        else
        {
            cnt[a[t2].id]+=query(a[t2].z);
            b[i]=a[t2++];
        }
    }
    for(int i=l;ia[i].w);
    for(int i=l;ib[i];
}

int main()
{
    cin&gt服务器托管网;>n>>k;
    for(int i=1;i)
    {
        cin>>a[i].x>>a[i].y>>a[i].z;
        a[i].id=i;
    }
    sort(a+1,a+n+1);
    int num=1;
    for(int i=2;i1;i++)
    {
        if(a[i].x!=a[i-1].x || a[i].y!=a[i-1].y || a[i].z != a[i-1].z)
        {
            d[++m]=a[i-1];
            d[m].w=num;
            num=1;
            v2[a[i-1].id]=v1;
            v1.clear();
        }
        else
        {
            num++;
            v1.push_back(a[i-1].id) ;
        }
    }
    for(int i=1;id[i];
    cdq(1,m);
    for(int i=1;i)
    {
        int sz=v2[a[i].id].size();
        for(auto v:v2[a[i].id]) cnt[v]+=cnt[a[i].id]+sz;
        cnt[a[i].id]+=sz;
    }
    for(int i=1;i;
    for(int i=0;i'n';
    return 0;
}

CDQ分治的限制

1. 题目允许离线操作
2. 修改操作对询问的贡献独立，且修改之间互不影响
3. 修改对答案的贡献是确定的，与判定标准无关

CDQ分治和整体二分

CDQ分治和整体二分都是基于分治的思想，把复杂的问题拆分成许多可以简单求的解子问题。但是这两种算法必须离线处理，不能解决一些强制在线的题目。不过如果题目允许离线的话，这两种算法要比在线解法（如树套树）快很多。

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwqtg.net

相关推荐: Visual prompt turning

摘要 目前调整预先训练的模型的工作方式涉及更新所有主干网络参数，即全面微调。 本文介绍了视觉提示调整(VPT)作为大规模Transformer模型完全微调的有效替代方案。 VPT从最近高效调优大型语言模型的进展中得到启发，在保持模型主干网络不变的情况下，只在输…