Zirnc's Blog
Recent content on Zirnc's Blog
马上订阅 Zirnc's Blog RSS 更新: https://blog.chungzh.cn/index.xml
CDQ 分治笔记
基本思想
CDQ 分治的基本思想十分简单。如下：
- 我们要解决一系列问题，这些问题一般包含修改和查询操作，可以把这些问题排成一个序列，用一个区间 $[L,R]$ 表示。
- 分。递归处理左边区间 $[L,M]$ 和右边区间 $[M+1,R]$ 的问题。
- 治。合并两个子问题，同时考虑到 $[L,M]$ 内的修改对 $[M+1,R]$ 内的查询产生的影响。即，用左边的子问题帮助解决右边的子问题。
这就是 CDQ 分治的基本思想。和普通分治不同的地方在于，普通分治在合并两个子问题的过程中，$[L,M]$ 内的问题不会对 $[M+1,R]$ 内的问题产生影响。
前置知识：二维偏序
给定 $N$ 个有序对 $(a,b)$，求对于每个 $(a,b)$，满足 $a2<a$ 且 $b2<b$ 的有序对 $(a2,b2)$ 有多少个。
可以将归并排序求逆序对的思路套用过来，这题实际上就是求顺序对。首先根据 $a$ 的大小排序，然后归并排序 $b$，这样就可以忽略 $a$ 元素的影响，因为左边区间的元素的 $a$ 一定小于右边元素的 $a$。归并排序时，每次从右边区间的有序序列取一个元素，然后求左边区间多少个元素比它小即可。
更浅显的解法是，用树状数组代替 CDQ 分治。这里就不赘述。
放个求逆序对的代码：
|
|