cdq分治 笔记

博客观赏效果更佳：
github
cnblogs

算法讲解

这个算法用于解决三维偏序问题。

三维偏序：给定 $n$n 个三元组： $(a_i,b_i,c_i)$(ai​,bi​,ci​)，求同时满足满足 $a_i\le a_j,b_i\le b_j,c_i\le c_j$ai​≤aj​,bi​≤bj​,ci​≤cj​ 的 $(i,j)$(i,j) 的数量。

那这该咋求呢⊙(・◇・)？

先把维度降下来，二维偏序，会不会做？就是求多少个 $(i,j)$(i,j) 满足 $a_i\le a_j,b_i\le b_j$ai​≤aj​,bi​≤bj​。

显然，先按照 $a$a 排一下序。然后就变成了 $i<j,b_i\le b_j$i<j,bi​≤bj​ 的问题了。可以用树状数组做。最典型的案例就是逆序对问题，这个都写熟练了哈(*╹▽╹*)

三维偏序的问题，也是先按 $a$a 排一下序。然后接下来的问题考虑分治（这样的分治过程被我们称为“cdq分治”）

假设我们要求 $[l,r]$[l,r] 中的答案。已经求好了 $[l,mid],[mid+1,r]$[l,mid],[mid+1,r] 中的答案，现在只需要考虑跨区的答案了。

那么我们可以把 $[l,mid]$[l,mid] 和 $[mid+1,r]$[mid+1,r] 内部都按照 $b$b 排序。因为我们只要考虑跨区的答案，那么我们把两边分别都随便排序，对跨区的时候 $a$a 的大小关系没有影响。然后我们在 $[mid+1,r]$[mid+1,r] 中枚举一个元素 $j$j，找到在 $[l,mid]$[l,mid] 中有多少个 $i$i 满足 $b_i\le b_j$bi​≤bj​，然后这个 $i$i 显然是递增的。然后我们一边单调的维护这个 $i$i ，一边用树状数组维护 $c_i\le c_j$ci​≤cj​ 的数量即可。

板子

洛谷3810 陌上花开

（↑代码找我老婆要）（那张图是一个链接(*^▽*)）（偷偷测试功能）