【算法-数据结构】CDQ分治

PandZz · 2019-06-06 11:18:21 · 个人记录

基于时间的分治算法 CDQ 分治 详解

降维!!!

基础知识 (都是书上的原话)

大多数数据结构问题都可以抽象为”维护一系列数据，并对一系列操作做出响应”。 这些操作分为“查询”和“修改”两类 对于操作的顺序，也是一个要点，我们称之为：时间轴

算法的分类：

根据对“查询”响应时间的不同，算法可大致分为两类：

• 在线算法 ： 在线算法依次获得每项操作，并能够在每次“查询”时给出答案，再进行下一个操作
• 离线算法 ： 离线算法预先获得所有操作，经过计算后，统一、批量地给出答案

问题的分类：

根据两种操作在时间轴上的不同，问题可分为两类：

• 静态问题 ： 没有“修改“类操作，或所有”修改“类操作都在”查询“类操作的前面
• 动态问题 ： 不是静态问题的，就是动态问题

而这里即将介绍的CDQ 分治算法就可以将一个动态问题转化成若干个静态问题求解，进而使得动态问题求解过程中常常不能使用的操作，如：排序，在这若干个静态问题中的使用成为了可能

CDQ 分治 的一般过程

敲黑板： ==对于操作序列的每个“查询”操作，计算其结果等价于“初始数据”以及“之前的修改”对该查询造成的影响==

设操作序列为 M，\forall l,r \in [1,M] , l \le r，定义 solve(l,r) 为：\forall k \in [l,r]，若第 k 项是“查询”操作，就计算 [l,k-1] 中的“修改”操作对第 k 项“查询”的影响

方法如下：

1. 设 mid=(l+r)>>1 ，递归计算 solve(l,mid)
2. 递归计算 solve(mid+1,r)
3. 计算 [l,mid] 项操作中所有“修改”操作对 [mid+1,r] 中所有“查询”操作的影响(重中之重)

显然 solve(1,M) 就是原问题， solve(i,i) 就是递归边界

一般的，当 l<r 时，计算完 solve(l,mid) 与 solve(mid+1,r) 后，还要计算 3，此时 [l,mid] 的“修改”操作已确定，[mid+1,r] 的“询问”操作也确定，因此，就可以作为一个静态问题来求解

而静态问题一般就比动态问题简单，这样，我们如果能用仅与 l \to r 的规模相关的时间复杂度解决 solve(l,r) ==3 部分==，那就太棒了~

事实上，==3 部分==的求解也是CDQ 分治的关键部分：

对于 solve(i,i+1) 其实只需应用 3 解决 M_i 对 M_{i+1} 的影响即可；此时回溯，操作序列 [i,i+1] 就已经处理完毕，再应用 3 、回溯......最终就解决了整个操作序列 M

因此，写好了 ==3 部分==，CDQ 分治 就完成了主体部分

例题一：LuoguP3810 三维偏序(陌上花开)

题目大意

有 n 个元素，第 i 个元素有 a_i,b_i,c_i 三个属性，设 f(i) 表示 \forall j \in n 且 a_j \le a_i,b_j \le b_i,c_j \le c_i 的 j 的数量

对于 d \in [0,n] ，求 f(i)=d 的 i 的数量并输出

输入输出

输入格式

第一行：n 和 k，表示元素数量和最大属性值

之后 n 行，每行三个整数 a_i,b_i,c_i ，为三个属性值

输出格式

• 每次将 i 对应的元素的 c 属性加入到 权值树状数组中，累加此时 \le c_j 的元素的个数

这样，就完成了至关重要的的 ==3 部分==

我的代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e5;
struct T{
    int a,b,c,num,s;
}fl[maxn+1];
//a,b,c是三个维度,num是该点的数量,s是满足该点的数据的数量：f(i)
int n,k;
int ans[maxn+1];
int c[2*maxn+1];

inline void upDate(int i,int x){
    for (;i<=k;i+=i&-i) c[i]+=x;
}

inline int getSum(int i){
    int s=0;
    for (;i>0;i-=i&-i) s+=c[i];
    return s;
}

inline void in(int &x){
    x=0;
    char ch=getchar();
    int f=1;
    while(ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    x*=f;
}

inline bool cmp(const T &x,const T &y){
    if (x.a<y.a) return 1;
    if (x.a>y.a) return 0;
    if (x.b<y.b) return 1;
    if (x.b>y.b) return 0;
    if (x.c<y.c) return 1;
    return 0;
}

inline bool cmp1(const T &x,const T &y){//按照b排序
    if (x.b<y.b) return 1;
    if (x.b>y.b) return 0;
    if (x.c<y.c) return 1;
    if (x.c>y.c) return 0;
    if (x.a<y.a) return 1;
    return 0;
}

void cdq(int l,int r){
    if (l==r){
        fl[l].s+=fl[l].num-1;
        return ;
    }
    int mid=l+r>>1;
    cdq(l,mid);cdq(mid+1,r);//假设已处理好了[l,mid]和[mid+1,r]
    //只剩下 3 部分
    sort(fl+l,fl+mid+1,cmp1);//前后分别排序
    sort(fl+mid+1,fl+r+1,cmp1);
    register int i,j=l;
    for (i=mid+1;i<=r;++i){
        while(j<=mid&&fl[j].b<=fl[i].b){
            upDate(fl[j].c,fl[j].num),++j;
        }
        fl[i].s+=getSum(fl[i].c);
    }
    for (i=l;i<j;++i) upDate(fl[i].c,-fl[i].num);//还原树状数组
}

int main(){
    in(n),in(k);
    register int i,cnt=0,m=0;
    for (i=1;i<=n;++i){
        in(fl[i].a),in(fl[i].b),in(fl[i].c),fl[i].s=1;
    }
    sort(fl+1,fl+1+n,cmp);
    for (i=1;i<=n;++i){
        ++cnt;
        if (fl[i].a!=fl[i+1].a || fl[i].b!=fl[i+1].b || fl[i].c!=fl[i+1].c){
            fl[++m]=fl[i],fl[m].num=cnt,cnt=0;
        }
    }
    cdq(1,m);
    sort(fl+1,fl+1+m,cmp);
    for (i=1;i<=m;++i){
        ans[fl[i].s]+=fl[i].num;
    }
    for (i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}

例题二：NSOJ P1363 天使玩偶 真-例题

题目大意解读

先给出一些 基础点，这些点具有横纵坐标，给定一系列操作：

1. 加入新点

2. 给定一个点，询问其它点到该点最近的的曼哈顿距离

曼哈顿距离：

解法分析

CDQ 分治将动态问题(如：此题)转化为若干个静态问题，让需要控制的维度减少

那么，我们先思考此题的静态问题： 没有”修改“操作(新加入点)，或“修改”操作都在最前面

我们来看图，感性理解 分析一下：

为方便分析，我们先考虑在该点++左下方++的点

因此，dis(i,j)的最小值可转化为：

这样，我们只需要将 基础点 和“询问”点都加入一个序列，将此序列按横坐标x排序，然后依次扫描：

1. 若扫描到一个 基础点 (x_i,y_i)，就在权值树状数组中的 c[y_i] 处维护 x+y_i的最大值
2. 若扫描到“询问”点 (x_0,y_0)，就在权值树状数组中查找(0,y] (树状数组不访问c[0]) 上的最大值 val，此询问答案就是：x_0+y_0-val

静态问题解决了，那么动态问题呢？

事实上，这道题需要控制三个维度：

1. 时间轴
2. 横坐标
3. 纵坐标

特别地，对于 基础点 ，我们将其视为修改操作，时间轴节点在整个操作序列的最前端

举个栗子

对于给定点 i:x_0,y_0 的++左下方++，即求：

• 时间轴节点在 i 前
• x_j \le x_0
• y_j \le y_0

并且 dis(i,j) 最小的 dis

可以看做不那么典型的三维偏序问题，套用CDQ 分治求解

解法讲解

按照惯例，我们还是直接分析 ==3 部分==如何写

计算前半部分对后半部分的影响：

• 对 [l,r] 整体是按 时间轴节点 排序的，因此后半部分的时间轴节点总在前半部分的“后面”
• 对于 [l,mid]操作区间， 将“修改”操作(新加入点)作为后半部分“询问”操作的基础点，并加入临时数组，将后半部分“询问”操作加入临时数组，对临时数组按 x 排序
• 还是用 i=l 与 j=mid+1，保证 x_i \le x_j，用权值树状数组维护前缀最大值，将选出的基础点 i 在权值树状数组的 c[y_i] 处维护 max\{x_i+y_i\}，查询时，更新 ans[j] 为 max\{ask(y_j)\}

这样三个维度分别用：

• 时间轴节点：CDQ 分治
• 横坐标：排序
• 纵坐标：维修维护前缀最大值的权值树状数组

就解决了在左下方的 \frac{1}{4} 的问题

关于其他方向

• 左上方：

• 右下方：

• 右上方：

综上：

对于树状数组的初始化，要初始化为“负无穷”

每次 ==3 部分==使用完树状数组后，需要还原(不要用memset，不然等着超时吧)

inline void clean(int i){//还原c[i]
  for (;i<=maxy&&c[i]!=minn;i+=i&-i)
    c[i]=minn;
}

对这几个方向也有不同：

1. 在右边：x 要按降序扫描(不一定重新排序)
2. 在上面：查询 y 的后缀最大值，此时对 y，我们更新的是 c[maxy-y]，这样，较大的 y 就被放在了前面(注意：maxy 一定要比所有 y 大，因为树状数组不会访问 c[0])

比较好想的写法是：对整个操作序列进行一次CDQ 分治，==3 部分==进行 4 次计算：左下、左上、右下、右上

==3 部分==的写法：

/*
st为扫描的开始位置，en是扫描的结束位置，dx是横坐标的系数，dy是纵坐标的系数
add是for循环中，循环变量的增值(可为1，可为-1)
*/
//之所以规定st,en,add，是为了确定横坐标升序或降序
inline void calc(int st,int en,int dx,int dy,int add){
    register int i,y,temp;
    for (i=st;i!=en;i+=add){
        y= ((dy==-1)?maxy-b[i].y:b[i].y);
        //若dy=-1，代表点在上面
        temp=b[i].x*dx+b[i].y*dy;
        if (b[i].t==1) upDate(y,temp);
        else ans[b[i].id]=min(ans[b[i].id],abs(temp-getMax(y)));
    }
    for (i=st;i!=en;i+=add){
        y= ((dy==-1)?maxy-b[i].y:b[i].y);
        if (b[i].t==1) clean(y);
    }
}

~
分
~
隔
~
线
~
啦
~
啦
~
啦
~
啦
~
啦
~
分
~
隔
~
线
~
啦
~
啦
~
啦
~
啦
~
啦
~
啦
~
啦
~
啦
~

我的代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using std::sort;
const int minn=-(1<<30);
const int maxn=1e6;
int n,m,tot,cnt;
struct Data{
    int x,y,t,id;
}a[maxn+5],b[maxn+5];
int ans[maxn+5];
int c[1000010],maxy;

inline int min(int a,int b){
    return a<b?a:b;
}

inline int max(int a,int b){
    return a>b?a:b;
}

inline int abs(int x){
    return x<0?-x:x;
}

inline bool operator <(const Data &a,const Data &b){
    if (a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}

inline void upDate(int i,int x){
    for (;i<=maxy;i+=i&-i) c[i]=max(c[i],x);
}

inline int getMax(int i){
    int Max=minn;
    for (;i>0;i-=i&-i) Max=max(Max,c[i]);
    return Max;
}

inline void in(int &x){
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}

inline void clean(int i){
    for (;i<=maxy&&c[i]!=minn;i+=i&-i) c[i]=minn;
}
/*
st为扫描的开始位置，en是扫描的结束位置，dx是横坐标的系数，dy是纵坐标的系数
add是for循环中，循环变量的增值(可为1，可为-1)
*/
inline void calc(int st,int en,int dx,int dy,int add){
    register int i,y,temp;
    for (i=st;i!=en;i+=add){
        y= ((dy==-1)?maxy-b[i].y:b[i].y);
        temp=b[i].x*dx+b[i].y*dy;
        if (b[i].t==1) upDate(y,temp);
        else ans[b[i].id]=min(ans[b[i].id],abs(temp-getMax(y)));
    }
    for (i=st;i!=en;i+=add){
        y= ((dy==-1)?maxy-b[i].y:b[i].y);
        if (b[i].t==1) clean(y);
    }
}

void cdq(int l,int r){
    int mid=(l+r)>>1;
    if (l<mid) cdq(l,mid);
    if (mid+1<r) cdq(mid+1,r);
    tot=0;
    for (register int i=l;i<=r;++i){
    //把前半的修改，后半的询问加入临时数组
        if ((i<=mid && a[i].t==1)||(i>mid && a[i].t==2)){
            b[++tot]=a[i];
        }
    }
    sort(b+1,b+1+tot);//按横坐标排序
    calc(1,tot+1,1,1,1),calc(1,tot+1,1,-1,1);
    calc(tot,0,-1,-1,-1),calc(tot,0,-1,1,-1);
}

int main(){
    in(n),in(m),m+=n;
    register int i;
    for (i=1;i<=n;++i){
        in(a[i].x),in(a[i].y),a[i].t=1,++a[i].y,maxy=max(a[i].y,maxy);
    }
    for (i=n+1;i<=m;++i){
        in(a[i].t),in(a[i].x),in(a[i].y),++a[i].y,maxy=max(a[i].y,maxy);
        if (a[i].t==2) a[i].id=i;
    }
    ++maxy;
    memset(ans,0x7f,sizeof(ans));
    memset(c,0xcf,sizeof(c));//重置c为极小值
    cdq(1,m);
    for (i=1;i<=m;++i)
        if (a[i].t==2)
            printf("%d\n",ans[i]);
    return 0;
}

快去切了这道题吧~ O(2)才是精髓

总结

CDQ 分治可以将问题需要控制的一个维度(常常是：时间)分治，进而将动态问题转换成静态，这样转化的静态问题就减少了一个维度，可以单独思考来解决，降低了数据结构需要控制的维度

。。。至于KD-Tree，它是一颗二叉搜索树什么东西，很熟悉的感觉，需要写过替罪羊树才可以展开讲，这里就交给大家自学啦~，或是以后有时间再讲，不然只是 CDQ 就讲不完 Liao~