少女祈祷中...

做着做着 cdq 分治的题发现自己太菜了写不出来题 XD,所以来写写学习笔记。

CDQ 分治

CDQ 分治一般有两个用途:解决偏序问题、将动态问题转化为静态问题。

偏序问题

我们先来介绍第一个问题:偏序问题。

普通的二维偏序就类似于逆序对,每个元素有两个属性 ai,bia_i, b_i,我们需要统计 ai<aj,bi<bja_i<a_j, b_i<b_j 的数对 (i,j)(i, j) 的数量。我们可以通过归并排序或者是树状数组来计算,时间复杂度 O(nlogn)O(n\log n)

而对于三维偏序,即统计 ai<aj,bi<bj,ci<cja_i<a_j, b_i<b_j, c_i<c_j 的数量,我们就可以使用 cdq 分治来解决。

具体的算法流程为:

[l,r][l, r] 分成两半,将两半区间递归下去处理,它们内部的偏序对自己处理,当前这一层只考虑左半边对右半边的贡献。我们按照 aia_i 排好序,来消去第一维,这时,我们发现,左半边的所有数的 aia_i 都小于右半边,这意味着在第一维上,我们从左半边向右半边的转移的限制消失了,这就允许我们在左右两部分进行一些乱搞操作,比如排序。

我们再把左右两边分别按照 bb 排序,我们可以用一个双指针,卡住左半边中 bb 小于当前的数的数(这里有点绕口 XD),用图来讲就是这样:

我们这时会发现现在 bb 的限制也消失了,我们就只有 cc 的限制了。这时我们可以直接上数据结构维护。我们把左边区间小于当前 bb 的点的 cc 加入到树状数组中,在查询时,我们只需要查询小于等于当前 cc 的元素个数即可。

这个流程十分像归并排序,只是多了一个树状数组而已。因此时间复杂度为 T(n)=2T(n2)+O(nlogn)T(n)=2T(\frac{n}{2})+O(n\log n),即 O(nlog2n)O(n\log^2 n)


cdq 分治的这个用处很多,可以用来解决许多二维数点问题,并且时间复杂度也比 KD-Tree 的 O(nn)O(n\sqrt n) 要好。我们可以来看几道例题:

[CQOI2011] 动态逆序对

给出 1n1\sim n 的排列,按照给定顺序依次删除 mm 个元素,在每次删除前统计逆序对个数。

数据范围:1n1051\le n \le 10^5


我们把每个数看成有 33 个属性的元素,三个属性分别为 pos,val,timepos, val, time,即它在数组中的位置,它的值,它被删除的时间。我们可以发现,它能够和别的数形成逆序对的条件为:posi<posj,vali>valj,timei<timejpos_i < pos_j, val_i > val_j, time_i < time_jposi>posj,vali<valj,timei<timejpos_i > pos_j, val_i < val_j, time_i < time_j。这样我们就把问题转化为了一个三维偏序问题。

[SHOI2007] 园丁的烦恼

nn 个点 (xi,yi)(x_i, y_i)mm 次询问询问一个矩形区域内点的个数。

数据范围:n,m5×105,xi,yi107n,m\le 5\times 10^5, x_i, y_i\le 10^7


本题虽然和 cdq 分治无太大联系,但是我们可以把它看作一道前置题目。

我们可以先把一个询问拆成四个询问,将所有点和询问放到一起按照 xx 排序,这时我们直接扫描线一下,从左向右扫,遇到一个点就加入,遇到询问则记录答案。这样就做完了,时间复杂度 O(nlogn)O(n\log n)(KD-Tree还被卡了 www)。

而对于带插入点的问题,我们可以留到下面再看。

[SDOI2011] 拦截导弹

nn 发导弹,每发导弹有一个速度 viv_i 和一个高度 hih_i。设上一次拦截的导弹为 jj,导弹拦截系统只能拦截 vi<vjv_i < v_jhi<hjh_i < h_j 的导弹。问最多能拦截多少导弹,以及如果所有最优方案被选择的概率相同的话,每发导弹被拦截的概率。

数据范围:n5×104n\le 5\times 10^4


我们很容易就能写出转移方程:设 fif_i 为以第 ii 发导弹结尾最多能拦截多少,gig_i 为以第 ii 发子弹结尾拦截的最优方案数。则有

fi=1+maxj<ifj(vi<vj,hi<hj)f_i=1+\max _{j<i}f_j(v_i<v_j,h_i<h_j)

gi=j=1i1gj[fj+1=fi]g_i=\sum \limits_{j=1}^{i-1}g_j[f_j+1=f_i]

这个方程直接转移的复杂度为 O(n2)O(n^2)。我们考虑优化它。注意到其中有 33 个偏序关系:j<i,vi<vj,hi<hjj<i, v_i<v_j, h_i < h_j。我们考虑用 cdq 分治优化。

首先第一维已经排好序了,我们直接来看第二和第三维。我们再把第二维排个序,和三位偏序一样,用双指针卡住,并且把第三维所代表的 dp 值加入数据结构中。这时我们需要一个查询区间最大值以及最大值出现次数的数据结构,可以考虑用线段树维护。这样第一问就做完了。

我们再考虑第二问,我们可以先把所有的方案数算出来,即 sum=i=1ngi[fi+1=ans]sum=\sum \limits_{i=1}^{n}g_i[f_i+1=ans]。我们再考虑每个点的出现次数。我们再反着跑一遍 dp,求出反着的最长上升序列,也算出当前的 gg 值,分别记为 f1(i),g1(i)f_1(i), g_1(i)

我们枚举每个点,因为它左右都为最优方案,如果 f(i)+f1(i)1ansf(i)+f_1(i)-1 \not= ans,则它一定不可能被拦截,否则根据乘法原理,拦截它的方案数为 g(i)×g1(i)g(i)\times g_1(i)

同时,我们在这题中还需要注意转移顺序的问题。我们必须先执行 cdq(l,mid)cdq(l, mid),再计算左半区间对右半区间的贡献,最后再计算 cdq(mid+1,r)cdq(mid + 1, r)。这样是为了防止在右区间转移时用不正确的 dp 值直接转移。

动态问题转为静态问题

动态问题是指在询问的过程中可能会有修改的操作,而静态问题指所有的修改都在询问前完成。用 cdq 分治,我们可以把动态问题转化为静态问题,取而代之的是时间复杂度增加一个 logn\log n

我们可以把所有操作看成一个序列,我们设 cdq(l,r)cdq(l, r) 为计算 [l,mid][l, mid] 的修改对 [mid+1,r][mid + 1, r] 的询问的影响。我们可以直接把 [l,mid][l, mid] 的修改操作全部加入,然后扫描一遍右半区间的询问,更新一遍即可。

听起来十分简单,下面来看几道例题。

简单题(弱化版)

给定一个平面,支持两种操作:在 (x,y)(x, y) 处添加一个权值为 vv 的点、查询矩形区域内的点的权值和。

数据范围:q105q\le 10^5


根据上面“园丁的烦恼”那道题,我们可以如法炮制,一个询问拆成四个询问,然后前缀和即可。但是本题带上了插入点操作。我们就需要 cdq 分治来解决。

我们考虑 [l,mid][l, mid] 插入的点对 [mid+1,r][mid + 1, r] 的贡献,我们可以直接把这些点全部加入到平面中,然后进行一遍扫描线即可,最后将答案累加。

时间复杂度 O(nlog2n)O(n\log^2n)

(本人在闲来无事的时候突然想到:如果一个点能对询问产生贡献,那么必须满足 ti<tj,xi<xj,yi<yjt_i < t_j, x_i < x_j, y_i < y_j,好像又是一个三维偏序 XD)

天使玩偶/SJY摆棋子

平面上有 nn 个点,mm 次操作,有两种操作:向平面内添加点、询问与 (xi,yi)(x_i, y_i) 曼哈顿距离最近的点的曼哈顿距离。

数据范围:n,m3×105,xi,yi106n, m\le 3\times 10^5, x_i, y_i \le 10^6


我们先来考虑没有添加点的操作时怎么解决。我们可以先把曼哈顿距离中的绝对值去掉,我们在这里只讨论 xa>xb,ya>ybx_a>x_b, y_a > y_baa 为查询的点)时的情况,剩下的情况同理。

我们的式子就变为了求 xaxb+yaybx_a-x_b+y_a-y_b 的最小值,也就是求 max(xb+yb)\max (x_b+y_b)。我们可以先把所有询问和修改按照 xx 排序,然后维护线段树,扫描到修改就在 yby_b 处插入值 xb+ybx_b+y_b。扫描到询问就询问所有小于 yay_a 的位置的最大值即可。

而这时增加了询问,我们就需要用 cdq 分治解决。我们可以先把左半区间的修改点加入到一个集合内,再把右半区间的询问也加入到这个集合,对这个集合跑一遍上面的流程更新答案即可。

这样,一个询问总共会被更新 logn\log n 次,所以复杂度为 O(nlog2n)O(n\log^2 n)

镜中的昆虫

给定一个长度为 nn 的序列,支持以下两种操作:查询 [l,r][l, r] 有多少不同的数值,区间覆盖。

数据范围:n105n\le 10^5


我们先考虑答案怎么统计。对于区间数颜色,有一个十分套路的方法:对每个点维护一个 preipre_i,即这个点往前走,第一个遇到的和它相同的颜色的点。那么这个区间的颜色数即为在这个区间内,且 preipre_i 小于 ll 的个数,形式化的说就是满足 lir,prei<ll \le i \le r, pre_i < l 的个数。

是不是感觉很眼熟,这就是一个典型的二维数点。可以直接用树状数组做,像下图。

我们这样就可以统计完无修改时的答案,我们再来考虑有单点修改的情况。

我们注意到,单点修改颜色每次只会导致 O(1)O(1) 位置的 preipre_i 发生变化,我们可以把这些变化也看成平面上的点,只是带上了 111-1 的权值,我们用 cdq 分治直接二维数点即可。

而对于区间覆盖,我们需要一个结论:我们能发现,在这些颜色段中,对于每个颜色段,只有两端的 preipre_i 才是有价值的,我们不妨称它为有效 preipre_i,而有效 preipre_i 的变化数量为 O(n+m)O(n+m) 级别。我们可以用颜色段均摊的方法证明,对于每次区间覆盖,只会增加一个颜色段,可能还会删除更多的颜色段,因此变化量在 O(n+m)O(n+m) 级别。

我们就可以用珂朵莉树先对所有修改跑一遍,跑出所有的 prepre 变化。然后 cdq 分治二维数点即可。

[HNOI2010] 城市建设

给定一张图,图有边权,有 mm 次修改一条边的边权,每次修改后输出最小生成树边权和。

数据范围:n2×104,m5×104n\le 2\times 10^4, m \le 5\times 10^4


本题个人感觉比上面那题难

本题有常数巨大的线段树分治套 lct 做法,这里不介绍。

暴力肯定是每次询问都跑一次 kruskal,但是复杂度直接爆炸。因此我们考虑简化 kruskal 中边的集合。

我们考虑 [l,r][l, r] 这段区间修改的边,不妨把这些边叫做动态边,剩下的边叫做静态边。我们考虑两个极端情况:-\infty++\infty。先把动态边的边权全部设为 -\infty,然后跑一遍 kruskal,这时在 MST 中的静态边一定是会被选择的,我们不妨把这些边所对应的点全部缩到一起,这些边也就无用了。

我们再把动态边的边权设为 ++\infty 跑 kruskal,这时不在 MST 中的静态边一定不会在最终的 MST 中,直接扔掉即可。这样我们就完成了简化边集的效果。递归到 l=rl=r 时把动态边和剩下的边集放一起跑 kruskal 即可。

至于递归顺序,我们可以采用先处理 [l,r][l, r],再 CDQ(l,mid),CDQ(mid+1,r)CDQ(l, mid), CDQ(mid + 1, r)。因为我们考虑的是极端情况,而在极端情况之内的普通情况也一定是适用的,所以先处理 [l,r][l, r] 再处理左右区间也是正确的。

而对于时间复杂度的分析,我们只需要分析出每一层的复杂度是 O(len)O(len) 相关即可。对于第一个简化边集的操作,至多会剩下 lenlen 个联通块,因此每个区间要处理的边集也是 O(len)O(len) 级别的。因此复杂度为 O(nlog2n)O(n\log^2n)

其实这题也可以用线段树分治的思想理解。我们在 cdq 分治的过程中其实也建出了一颗线段树,我们上面这题就是对这颗线段树的前序遍历。不过线段树分治可能更好理解 XD。

The End

其实 CDQ 分治我还有一些没写,比如优化斜率优化、四维偏序,但是限于本人能力有限,因此没有写。