暑假集训__cdq分治

主要思想
和所有分治思想一样，将一个大问题分为两个小问题，归纳解决小问题，然后计算出其之间的贡献，即可合并为这个问题的答案。

大概是

找到区间[l,r]的mid

解决 [l,mid] , [mid+1,r] 两个小问题

计算左区间对于右区间贡献并更新右区间的ans

问题是如何计算两个小问题后并之后的贡献。

我们可以看一道题：

P1908 逆序对
大家肯定都学过了归并排序求逆序对
那么我们在思考一下，这其实也是一种分治：首先解决了
,然后在合并时需要计算左边对右边的影响， 具体则是类似于双指针，右边挨个看左边有多少比它大的 ，可以参考代码理解以下过程 。

具体可看代码：

码
首先我们对
进行完操作后，他们应该是已经排好序的。

如 [1,4,6] , [2,3,8]

初始状态，双指针都在最开始，

屏幕截图 2026-07-12 204224

首先比较
和
两指针所指向的谁比较小，可以看到
所指的比较小 ，左侧不需要考虑新贡献，所以只需要将其加入b里面以方便排序，将
向右移动一格。

屏幕截图 2026-07-12 211453

再次进行比较，发现
所指的比较小，需要计算贡献，此时
的有
个，加在
上即可，然后将
所指的加到
数组里即可 ，
右移。

然后依次进行比较：

最后输出
即可 ， 复杂度

那么我们大概可以理解cdq的主要思想了，接下来看几道例题。

回到顶部
例题
P4390 [BalkanOI 2007] Mokia 摩基亚
首先不难想到一个矩形
, 可以拆成
四个与
组合的大矩形计算。

于是题目转化为了，给出对任意
的操作和询问，涉及二维偏序(其实还有时间一维)。

类似于上面，可以在cdq双指针里套一层树状数组解决，可以做到
。

关于时间复杂度的证明： 首先cdq本身是一个log，在每个双指针进行操作时，我们将直接操作改为树状数组，相当于每个操作都乘了一个
，
是不确定的，但
，所以其实复杂度是介于
之间的，但基本认为是近似于
。

点击查看代码
P3810 【模板】三维偏序 / 陌上花开
其实同样这次是真的三维偏序，只需先sort解决一维，然后和上面一样cdq+树状数组干掉两维。

需要注意的是，挂=就很难处理，一个不错的思路是分为操作和询问分类进行处理，在sort里优先将操作放在前面以产生对后面的影响，最后答案-1即可 ,

点击查看代码
回到顶部
进阶（从三维偏序到四维偏序）
根据上面的题目，我们似乎只会最多三维偏序，接下来学习四维偏序怎么处理。

P14957 【模板】离线静态四维数点
首先转化一下题意，可以将
取负，这样我们的条件都是
，
这样后面也不用考虑谁大谁小了。

事实上，cdq是可以嵌套的。

啥意思？ 其实我们可以想一下，对于计数的条件是四维都满足
的关系，那么我们首先
解决一维，然后变成了三维，如果再套一层
双指针树状数组
即可，可是从第一层cdq如何转向第二层cdq，并保证第一层的cdq所排序的信息有效。

在 cdq1 时，我们首先递归解决了
，
接下来如何计算左边对右边的影响？ 我们知道，经过递归，左右序列均已按照
(这里我定义
为第二关键字，别的也可以) 排好序了，并且第一层的排序使得只能左边对右边产生影响，剩下的两维需要传到 cdq2 里面去解决。

可是在cdq2之前，我们已经按第二关键字，排完序了，我们需要保住第一层的信息，即 区分好左边和右边 ，所以我们在进入cdq2之前要先给
部分打上 左 标记 ， 给
打上 右 标记，然后传入cdq2后只能由既有左标记，又在新排序后左侧的数给既有右标记，又在新排序后右侧的数造成贡献。这样，在同时保证一二维的情况下可以用双指针加树状数组解决后两维，复杂度

码
再给出一道四维偏序的例题：

其实大家可以先做一下 P4093 [HEOI2016/TJOI2016] 序列 , 可以学习一下cdq优化dp的思路。

P5621 [DBOI2019] 德丽莎世界第一可爱
首先我们已经可以处理四维偏序，但这题困难其实在于DP部分的思想和之前cdq惯用部分不同，之前是单纯的计数，先记哪个部分没有影响，但DP是有严格的转移顺序的，必须左边全都做完了，才能做右边。

也就是说，我们不能上来就处理
,因为右边部分内部转移时，并未进行左边到右边的转移，顺序是错的，事实上，应该先处理了
，毕竟这部分和右边无关，然后计算左边到右边的转移，然后再处理
的内部转移。

具体题解可以看luogu