有各种分治：CDQ分治，树上分治，数据结构上分治，根号分治，etc.
普通分治
求逆序对
用归并排序求逆序对。
Sol：
其实逆序对是在归并排序时顺带求的，主要是归并排序。
我们要对区间\([l,r]\)从小到大排序，先对\([l,mid],[mid+1,r]\)排序（这一步体现分治思想）。
现在考虑怎么把两边合并。我们定义两个指针\(i,j\)分别指向左右两边最小的那个元素（由于排好序了，指向的就是第一个）,依次从\(i,j\)指向的两个元素中选较小的一个加入到答案序列中，并将其所对应的指针往后移即可。
求最大子段和
求当前区间\([l,r]\)的最大子段和。
Sol：
先将当前区间分成两边\([l,mid],[mid+1,r]\)。
考虑将两边的区间合并得到答案。
发现只维护每个区间的最大子段和不够，再维护最大前缀和,最大后缀和与区间和。
合并时维护区间的最大前缀和\(lmx\)，最大后缀和\(rmx\)，区间和\(sum\)与最大子段和\(val\)。
这个分治操作可以搞到线段树上，这是简单的。
求关于所有区间的信息
发现关于所有区间的信息是\(O(n^2)\)的，于是尝试通过分治降到\(O(n\log n)\)。
每次分治后只需考虑跨过区间中点的区间的答案，考虑合并得到这个答案，一般是处理左边区间的后缀信息，右边区间的前缀信息，然后尝试合并，再简化合并的过程，通过分析一些关于答案的性质来快速计算。