离线分治主要是一类用于解决数据结构类型题目的算法，顾名思义，这种算法是一类离线解决问题的分治算法.
离线，意味着题目必须能够提前预知整个操作序列而不是只能回答一个操作后才能知道下一个操作，所以在线的题目就用不了这个算法啦，赶紧去写毒瘤有趣的树套树和可持久化数据结构吧！
离线分治算法主要有两种：cdq分治和整体二分.接下来写一下二分.
CDQ
CDQ问题的经典实现是偏序问题，即对于给定的ii有ai,bi,ci,..ai,bi,ci,.. 且有形如(下面)的条件，问满足条件的(i,j)(i,j)有几个
ai<aj
bi<bj
ci<cj
.....
算法思路
假如只有一维，我们容易想到直接排序即可，每个ii对它后面的数有贡献1(其实每个ii收到的贡献就是i，答案直接就是∑n1)。
假如有两维，我们先排序，把aiai当做下标，这就是经典的逆序对(顺序对)问题，我们这里只讨论顺序的情况！经典的方法之一是使用树状数组，每个bibi对大于它的bjbj有贡献，哈希记在树状数组里就行了，每次更新完树状数组后查询i位置的值，这就是贡献(因为前面的b′<bi才是a′<aii的)。
但是更常见的方法是使用归并排序bibi，用类似的思想，还是先按aa排序每次分治左右区间，回溯时统计左区间对右区间的影响(此时的左右区间是已经排序完了的，归并的过程中进来的是左边则tot++tot++，进来的是右边则ans+=tot，原理同上，因为归并只有每次的左边对右边答案的贡献，所以是不会重复的)
到了三维，我们是不是可以考虑把分治和树状数组联系起来搞一搞呢，一维排序，二维分治，三维树状数组，只是更新最后无脑tot++变成“归并的过程中进来的是左边则更新树状数组，进来的是右边则查询树状数组”
其实也可以只用分治，这种分治的名称就叫做CDQ分治，它的准确定义是用一个子问题去更新另一个子问题，于是它具有嵌套的能力，四五维偏序也可以搞了
画外音
其实很多时候，那种查询+更新二维区间的东西，看起来是两维其实这种东西是三维偏序！因为有一层隐藏的维度是时间，这时候不需要初始化排序了，直接做就行
写这种题要先把题目转化为最经典的模型，n维偏序，看着不等式写CDQ分治！
cdq分治是一种基于时间的离线分治算法，也就是说它是在对时间进行分治.