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

路终会有尽头，但视野总能看到更远的地方。

0%

CDQ分治学习笔记

发表于 更新于 分类于 Valine：

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

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].t<=a[i].t$，$t$是在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

相关文章
姥爷们赏瓶冰阔落吧~