[偏序关系与CDQ分治]【学习笔记】

组合数学真是太棒了

$CDQ$真是太棒了(雾

---

参考资料：

1.《组合数学》

2.论文 课件 很容易查到

3.sro __stdcall

---

偏序关系

关系：

集合$X$上的关系是$X$与$X$的笛卡尔积$X \times X$的子集$R$
即$X$的元素的有序对集合的一个子集
属于$X \times 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$

偏序$Partial order$：

偏序关系 ：自反，反对称且传递，符号$<$

严格偏序 ：反自反，反对称且传递，符号$\le$，如$LIS$

偏序集 ：$(X,\le )$  如：集合包含，整除

可比 $:\ \forall x,y \in X,\ xRy \lor yRx=true$

全序 $:\ $每一对元素都可比

链 $chain:\ X$的一个子集，每一对元素都可比

反链 $antichain:\ X$的一个子集，任意两个元素都不可比

极小元和极大元 ：不存在更小/更大的元素

偏序集的极小元集合和极大元集合都是反链

链与反链有 对偶性 ；$A \bigcap C \le 1$

$Dilworth$定理：

$1.\ $最少反链个数等于最长链大小

$2.\ $最少链个数等于最长反链大小

证明：
只证明$1$ , $2$太长了不(我)想(没)写(看)

设最长链长度$r$

首先反链个数不可能更少是显然的，因为最长链里每一个元素必须在不同的反链里；

现在证明可以划分成$r$个反链,通过不停的在$X$中删除最小元集合，后删除的集合中的每个元素一定比先删除的集合中的某个元素大，这样形成一条链。设一共删除$p$次，容易得到$ p \le r \land p \ge r $, 因此 $ p=r $

---

$CDQ$分治

注：以下主要为个人理解

我们暂且定义偏序中几个比较关系就是几维，如$LIS$是二维偏序

$CDQ$分治可以解决一类偏序问题，将多维的偏序问题减维

减维的原理 ：

通过规定用$[L,MID]$更新$[MID+1,R]$，使得在满足上一维顺序的同时可以对这一维进行排序来满足这一维的顺序

其他的减维手段还有 排序 和 数据结构维护

二维偏序

通常用排序和数据结构维护就可以解决，如$LIS$，用$CDQ$分治强行做复杂度反而多一个$log$

但也有适合$CDQ$分治的，如逆序对。归并排序是$CDQ$的基础和最简单形式

三维偏序

可以用树套树或者$CDQ$分治$+$树，(然而$Candy?$蒟蒻并不擅长写树套树只会$CDQ$)

套路做法是第一维排序对其分治，第二维$CDQ$分治里排序，第三维用数据结构维护(常用树状数组)

因为前两维已经满足了，数据结构只维护一维就很简单了，常见区间和、区间最大值

常见形式：

目前遇到的三维偏序问题有两种形式

$1.$更新时不需要完整信息，可以把左更新右放到最后，如统计类问题

这类问题的排序可以使用归并排序，或者提前排序然后在分治里把序列分成两份(这时候递归调用写在最后)

$CDQ(l,r)$

$\ CDQ(l,mid)\ CDQ(mid+1,r)$

$\ [l,mid] \rightarrow [mid+1,r]$

$2.$更新时需要完整信息，用左更新右后才可以递归右面，如最优化问题

这类问题通常需要在分治里单独排序

$CDQ(l,r)$

$\ CDQ(l,mid)\ sort(l,r)$

$\ [l,mid] \rightarrow [mid+1,r]$

$\ CDQ(mid+1,r)$

复杂度分析

根据主定理：

$T(n)=2T(\frac{n}{2})+O(kn)=O(knlogn)$

根据算法导论上的练习题

$T(n)=2T(\frac{n}{2})+O(knlogn)=O(knlog^2n)$

常见用途：

$1.$数据结构题

在这类问题中通常将时间(操作序列)作为第一维，剩下的二维问题使用$CDQ$分治和数据结构

如$Mokia$，动态逆序对，天使玩偶

对应上文的第一种形式

注意必须要“修改独立”才行

如果强制在线我就只有等死了

$2.\ DP$

$(1)$三维$LIS$

将序列编号作为第一维，分治里需要单独排序，感觉使用间接排序比较好

如$SDOI2011$拦截导弹

$(2)$斜率优化$DP$维护凸包

感觉比用平衡树好多了($Candy?$蒟蒻并没有写过用平衡树维护)

如：$cash$,$WF2011\ Machine\ Works$

序列编号作为第一维，然后使用一种“先按斜率排序，分治时按序列编号(时间)分成两块再递归”的技巧

递归完$[l,mid]$后需要按$x$排好序，然后维护一个凸包

因为这时$[mid+1,r]$是斜率排好序的，在凸包上扫描一遍就可以了

为了避免精度问题可以使用叉积与点斜式

四维偏序

$CDQ$分治套$CDQ$分治

设四维$a,b,c,d$

$Sort\ at\ a$

$CDQ(l,r)$

$\quad CDQ(l,mid)$

$\quad CDQ(mid+1,r)$

$\quad MergeSort\ at\ b$ 每个元素标记属于$[l,mid]$还是 $[mid+1,r]$

$\quad CDQ2(l,r)$

$CDQ2(l,r)$要做的和普通的三维偏序一样，就是多了一个标记的限制(来自$CDQ$中$a$的限制，必须用标记不能判断$a \le mid$，因为$CDQ2$是要递归下去的，$mid$就变了)

总结一下就是有一个序$b$和限制$a$，然后处理$c,d$的二维问题

复杂度$O(nlog^3n)$ ,每多套一个$CDQ$分治就多一个$log$

100维偏序

$O(100*N^2)$暴力就好了.....

---

总结：

$CDQ$分治结束啦~\(≧▽≦)/~

虽然课件上还有一些题下个月再做吧

明天看一下整体二分然后就开始仔细研究组合数学了