CDQ分治学习笔记

陈丹琦分治(以下简称为CDQ分治)来自雅礼中学的前信息学奥赛队队员陈丹琦,她在2008年发佈的集训队论文作业《从〈Cash〉谈一类分治算法的应用》中提出了这一种能够简洁有效解决问题的方法。

而本文将选取有关CDQ分治的典型题目和非典型题目,来进一步探讨该算法的模型特点、解题思路和根本内涵。

典型选例

我们首先将论文《从〈Cash〉谈一类分治算法的应用》的内容整理在这裡,以详细了解CDQ分治的思想来源。

NOI 2007 货币兑换

命题

小Y最近在一家金券交易所工作。该金券交易所只发行交易两种金券:$A$纪念券(以下简称$A$券)和$ B $纪念券(以下简称$ B $券)。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。

每天随着市场的起伏波动,两种金券都有自己当时的价值,即每一单位金券当天可以兑换的人民币数目。我们记录第$ k $天中$ A $券和$ B $券的价值分别为$ A_k$和$ B_k$(元/单位金券)。

为了方便顾客,金券交易所提供了一种非常方便的交易方式:比例交易法。

比例交易法分为两个方面:

A) 卖出金券:顾客提供一个$[0,100]$内的实数$ OP $作为卖出比例,其意义为:将$ OP\%$的$ A $券和$ OP\%$的$ B $券以当时的价值兑换为人民币;

B) 买入金券:顾客支付$ IP $元人民币,交易所将会兑换给用户总价值为$IP $的金券,并且,满足供给顾客的$ A $券和 $B $券的比例在第$ k $天恰好为$ Rate_k$;

例如,假定接下来 3 天内的$ A_k$、$B_k$、$Rate_k $的变化分别为:

時間 $A_k$ $B_k$ $Rate_k$
第一天 1 1 1
第二天 1 2 2
第三天 2 2 3

假定在第一天时,用户手中有100元人民币但是没有任何金券。 用户可以执行以下的操作:

时间 用户操作 人民币(元) $A $券的数 $B $券的数
开户 100 0 0
第一天 买入100元 0 50 50
第二天 卖出50% 75 25 25
第三天 买入60元 15 55 40
第四天 卖出100% 205 0 0

注意到,同一天内可以进行多次操作。

小Y是一个很有经济头脑的员工,通过较长时间的运作和行情测算。他已经知道了未来$ N $天内的$ A $券和$ B $券的价值以及 $Rate$。他还希望能够计算出来,如果开始时拥有$ S $元钱,那么$ N $天后最多能够获得多少元钱。


首先我们可以列出一个朴素的$O(n^2)$的动态规划方程,设$f[i]$表示在第$i$天把所有钱全部兑换所能得到的最多的$A$券数量,有:

$$f[i]=\max_{j<i}\left\{f[j]\cdot A[i]+f[j]\cdot \frac{1}{Rate[j]}\cdot B [i]\right\}\cdot Rate[i]\div(A[i]\cdot Rate[i]+B[i])$$

设$g[i]=\frac{f[i]}{Rate_i}$,不妨设$f[j] < f [k]$,那麽有:

$$\frac{g[j] – g[k]}{f [j] – f[k]} < -\frac{A[i]}{B[i]}$$

这样问题就变成了斜率优化动态规划问题,但我们发现横坐标并不满足单调性质,也就是说这个凸包需要动态维护。关于动态凸包维护使用的是平衡树这种数据结构,原文中有这麽一句话:

这样动态规划的时间复杂度就降低为$O(nlog^2n)$,但是维护凸线的平衡树实
在不容易在考场中写对☹,编程复杂度高,不易调试。

下面就是经典的CDQ分治算法的流程,请务必不要走神仔细阅读:

我们定义函数$solve(l,r)$表示对于$i\in[l,r]$,我们想用$j\in[l,i-1]$求出$f[i]$的答案。我们取$[l,r]$中点$mid$,我们希望调用$solve(l,mid)$之后立即用已经形成的凸包来更新$[mid+1,r]$中的$f$函数值。不停像分治那样递归求解,不难发现当$l=r$时,$f[l]$的决策区间$[1,l-1]$已经被$log(l)$块之前的分治区间所完整包含,已经求出了最优解。

下面探讨实现这个优美思想的细节问题。

对于维护凸包,我们在递归的过程中使用类似归并排序的方法,使$mid$左右的区间分别以$f$为关键字有序,然后使用计算几何中的Graham凸包构造方法,使用一个栈维护合併后的凸包。

递归调用$solve(l,mid)$后返回到当前分治区间,现在我们在$[l,mid]$有了一个凸包,我们队$i\in[mid+1,r]$中的元素以$-\frac{A[i]}{B[i]}$为关键字排序,之后可以使用经典的双指针在$O(n)$的时间複杂度内更新$f$。可排序是$O(nlogn)$的,複杂度相对过高,但我们发现$A,B$是提前给出的,我们只需在归併排序中再另外预处理出顺序即可,时间複杂度变成$O(n)$。

就这样,我们解决了这个问题,而没有调用复杂的数据结构,代码複杂度大大降低😆!最终的时间複杂度为$O(nlogn)$,空间複杂度为$O(nlogn)$。

下面引用原论文的伪代码:

———————————————————————————————————————————————————
$Procedure\,Solve(l, r) :$
$lf\,l = r$
$Then$更新$ans$,利用已经计算好的$l$的最优决策$k$,计算$f [l]$值,$Exit$
$Mid ← (l + r) / 2$
$Solve(l, mid -1)$
对$[l, mid-1]$这一段扫描一遍计算出决策的凸线,由于$[mid+1 .. r]$这一段以$-a[i] / b[i]$的排序在预处理已经完成,因此只需要扫描一遍更新$[mid + 1 … r]$的最优决策。
$Solve(mid+1, r)$
利用$[l, mid-1]$已排好序的$f []$值和$[mid+1, r]$已排好序的$f []$值归并排序将$[l, r]$这一段按$f[]$值排序。
$End\,Procedure$
——————————————————————————————————————————————————————————

解題

我们发现我们之所以能做这些操作,是因为我们保证了无论如何,在任意分治区间的$mid$左边的任意一个元素的$i$均小于右面的任意元素的$i$。我们直接拿出了一整个集合,然后统一处理其能影响的各个询问(按最优化的顺序处理),不停分治下去直到上面一开始提到的$l=r$的情况。

无论题目如何变化,只要这一思想适用,则就可以使用CDQ分治。更具体的话。其在表面上应满足:

  1. 操作相互独立,且对询问的贡献相互独立。
  2. 允许离线操作,即可以先得到所有操作和询问。

这就是CDQ分治的适用条件,我们往往使用排序来实现这一思想,而与分治有关的排序中,自然是归并排序的效率最高,可以在分治的同时排序,大大降低复杂度。

BalkanOI 2007 Mokia

命題

有一个$W\times W$的棋盘,每个格子内有一个数,初始的时候全部为$0$。现在要求维护两种操作:
1) $Add$:将格子$(x, y)$内的数加上$A$。
2) $Query$:询问矩阵$(x_0, y_0, x_1, y_1)$内所有格子的数的和。
数据规模:操作$1) ≤ 160000$,操作$2) ≤ 10000$,$1\leq W\leq 2000000$。


这是十分典型的二维区间查询单点修改,使用二维区间数据结构维护。但本命题的$W$过大,而二维树状数组的空间複杂度为$O(n^2)$,即使使用动态开点线段树最多也会有操作数量$\times O(log^2n)$的空间複杂度,依然无法承受。

这时我们的注意到这个命题符合上面的CDQ分治适用条件。首先用经典的区间变前缀方法把询问拆为4个前缀查询并任意放在原来询问的位置,这样计算每个询问时取出它的原询问编号更新答案。这样命题变成了:有两个操作:1. 将格子$(x, y)$内的数加上$A$。2. 询问二维前缀矩阵$(x_0, y_0)$内所有格子的数的和。

直接使用刚才的CDQ分治的方法,把这两个操作看做二维平面上的点,则成为经典的二维偏序问题。

我们在每个分治区间保证$x$维度满足$mid$左边的任意一个点的$x$均小于右边的任意一个点的$i$,然后直接使用二维区间数据结构维护$[l,mid]$的一个前缀区间和,然后对于$[mid+1,r]$的元素使用区间查询前缀和求出答案。设$n$为操作数,由递推式$T(n)=2\cdot T(\frac{T}{2})+O(nlogW)$可得最终时间複杂度为$O(nlogn\cdot logW)$,小于二维数据结构的$O(nlog^2W)$。

我们又一次整体维护了被询问集合,并整体更新了询问集合的答案,最终解决了问题。

三维偏序问题

小总结

如果要简洁概括出CDQ分治的通俗步骤,应该为:
递归处理$[l,mid]$的操作和询问$\rightarrow$
处理$[l,mid]$的操作对$[mid+1,r]$的询问的影响$\rightarrow$
递归处理$[mid+1,r]$的操作和询问

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注