Copyright By

注意事项

讲评人没有实力，也没有烤鸭皮皮，所以对于接下来提到的一些结论将不予证明，感兴趣的可以自己bdfs一下，或者课后询问讲评人

部分定义不准确，并不形式化，是讲评人自己思考后的结果

如果觉得自己的想法与讲评人有不同或者算法更优，可提出自己的见解

介绍

此算法源自巨佬陈丹琦（有人真的面向到对象了我不说是谁）

CDQ分治是一种思想，并没有具体板子，可以代替一些复杂的数据结构（所以说FHQtreap和树套树能不能死一死啊）

讲评人已破防

前置

分治

分治是一种非常常用的思想（例如快排归并都是这种思想）

见书P337

例题

由于cdq分治的形式化做法，书上讲的很乱，所以这里用一道经典例题讲解。

三维偏序

P3810 【模板】三维偏序

CDQ 分治 - OI Wiki

cdq可以很容易的处理这些类似逆序对的问题

对于整个序列，首先以a为关键字排序，再对b离散化，这样问题就转变为：

对于一个序列，求有多少个数对，满足$i\leq j,b[i]\leq b[j],c[i]\leq c[j]$

对于区间l~r

先二分为l~mid，mid+1~r

对于两个子区间递归处理

接下来考虑两个子区间之间的答案数

根据b排序，左边根据依次插入从c[i]到树状数组，然后用类似与统计逆序对的操作处理就可以了

是不是听着很痛骨，没事接下来看模拟

先润啦886