暑假集训__cdq分治

主要思想和所有分治思想一样将一个大问题分为两个小问题归纳解决小问题然后计算出其之间的贡献即可合并为这个问题的答案。大概是找到区间[l,r]的mid解决 [l,mid] , [mid1,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