CDQ 分治

作者: ffacs 分类: 总结 发布时间: 2020-04-30 10:09

逆序对-梦开始的地方

题目:给定序列$s,|s|\leq 1e5$,求序列中逆序对的数量

一种解法当然是离散化以后用树状数组求啦.

另外一种方法就是 归并排序,采用分治的思想,一个区间中全部的逆序对数等于左区间的逆序对数+右区间的逆序对数+对右区间中每一个数左区间中比它小的数的个数.

其实逆序对可以看成二维偏序.我们把每个元素$s[i]$换成二元组$a,b$,其中$a$就是元素的下标,$b$是元素的值.那么我们求逆序对其实就是求出了 对于每一个$j$, $a_ib_j$的$i$的数量的和.

二维偏序

有$n \leq 1e5$个二元组$(a,b)$,对于每一个二元组,求$a_i \le a \wedge b_i \le b$ 的个数.

第一种解法:首先很自然地对$a$排序,那么对于一个元素我们要找的就是排在他前面的并且$b_i \le b$ 的,或者后面等于自己的.前面的并且$b_i \le b$ 的,我们只需要树状数组维护一下即可.

第二种解法:还是像第一种解法一样排序,还是前面$b$比自己小的+后面等于自己的,但是不用树状数组求,而是用求逆序对的方法求.求逆序对的方法求的就是前面有多少比自己大的,我们只要稍加改造就能做了.

三维偏序

有$n \leq 1e5$个三元组$(a,b,c)$,对于每一个二元组,求$a_i \le a \wedge b_i \le b \wedge c_i < c$ 的个数.还是同样的思路,按$a,b,c$排序,那么每个数要求的就是前面$b,c$比自己小的+后面和自己相等的.我们发现求二位偏序使用归并排序方法的时候$b$的访问是有序的,那么我们只要再加上一个树状数组维护第三维的前缀和就能完成三位偏序了.

四维偏序

第一维排序,第二维CDQ,只要求三四维小于自己的,这个可以再用一次CDQ求出.

发表评论

电子邮件地址不会被公开。 必填项已用*标注