P13520 [KOI 2025 #2] 存放箱子 题解 / Dilworth 定理学习笔记
:::::info[闲话]{open}
来一篇严谨证明题解！
:::::
:::::info[题目基本信息]
考察：Dilworth 定理，线段树（提高+/省选-）。
题目简介：
给定
数据范围：
-
2\le n\le 2\times 10^5 -
\forall i\in[1,n],1\le c_i<s_i\le 10^9 ::::: 我们定义
a\preceq b 表示a 可以包含b 或a=b ，然后我们对下面的性质做证明： - 自反性：
a\preceq a 。 :::::success[证明] 根据定义容易得出。
::::: - 反对称性：
a\preceq b\land b\preceq a\Rightarrow a=b 。 :::::success[证明] 考虑证明它的逆否命题a\ne b\Rightarrow a\npreceq b\lor b\npreceq a ，考虑反证证明a\ne b\land a\preceq b\land b\preceq a 不成立，我们可以得到s_a\le c_b<s_b\le c_a<s_a ，显然不成立。 ::::: - 传递性：
a\preceq b\land b\preceq c\Rightarrow a\preceq c 。 :::::success[证明] 若a=b\lor b=c ，那么等量代换一下显然成立。
否则我们得到s_a\le c_b<s_b\le c_c ，进一步得出a\preceq c 。
::::: 那么a\preceq b 是偏序，设偏序集为S=[1,k]\cap\mathbb Z ，那么我们应用 Dilworth 定理（参考 oiwiki，但给出了自认为更严谨更详细的证明）。
:::::success[Dilworth 定理]::::: :::::success[证明] 考虑数学归纳法。 若 $|S|\le 3$，暴力枚举验证发现确实成立。 假设偏序集大小小于 $|S|$ 的偏序集均成立，若 $S$ 内的元素两两不可比（$\forall u,v\in S,u\ne v\Rightarrow u\npreceq v\land v\npreceq u$），那么命题显然成立，否则取一条长度不为 $1$ 的链 $P$，设最小元（$\forall p\in P,v\preceq p$）为 $v$，最大元（$\forall p\in P,p\preceq v$）为 $V$。 再设 $T=S\backslash\{v,V\}$，如果 $T$ 的最长反链小于 $S$，那么由于 $v\preceq V$ 所以两者不位于同一反链，那么最长反链长度为 $S$ 的最长反链长度减 $1$，那么根据假设 $T$ 的最小链覆盖数等于最长反链，那么由于 $S$ 到 $T$ 扔掉了两个点，那么 $S$ 的最小链覆盖数会等于 $T$ 的最小链覆盖数加 $0,1$ 或 $2$。 - 不会是
2 ：
若S 的最小链覆盖数等于T 的最小链覆盖数加2 ，那么将T 的最小链覆盖加上一条\{v,V\} 就会得到更小的链覆盖数，产生矛盾。 - 不会是
0 ：
若S 的最小链覆盖数等于T 的最小链覆盖数，传递一下得到S 的最小链覆盖数等于S 的最长反链长度减1 ，但是S 的这条反链内的元素一定两两不位于一个链，产生矛盾。
故
当
对
证毕。
:::::
好的我们将这个问题转化为最长反链，我们注意到对于
然后我们就做完了此题。
时间复杂度为
code