CDQ分治

CDQ分治

定义:

\(CDQ\) 分治是一种思想而不是具体的算法,和 动态规划 类似,大致分为三类:

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

解决和点对有关的问题:

这类问题类似于:

给定一个长度为 \(n\) 的序列,统计有一些特性的点对 \((i,j)\) 的数量,或者使 \((i,j)\) 对应的函数值最大

流程:

  1. 找到这个序列中点 \(mid\)
  2. 将所有点对分为三类: 都在中点左边,一左一右,都在中点右边
  3. 将 \((1,n)\) 这个序列拆成两个序列: \((1,mid)\) 和 \((mid+1,n)\) 。此时第一类点对和第三类点对都在这个序列。
  4. 递归处理这两类点对
  5. 设法处理一左一右的情况。

可以看出,\(CDQ\) 分治思想就是不断把点对通过递归的方式分给左右两个区间,运用 \(dfs(l,r)\) 这种函数解决问题。

例题:

最经典的就是处理三维偏序:陌上花开

题意:

有 \(n\) 个元素,第 \(i\) 个元素有 \(a_i,b_i,c_i\) 三个属性,设 \(f(i)\) 表示满足 \(a_j \leq a_i\) 且 \(b_j \leq b_i\) 且 \(c_j \leq c_i\) 且 \(j \ne i\) 的 \(j\) 的数量。

对于 \(d \in [0, n)\) ,求 \(f(i)=d\) 的数量。

分析:

首先,数字顺序没有影响答案,因此可以重新进行排序,并且将相同的数字存一块。

按照 \(a\) 排列数组,则满足答案的式子为 \(b_j \leq b_i,c_j \leq c_i\)。

传到 \(solve\) 中后,我们把左右两边 \([l,mid],[mid+1,r]\) 分块按 \(b\) 排列。

然后从 \(i\in [mid+1,r]\) 中,挑选出 \(b_j \leq b_i\) 的情况,并且运用 树状数组 在 \(c_j\) 的位置上加上 \(c_j\) 的数量。

然后,计算 \(c_j \leq c_i\) 的数量一共有多少个。这个操作也是运用了树状数组。

最后,注意算完清空即可。更多详细过程在代码中:

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&-x
const int N=5e5+5;

struct node{
    int a,b,c,cnt,ans;
}s1[N],s2[N];

int ans[N];

bool cmp1(node x,node y){//按照第一维排序
    if(x.a==y.a){
        if(x.b==y.b) return x.c<y.c;
        else return x.b<y.b;
    }
    else return x.a<y.a;
}

bool cmp2(node x,node y){
    if(x.b==y.b) return x.c<y.c;
    else return x.b<y.b;
}

int n,k,m,cnt;
int c[N];
void add(int x,int z){
    for(;x<=k;x+=lowbit(x)) c[x]+=z;   
}

int query(int x){//记录权值为x的元素的个数
    int res=0; for(;x;x-=lowbit(x)) res+=c[x]; return res;
}

void solve(int l,int r){
    if(l==r) return;
    int mid=l+r>>1;
    solve(l,mid); solve(mid+1,r);
    sort(s2+l,s2+mid+1,cmp2); sort(s2+mid+1,s2+r+1,cmp2);
    //分区键排序:保证[l,mid] 第一维小于 [mid+1,r] 第一维,并且保证两区间内第二维单调不下降
    int i,j=l;
    for(i=mid+1;i<=r;i++){
        while(s2[i].b>=s2[j].b&&j<=mid){
            add(s2[j].c,s2[j].cnt);//在s2[j]加上s2[j]的个数,表示第二维满足
            j++;
        }
        s2[i].ans+=query(s2[i].c);//查询[l,mid] 中有多少数满足小于等于s2[i].c
    }
    for(i=l;i<j;i++) add(s2[i].c,-s2[i].cnt);
}

int main(){
    cin>>n>>k;
    for(int i=1,x,y,z;i<=n;i++){
        scanf("%d%d%d",&x,&y,&z); s1[i].a=x; s1[i].b=y; s1[i].c=z;
    }
    sort(s1+1,s1+1+n,cmp1);
    for(int i=1;i<=n;i++){//转入 CDQ 数组
        cnt++;
        if((s1[i].a!=s1[i+1].a)||(s1[i].b!=s1[i+1].b)||(s1[i].c!=s1[i+1].c)){
            s2[++m].a=s1[i].a,s2[m].b=s1[i].b,s2[m].c=s1[i].c; s2[m].cnt=cnt; cnt=0;
        }
    }
    solve(1,m);
    for(int i=1;i<=m;i++) ans[s2[i].ans+s2[i].cnt-1]+=s2[i].cnt;
    //实际一个数的答案是和这个数相同的个数cnt和本身的答案ans
    for(int i=0;i<n;i++) printf("%d\n",ans[i]);
    system("pause");
    return 0;
}

优化 \(1D\) 动态规划转移:

\(1D\) 动态规划指的是一类特定的 \(DP\) 问题,该类题目的特征是 \(DP\) 数组是一维的,转移是 \(O(n)\) 的。

而分治能把他们的时间复杂度下降到 \(O(n \log^2 n)\)

通常,这些 \(dp\) 条件是多维偏序。

流程:

  1. \(l=r\) 说明 \(dp_r\) 值已经被计算好了,直接令 \(dp_r+1\)
  2. 递归使用 solve(l,mid)
  3. 处理所有 \(l\leq j \leq mid, mid+1\leq i \leq r\) 的转移关系
  4. 递归使用 solve(mid+1,r)

第三步做法和 \(CDQ\) 分治求三维偏序差不多。处理转移关系时,依然将所有点 \(i,j\) 按照 \(a\) 排序。然后跟上面处理差不多,最后查一下前缀最大值更新 \(dp_i\) 就可以了。

给一道例题:[SDOI2011]拦截导弹

动态问题转化为静态问题:

前两种情况使用分治目的是: 将序列折半,递归处理点对间的关系。

不过现在要求折半 时间序列

它适用于一些「需要支持做 \(xxx\) 修改然后做 \(xxx\) 询问」的数据结构题。该类题目有两个特点:

  1. 把询问离线,所有操作会按时间排成一个序列。
  2. 每一个修改和之后的询问息相关,有 \(O(n^2)\) 对。

分治的操作和处理点对关系的分支操作也相同。

如果各个修改之间是 独立 的话,就不需要处理左右区间的时序问题。

如果不独立,那么两个区间可能会进行依赖关系,此时所有跨越 \(mid\) 的修改必须放在 solve(l,mid)solve(mid+1,r) 之间。

例题:[HNOI2010]城市建设

上一篇:428,剑指 Offer-打印从1到最大的n位数


下一篇:LOJ112三维偏序