CDQ分治【使用说明书】

适用范围

cdq分治，用于解决各类动态（包含修改操作）的离线问题，在此方面可以用于替代复杂的数据结构，实现更简单的解法。

对口的问题通常由一些修改和查询操作组成。

注：本产品老少咸宜，患有高血压、低血糖者均可使用。
   本产品口服、外敷均可，推荐搭配c++食用，口感更佳。

生效原理

这玩意略显抽象，似乎大多都用例题来具体解释

将要解决的多个操作排成一个序列：\(Q_1,Q_2,Q_3,\cdots,Q_n\)

可以对这个序列进行分治，递归处理\([1,mid]\)，\([mid+1,n]\)的问题
（实际上左右界不一定是\(1\)和\(n\)，用\(l,r\)表示更准确些）

具体的问题在于如何合并左右区间。合并过程中应当确保每个询问的情况都被维护好。我在说什么
事实上，我们只需要在合并过程中，维护好左区间修改对右区间查询的影响即可。（因为是左右有序的）这一点和普通分治不同。

有一篇博客写道：详见《算法竞赛进阶指南》，
看书的时候似乎没看到这一章，可惜笔者此时此地翻不了书QAQ
确实是写的挺好的一本书，推荐去看
当然，书也只是更系统一点，如果有足够的资料就不必要了

好吧，确实有点抽象，所以来点例题！

使用范例

三个维偏序问题

指一维偏序、二维偏序和三维偏序（bushi）

一维偏序问题（逆序对问题）

也就是归并排序。归并排序昨天写在mys了，晚点搬运过来然后贴个链接吧。
（待续）

二三维偏序问题

懒得写了（不要啊）
二维偏序传送门
其实还得是某OJ啊
三维偏序传送门

其他例题（待续）

后记

虽说好像现在才正式学习、写笔记什么的。

但其实很早就在某OJ做过二维偏序了，只是当时不知道“CDQ分治”这么个东西。
L('ω')┘某OJ好耶└('ω')｣

说起来，OI算法本来也不那么正式吧

所以学习最重要的是学思想嘞。