偏序关系
关系：
集合$X$的关系，是$X$与$X$的笛卡尔积$X × X$ 的子集R，即$X$的元素的有序对集合的一个子集
属于$X × X$的有序对$(a,b)$记为$aRb$
$R$的一些概念：
自反：$\forall x \in X, xRx $
对称：$\forall x, y \in X, xRy \rightarrow yRx $
传递：$\forall x, y, z \in X, xRy, yRz \rightarrow xRz $
偏序：
偏序关系：自反，反对称且传递 符号 $ \leq $
严格偏序：自反，反对称且传递 符号 $ < $
可比：$ \forall x, y \in X, xRy \vee yRx = true$
CDQ分治
我们暂且定义偏序中几个比较关系就是几维，如LIS是二维偏序
CDQ分治可以解决一类偏序问题，将多维的偏序问题减维
减维的原理：
通过规定用$[L,MID]更新[MID+1,R]$，使得在满足上一维顺序的同时可以对这一维进行排序来满足这一维的顺序
- 其他的减维手段还有排序和数据结构维护
二维偏序
通常用排序和数据结构维护就可以解决，如LIS，用CDQ分治强行做复杂度反而多一个log
但也有适合CDQ分治的，如逆序对。归并排序是CDQ的基础和最简单形式
三维偏序
可以用树套树或者CDQ分治+树
- 套路做法是第一维排序对其分治，第二维CDQ分治里排序，第三维用数据结构维护(常用树状数组)
因为前两维已经满足了，数据结构只维护一维就很简单了，常见区间和、区间最大值
常见形式：
目前遇到的三维偏序问题有两种形式
更新时不需要完整信息，可以把左更新右放到最后，如统计类问题
这类问题的排序可以使用归并排序，或者提前排序然后在分治里把序列分成两份(这时候递归调用写在最后)
$CDQ(l,r)$
$CDQ(l,mid) $
$CDQ(mid+1,r)$
$[l, mid] \rightarrow [mid+1, r]$
更新时需要完整信息，用左更新右后才可以递归右面，如最优化问题
这类问题通常需要在分治里单独排序$CDQ(l,r)$
$CDQ(l,mid) sort(l,r) $
$[l, mid] \rightarrow [mid+1, r]$
$CDQ(mid+1,r)$
复杂度分析:
基本就是以下两种复杂度:
$T(n)=2T(n/2)+O(kn)=O(knlogn)$
$T(n)=2T(n/2)+O(knlogn)=O(knlog^2n)$
常见用途:
数据结构题
在这类问题中通常将时间(操作序列)作为第一维，剩下的二维问题使用CDQ分治和数据结构，如Mokia，动态逆序对，天使玩偶，对应上文的第一种形式，注意必须要“修改独立”才行，强制在线GG
DP
(1)三维LIS
将序列编号作为第一维，分治里需要单独排序，感觉使用间接排序比较好,如SDOI2011拦截导弹
(2)斜率优化DP维护凸包
如：cash,WF2011 Machine Works
序列编号作为第一维，然后使用一种“先按斜率排序，分治时按序列编号(时间)分成两块再递归”的技巧
递归完$[l,mid]$后需要按x排好序，然后维护一个凸包
因为这时$[mid+1,r]$是斜率排好序的，在凸包上扫描一遍就可以了
为了避免精度问题可以使用叉积与点斜式
四维偏序:
CDQ分治套CDQ分治
$设四维a,b,c,d$
$sort \ at \ a $
$CDQ(l, r)$
$CDQ(l, mid)$
$CDQ(mid+1, r)$
$MergeSort\ at\ b, 每个元素标记属于[l,mid]还是[mid+1,r]$
$CDQ2(l, r)$
$CDQ2(l,r)$要做的和普通的三维偏序一样，就是多了一个标记的限制(来自CDQ中a的限制，必须用标记不能判断$a≤mid$，因为CDQ2是要递归下去的，mid就变了)
总结一下就是有一个序b和限制a，然后处理c,d的二维问题
复杂度$O(nlog^3n)$ ,每多套一个CDQ分治就多一个log
