隐藏
CDQ分治学习笔记 | Bill Yang's Blog
0%

CDQ分治学习笔记

在看本文之前可以参考这篇文章

CDQ分治是陈丹琦在2009年国家集训队作业中提出的一种算法。
CDQ分治在信息学竞赛中有很重要的运用。


CDQ分治

先介绍一些概念,大概了解一下。
CDQ分治:对于有多个维度的问题,通过对其中一个维度进行分治,把穿插的修改和查询操作化为统一修改后统一查询的问题的算法。
不妨认为这个维度在分治中被“拍扁”成两个单位——修改单位和查询单位,也正因此我们把这种算法叫做降维打击。

这句话是CDQ分治的前奏部分,将所有有序的操作先混在一起变成无序,再按照一个维度排序后分治统一处理。

CDQ分治的思想:将信息混合到一起记作一个带信息的点。每一次先递归左子区间,然后处理左边的信息对右边信息的影响,再递归右子区间。


使用条件

  • 必须可以离线
  • 前一半做出决策后,后一半不可以再反过来影响前一半——也就是无后效性
  • 需要维护的数据规模与修改/提问的次数同阶

算法大致步骤

使用CDQBinary(L,R)来表示按照某个维度排好序后处理在区间$[L,R]$中的信息。

下面介绍CDQBinary(L,R)的过程:(所有应用的统一过程,并不会很详细)

单位区间特判

判断$L$是否等于$R$,若相等,则特殊处理点$L$的信息,然后返回。

1
2
3
4
if(Left==Right) {
Process_special();
return;
}

划分区间

然后对于$L\leftrightarrow R$中间的所有信息点,按照某一维度小于大于$mid$进行划分。
注意这里需要保证划分的维度不能有相同元素,否则会导致错误或时间退化,若划分的维度有重应该事先将其进行处理,在这里我曾经讲过。

1
2
3
4
5
6
int mid=(Left+Right)>>1;
int lpos=Left,rpos=mid+1;
for(int i=Left; i<=Right; i++)
if(a[i].???<=mid)tmp[lpos++]=a[i]; //???表示CDQ分治选取的维度
else tmp[rpos++]=a[i];
for(int i=Left; i<=Right; i++)a[i]=tmp[i];

递归左子区间

能够递归左子区间的充分性在于:我们按照$mid$进行划分后,左子区间与右子区间按照原有顺序(CDQ分治前排好序的顺序)仍然有序,因此可以递归左子区间。
能够递归左子区间的必要性在于:如果是按照CDQ分治的维度从左往右处理询问,那么对于某一类问题(如按照分治维度进行动规)就必须先将左子区间的答案计算出来才能计算当前答案。

推荐所有题都在这里事先递归。(但是有一类题是不行的,之后再介绍)

1
CDQBinary(Left,mid);

处理左边对右边的影响

如果是修改/询问的题目,在这里就是处理左边的修改对右边的询问的影响,否则统一是左边的信息点对右边的信息点的影响。

处理方法是这样的:

维护两个指针$i,j$,开始分别指向$mid+1,Left$。

若$a[j].<=a[i].$,$**$是在CDQ分治前排序的维度,就在数据结构中加入$a[j]$,并使$j$指针右移,这样我们就维护好了两维的偏序关系(CDQ分治维度,分治前排序维度)。
若不满足上述条件,则在数据结构中询问满足$a[i]$第三维偏序关系的影响。

这里用到的数据结构需要满足的要求是:能够在一段区间(偏序关系)内询问一些信息(题目要求维护的信息)。
一般我们采用树状数组/线段树进行处理。

1
2
3
4
5
6
7
8
int j=Left;
for(int i=mid+1; i<=Right; i++) {
while(j<=mid&&a[j]<a[i]) { //重载小于符号为排序序
bit.add(a[j].^^,a[j]...); //^^是第三个维度,...是点的信息
j++;
}
bit.ask(a[i].^^,a[i]...);
}

清空数据结构

用完数据结构后记得清空!

1
for(int i=Left; i<=mid; i++)bit.clear(a[i].z);

递归右子区间

然后递归右区间,充分必要性都与递归左区间差不多。

1
CDQBinary(mid+1,Right);

合并信息点

根据题目的不同,这里可能需要根据某个顺序对左右区间进行合并。(使用STL实现)

1
2
3
merge(a+Left,a+mid+1,a+mid+1,a+Right+1,tmp,cmp); //cmp是某个顺序
int tot=0;
for(int i=Left; i<=Right; i++)a[i]=tmp[tot++];

这就是CDQ分治的大致步骤了,虽然说讲的比较详细,但是初学者看到这里可能还是有些不懂,如果是这样希望你结合几道例题进行思考。
推荐先看这两道题:
「福建wc2014」3D桌球
「bzoj1176」「Balkan2007」Mokia


时间复杂度


应用

应用一.维护偏序问题

维护偏序问题是CDQ分治的拿手好戏。
这里我们有过对偏序问题的总结。

可分治维度

CDQ可以进行分治的维度有:

  • 实际的维度(如$x$,$y$,$z$,$\ldots$)
  • 时间维度(修改查询类问题的隐藏维度)
  • 数组的下标(如动规的阶段)
  • 树上的dfs序
  • 拓扑序
  • 两个实际维度之和之差
  • 动态规划出来的值
  • 答案(业界称为整体二分,实际上还是CDQ分治)

但是这些进行分治的维度必须要满足上面提到的互不相同条件。

算法步骤

偏序问题的算法步骤与上面介绍的算法大致步骤基本相同。
不同之处在于两个地方。

  • 单位区间特判一般直接返回即可

    1
    if(Left==Right)return;
  • 合并信息的时候一般按照排序顺序合并。(在这里提到过原因)

经典例题

「福建wc2014」3D桌球
「bzoj3262」陌上花开
「bzoj1176」「Balkan2007」Mokia
「bzoj2683」简单题
「CQOI2011」动态逆序对
「bzoj2716」「Violet 3」天使玩偶

应用二.左右逼近

算法概述

思考,我们使用CDQ分治来解决从左往右的影响关系。
比如在CDQ分治上进行的动态规划根据阶段利用左边更新右边。
再比如修改/查询类问题利用时间小的修改处理对时间大的查询的影响。

那么反过来呢?我们也可以处理右边对左边的影响。
合起来不就可以处理所有信息了吗?
不!缺了一个东西$mid$的影响没有处理。

那么这就出现了CDQ分治的第二个应用:左右逼近解决少一个物品影响的问题

算法步骤

左右逼近的算法步骤与上述算法大致步骤许多不同,我们重新介绍:

单位区间特判

统计当前答案并返回

1
2
3
4
if(Left==Right) {
MakeAns();
return;
}

处理右边对左边的影响

先拷贝当前信息,然后处理右边对左边的影响。

递归左子区间

实际上我们先处理右边对左边的影响然后递归左区间,这样就可以从左到右依次统计出少一个物品的情况。

1
CDQBinary(Left,mid); //向左逼近

处理左边对右边的影响

因为递归了左区间,信息已经发生了修改,因此需要先恢复原有信息。
然后再处理左边对右边的影响。

递归右子区间
1
CDQBinary(mid+1,Right); //向右逼近
恢复信息

视情况决定是否需要恢复递归左右区间前的信息

一般这类问题的大致步骤如上,一般不含有划分合并的过程。

经典例题

「bzoj2287」消失之物
「bzoj4424」「Codeforces19E」Fairy

应用三.维护凸包

算法概述

这类问题一般用于处理动规斜率优化不单调的问题。
当然也可以处理裸的可离线仅加点凸包问题。

思想步骤

首先我们需要写出状态转移方程。
然后利用经典的斜率优化步骤对方程进行变化。
根据方程的几何意义决定维护什么凸包。
观察斜率$k$与加点横坐标$x$是否单调,若单调直接使用单调队列,否则进行CDQ分治的过程。

算法步骤

在CDQ分治前先对斜率进行排序。

单位区间特判

计算当前信息点的横纵坐标,若方程中还有其它项也可以在这里处理。
然后返回

划分区间

按照动规的阶段进行划分。

1
2
3
4
5
6
int mid=(Left+Right)>>1;
int lpos=Left,rpos=mid+1;
for(int i=Left; i<=Right; i++)
if(p[i].id<=mid)tmp[lpos++]=p[i];
else tmp[rpos++]=p[i];
for(int i=Left; i<=Right; i++)p[i]=tmp[i];

递归左子区间
1
CDQBinary(Left,mid);
处理左边对右边的影响

先维护左子区间的凸包。

1
2
3
4
5
deque<int>Q;
for(int i=Left; i<=mid; i++) {
while(Q.size()>=2&&Slope(Q[Q.size()-2],Q.back())<Slope(Q.back(),i))Q.pop_back(); //根据维护凸包不同改变小于符号,这里是上凸包
Q.push_back(i);
}

然后通过左区间的凸包优化右区间的值。

1
2
3
4
for(int i=mid+1; i<=Right; i++) {
while(Q.size()>=2&&Slope(Q.front(),Q[1])>p[i].k)Q.pop_front(); //根据维护信息不同改变大于符号
f[p[i].id]=max/min(f[p[i].id],....); //计算f值
}

递归右子区间
1
CDQBinary(mid+1,Right);
合并信息点

因为要维护左子区间的凸包,因此这里必须根据水平序返回。

1
2
3
merge(p+Left,p+mid+1,p+mid+1,p+Right+1,tmp,cmp); //水平序
int tot=0;
for(int i=Left; i<=Right; i++)p[i]=tmp[tot++];

注意若从右往左维护凸包需要交换递归顺序。

经典例题

「NOI2007」货币兑换
「SDOI2012」任务安排
「雅礼day6」失去了我的音乐lost my music

应用四.缩小数据规模

算法概述

这类问题长得一点也不像CDQ分治,但也是CDQ分治的一类。
将$Left \leftrightarrow Right$区间内的信息模糊化,通过特殊处理去掉一些肯定不会被选择的信息,然后递归左右区间进行处理。

算法步骤

单位区间特判

将信息实际化,在非单位区间我们将信息模糊化进行缩减规模,所以在单位区间我们要求出答案,因此需要将信息实际化。

然后我们根据所有未被去掉的实际信息,求出题目所要求的问题。

信息模糊化

将$Left \leftrightarrow Right$区间内的信息强制模糊化,将其数值置为一个特定的值。

缩减规模

根据被模糊化的信息,去掉一定不会被选取的点。

递归子区间

递归左右区间依次处理。

1
2
3
int mid=(Left+Right)>>1;
CDQBinary(Left,mid);
CDQBinary(mid+1,Right);

经典例题

「HNOI2010」城市建设

应用五.整体二分

算法概述

整体二分的特殊在于它是对答案进行二分,而CDQ分治是对操作(时间轴)等进行二分。
为什么这种方法被称为整体二分?普通的二分是对某个单个元素进行的二分,而整体二分是对一个区间整体进行的二分,因此被称为整体二分,但因此必须要求答案与点数同阶才能进行。
整体二分的原理是二分答案,将操作对答案的影响根据二分的值划归在两个区间中依次继续二分。若每一层消耗的时间是$O(R-L)$的,那么整体二分的复杂度则为$O(n\log n)$

整体二分的题目非常神奇,但也没什么值得讲的好题。
其算法步骤在例题中讲的已经很详细,就不在这儿赘述了。

经典例题

「ZJOI2013」K大数查询

扩展.树上CDQ分治

这个扩展是achen发现的,因此也被称为ADQ分治

算法概述

类似序列上的CDQ分治,我们需要将树分为一半递归。
不难想到使用重心将树划分为一半,然后先对重心以上的部分进行递归,处理重心以上对重心及以下的部分的影响,然后递归下面的子树。

具体的顺序需要根据题目的不同进行考虑。

经典例题

「雅礼day6」失去了我的音乐lost my music

姥爷们赏瓶冰阔落吧~