CDQ 分治学习笔记

没想到吧我刚学CDQ

本文只考虑狭义的 CDQ 分治（即处理偏序问题的 CDQ分治 ），广义的推广一下就行了。

我们先看这样一个问题

例1

简要题意

给你一个序列 $a$ ，问你序列中满足 $i < j, a_i>a_j$ 的二元组 $(a_i, a_j)$ 个数。

思路

这种东西我们有两种做法。

第一种是归并排序，在合并的时候查询右区间给左区间的贡献，然后递归下去不仅可以完成排序，还可以顺便查询出逆序对的个数。

具体来说，归并排序的时候，若我们往最终序列中加入一个左区间里的数，显然此时最终序列中右区间里的数都 $<$ 该左区间的数，就会产生 “此时最终序列中来自右区间的数的个数” 的贡献。

而且这样子可以囊括所有二元组之间的关系，是不重不漏的。

第二种是树状数组，设 $a_i$ 表示以 $i$ 这个数字的出现次数，那么通过树状数组实现 $a$ 数组的单点修改区间查询就可以统计出出现在某个数之前的 $<$ 该数的数的个数，并产生贡献。

这两种做法都是普及组难度，然后是 $O(n\log n)$ 的，接下来我们看一个新的问题。

例2

简要题意

给你两个序列 $a, b$ ，问你满足 $i < j, a_i>a_j, b_i > b_j$ 的二元组 $(i, j)$ 个数。

思路

这个东西。。。好像归并排序和树状数组都不好搞吧（（

我们不妨大胆假设，既然这东西归并排序和树状数组都不好搞，那合并起来可以搞吗？

于是我们引出由 CDQ 发明的 CDQ分治。

我们先看看归并排序为什么能够实现二维逆序对，归并排序中通过左右区间中前者对后者产生贡献保证了原始下标的有序，又通过排序后的结果使得前面的元素对后面的元素产生贡献从而保证了权值的有序。

我们再看看树状数组为什么能够实现二维逆序对，树状数组通过访问顺序保证了下标的有序性，然后又通过数据结构直接查询满足某个通过访问顺序保证的条件的小于某个数的数的个数。

我们惊奇的发现，归并排序恰好确定了访问顺序，然后我们套一个树状数组就可以了

大概的流程就是，我们按照 $a$ 进行归并排序，那么最终序列内的 $a$ 是有序的，然后由于我们只算一边对另一边的贡献所以下标也是有序的，在次基础上我们把右区间中的数放入最终序列时对树状数组进行修改，那么左区间被放入时就可以方便地用树状数组查询得到当前最终序列中 $b$ 这一维 $<$ 该数的数的个数了，不难发现这样的数由于在右区间所以一定满足 $i < j$ ，归并排序由满足 $a_i > a_j$ ，最后树状数组又查出了 $b_i > b_j$ ，问题就解决了。