第 111 章　偏序集与 Dilworth 定理

配套例题：BISHI133 最长不下降子序列、BISHI9 田忌赛马 来源：S3 day5《贪心》第 21–83 页（导弹拦截 / 偏序集 / Hasse 图 / 链与反链 / Mirsky 定理 / Dilworth 定理） 前置：102-线性DP、47-贪心

111.0　这一章为什么存在

S3 day5 的课件在讲贪心时，用了整整 60 页来铺垫一个东西：为什么「导弹拦截」的第二问 （最少需要几套系统）的答案，等于第一问的对偶——最长上升子序列的长度。

这个结论在很多题解里被写成一句「Dilworth 定理，直接上」，然后就没有然后了。 课件不一样，它老老实实地把偏序集、Hasse 图、链、反链、Mirsky 定理、Dilworth 定理 一路推了下来，还给出了两个定理的完整归纳证明。

牛客题单里没有导弹拦截原题，所以这套理论没被直接考。 但它值得单独成章，因为：

理由	说明
解释了一大类「最少覆盖」题的答案	「最少多少个不上升子序列覆盖」= 「最长上升子序列」
给了一个通用的建模语言	二维偏序、三维偏序、LIS、导弹拦截、盒子套盒子，都是同一个模型
是 118 章 的理论前置	CDQ 分治处理的就是「三维偏序」
一旦考到就是送分	认出模型 = 一行代码；认不出 = 想破头

---

111.1　起点：导弹拦截

课件引用的原题是 NOIP 1999 / 洛谷 P1020：

某国研发出一套导弹拦截系统，缺陷是：第一发炮弹能达到任意高度， 但以后每一发的高度都不能超过前一发。 敌国 \(n\) 颗导弹依次飞来，雷达侦测出每颗的高度。 1. 如果只有一套系统，最多能拦截多少颗导弹？ 2. 至少要多少套系统才能拦截所有导弹？

第一问显然是最长不上升子序列（LNIS）。第二问看起来完全不同， 但答案是：最长上升子序列（LIS）的长度。

第一次见到这个结论的人都会问：凭什么？

---

111.2　偏序集

课件第 24–25 页给的定义：

偏序集 \(P = (S, \le)\) 由集合 \(S\) 和二元偏序关系 \(\le\) 组成 （这不特指小于等于，只是一个形象表示），并且满足以下条件： 1. 自反性：对于任意 \(a \in S\)，满足 \(a \le a\)； 2. 反对称性：对于任意 \(a, b \in S\)，如果 \(a \le b\) 并且 \(b \le a\)，那么 \(a = b\)； 3. 传递性：对于任意 \(a, b, c \in S\)，如果 \(a \le b\) 并且 \(b \le c\)，那么 \(a \le c\)。

如果 \(a \le b\) 或者 \(b \le a\)，那么称 \(a\) 与 \(b\) 是可比较的，否则是不可比的。

课件给了两个例子：

偏序集	关系	特点
\(P = (\mathbb{Z}, \leqslant)\)	普通的小于等于	任意两元素可比（这叫全序）
\(P = (S, \mid)\)，\(S = \{1,2,3,4,6,9,12,18,36\}\)	整除	\(2\) 和 \(3\) 不可比（互不整除）

「偏」字的含义就在这里：全序里任意两个元素都能比大小； 偏序里允许存在「谁也不比谁大」的元素对。 竞赛中的偏序几乎都是多维比较：\((a_1,b_1) \le (a_2,b_2)\) 当且仅当 \(a_1 \le a_2\) 且 \(b_1 \le b_2\)——只要有一维反着，两者就不可比。

---

111.3　Hasse 图

课件第 26 页：

不得不承认的是，偏序集这个概念相当抽象。 为了简单明了地表示偏序集，Hasse 首先使用拓扑图来表示偏序集中的比较关系。 在 Hasse 图中，集合 \(S\) 中每个元素代表图中一个点。如果 \(a < b\) 且不存在 \(c\) 使 \(a < c < b\)，那么 Hasse 图中就有一条 \(a \to b\) 的边。

关键是那个加粗的条件：Hasse 图只画「直接覆盖关系」，传递闭包出来的边要删掉。 课件第 29 页专门给了反例：

右图是不正确的 Hasse 图，因为红色边应该被删去。

以 \(S = \{1,2,3,4,6,9,12,18,36\}\)、关系为整除为例：

              36
             /  \
           12    18
          /  \  /  \
         4    6      9
          \  / \    /
           2     3
            \   /
              1

\(1 \to 36\) 这条边不能画，因为存在 \(1 < 2 < 36\)。

Hasse 图一定是有向无环图（DAG）：如果有环，环上元素两两 \(\le\)， 由反对称性它们全相等，矛盾。所以偏序集上的问题都可以用 DAG 上的 DP 来做。

---

111.4　链与反链

课件第 34–38 页：

对于偏序集 \(P = (S, \le)\)，链（chain）\(C = [c_1, c_2, \dots, c_k]\) 是一个序列， 满足 \(c_1 < c_2 < \cdots < c_k\)。链 \(C\) 中任意两个元素都是可比的。

反链（antichain）\(A = [a_1, a_2, \dots, a_k]\) 也是一个序列， 但是反链中任意两个元素均不可比。

用许多条不相交的链覆盖所有节点称为链覆盖。同理，使用不相交的反链覆盖所有节点 称为反链覆盖。

概念	定义	Hasse 图上的直觉
链	两两可比	一条自下而上的路径
反链	两两不可比	一层「横着的」点集
链覆盖	用若干不相交的链盖住所有点	把 DAG 拆成若干条路径
反链覆盖	用若干不相交的反链盖住所有点	把 DAG 分层

于是有四个自然的量：

记号	含义
\(d\)	最长链的长度
\(m\)	最小反链覆盖中反链的条数
\(w\)	最长反链的长度
\(c\)	最小链覆盖中链的条数

两个定理各管一对：

\[\boxed{\text{Mirsky 定理：} \; m = d} \qquad \boxed{\text{Dilworth 定理：} \; c = w}\]

---

111.5　把序列翻译成偏序集

课件第 42–43 页做的这一步，是整章的枢纽：

对于一个序列 \(A[1..n]\)，将每个位置的下标和元素值关联起来得到二元组 \((k, A[k])\)。 定义二元关系 \((i, A[i]) \le (j, A[j])\) 成立当且仅当 \(i \leqslant j\) 并且 \(A[i] \leqslant A[j]\)。 之所以这么定义，是因为不下降子序列中相邻两个元素刚好满足这种关系。

令 \(S = \{(k, A[k]) : 1 \leqslant k \leqslant n\}\)，构造偏序集 \(P = (S, <)\)， 不难发现每个单调递增子序列对应偏序集中一条链。 进一步验证可以发现，每个不上升子序列对应偏序集中一条反链。

把这两句话拆开看：

序列上的对象	偏序集上的对象	为什么
不下降子序列 \(A[i_1] \le A[i_2] \le \cdots\)（\(i_1 < i_2 < \cdots\)）	链	相邻两项满足 \(i\) 增、\(A\) 增 → 可比
不上升子序列 \(A[i_1] \ge A[i_2] \ge \cdots\)（\(i_1 < i_2 < \cdots\)）	反链	\(i\) 增但 \(A\) 减 → 两个维度反着 → 不可比

这个转化是全章最需要理解的一步： 「下标增、值也增」= 可比 = 链； 「下标增、值却减」= 不可比 = 反链。 单调子序列问题 = 偏序集的链/反链问题，一一对应。

---

111.6　Mirsky 定理

Mirsky 定理：偏序集的最小反链覆盖中反链条数等于最长链的长度。即 \(m = d\)。

课件给的证明

课件第 54 页的完整证明（记号照抄，措辞略作整理）：

设 偏序集 \(P = (S, \le)\)，对于 \(x \in S\)，令 \(f(x)\) 表示从 \(x\) 开始的最长链的长度。

第一步：\(f\) 可以算。 因为 \(P\) 的 Hasse 图是一张拓扑图（DAG），所以可以采用 DP 的方式算出 \(f(x)\)。 记 \(f(x)\) 的最大值（即最长链长度）为 \(d\)，最小反链覆盖中反链条数为 \(m\)。

第二步：\(f\) 值相同的点两两不可比。 考虑两个不同的点 \(x\) 和 \(y\)，如果 \(f(x) = f(y)\)，那么说明 \(x\) 和 \(y\) 不可比—— 否则（不妨设 \(x < y\)）DP 过程中 \(y\) 可以更新 \(x\)，得到 \(f(x) \ge f(y) + 1 > f(y)\)，矛盾。

第三步：构造反链覆盖。 记 \(F(n) = \{x : f(x) = n,\ \forall x \in S\}\)，即 \(f\) 的「反」函数。 根据第二步，如果 \(F(n)\) 不为空，则 \(F(n)\) 构成一条反链。 因此 \(F(1), F(2), \dots, F(d)\) 是偏序集 \(P\) 的一个反链覆盖。 注意 \(F(1)\) 到 \(F(d)\) 中可能有空集，所以这里只能得出

\[m \leqslant d\]

第四步：反向不等式。 根据链和反链的定义，一条链上任意两个点不可能同时处在同一条反链中 （链上的点两两可比，反链要求两两不可比）。 所以在任意一个反链覆盖中，最长链上的每一个点必定分属不同的反链，于是

\[m \geqslant d\]

综上 \(m = d\)。\(\blacksquare\)

这个证明的可操作性非常强：第三步的 \(F(n)\) 直接给出了构造方法—— 按「从自己出发的最长链长度」给每个点分层，每一层就是一条反链。 很多「最少分几组」的构造题可以照这个思路给出方案，而不只是给出数量。

回到导弹拦截

课件第 47 页：

回到导弹拦截问题，一套系统能拦截的导弹是一个不上升子序列，也就是一条反链。 现在要用最少的系统拦截所有导弹，相当于一个最小反链覆盖。 根据 Mirsky 定理，最小反链覆盖的大小等于最长链的长度——最长的单调递增子序列的长度。

于是：

\[\text{最少需要的系统数} = \text{最长严格上升子序列的长度}\]

于是「导弹拦截」这道两问的题，两问都是 LIS，写两遍同一个模板就完事：

问	要求的东西	偏序集语言	代码
第一问：一套系统最多拦几颗	最长不上升子序列	最长反链	序列取负后求最长不下降
第二问：最少要几套系统	最少不上升子序列覆盖	最小反链覆盖	最长严格上升子序列

第二问的推导链条是：一套系统 = 一条反链 → 「用最少的系统拦下全部」= 最小反链覆盖 → Mirsky 定理把它换成最长链 → 链在序列上就是严格上升子序列。 整个过程没有任何新算法，只是把问题翻译了两次。

注意「严格」与「不严格」的对应关系必须成对翻转，这是本章最容易错的地方：

一套系统能拦的	最少套数 =
不上升子序列（允许相等）	严格上升子序列的最长长度
严格下降子序列	不下降子序列的最长长度

判断依据：把「一套系统内允许的关系」取反，就是链要求的关系。 「不上升」的反面是「严格上升」，「严格下降」的反面是「不下降」。 弄反了会 WA，且样例往往看不出来。

---

111.7　Dilworth 定理

Dilworth 定理：最小链覆盖中链的条数等于最长反链的长度。即 \(c = w\)。

先建立直觉

两边各自的含义摆出来，等号就不神秘了：

• \(c \ge w\) 是显然的（这一半随时能自己推出来）。 反链上的元素两两不可比，而一条链上的元素两两可比， 所以一条链最多吃下反链里的一个元素。 有 \(w\) 个元素必须分到不同的链里，链数当然至少是 \(w\)。
• \(c \le w\) 才是定理的内容：它断言「最长反链」这个下界总能取到， 不存在「明明反链只有 5，却非要 6 条链才盖得住」的偏序集。

换成大白话：最长反链是唯一的瓶颈。 拆分一个偏序集时，逼着你多开一条链的原因只有一个——有一撮元素两两不可比； 而这撮元素最多有多少个，答案就是多少。

同一句话在 Mirsky 定理那边镜像成立：最长链是分层的唯一瓶颈。 两个定理都在说「某个显而易见的下界恰好是紧的」， 这也是它们能把「最少要几组」这类问题一句话解决的原因。

这和 Mirsky 定理有什么区别？

课件第 63 页专门讨论了这一点，答案很有意思：

对于偏序集 \(P_1 = (S, \le)\) 和偏序集 \(P_2 = (S, >)\) 而言，这两个定理几乎是等价的， 因为 \(P_1\) 中的一条链就是 \(P_2\) 中的一条反链，反之亦然。

但是对于所有的偏序集都可以找到这样的对偶吗？并非如此。 还是整除的老例子，考虑偏序集 \(P = (\{1,2,\dots,n\}, \mid)\)，该如何对应呢？ 之所以 \(\le\) 可以对应，是因为 \(\le\) 的反面就是 \(>\)，并且两者都满足偏序集的三个要求。 而现在 \(\nmid\) 根本不满足传递性： $\(2 \nmid 3 \text{ 且 } 3 \nmid 4 \; \not\Longrightarrow \; 2 \nmid 4\)$ 但是不管怎么样，它依然是个定理。不过证明方法有些不同。

这一段值得记住：在「二维数对」这种偏序集里， Mirsky 和 Dilworth 互为对偶，用哪个都行； 但在整除、包含之类的一般偏序集里，两者不能互相推导，必须分别使用。

课件给的证明（对 \(|S|\) 归纳）

设 偏序集 \(P = (S, \le)\)，最长反链长度为 \(d\)，最少需要 \(c\) 条链才能覆盖偏序集。

易证的一半：由于反链中任意两个元素不可能出现在同一条链里面， 所以对于任意一个链覆盖，反链中每个元素必定处于不同的链中，于是 \(c \geqslant d\)。

难的一半：构造出 \(d\) 条链的覆盖。对 \(|S|\) 归纳。

• 奠基：\(|S| = 0\) 和 \(|S| = 1\) 时显然成立； \(P\) 的 Hasse 图中没有边时，所有点两两不可比，\(d = |S|\)，每个点各成一条链，成立。
• 归纳假设：对 \(|S| = 0, 1, \dots, n-1\) 均成立。

• 归纳步骤：考虑 \(|S| = n\)。选取一个极大值 \(M\)（即不存在 \(x \in S\) 满足 \(M \le x\) 且 \(x \ne M\)） 和一个极小值 \(m\)，并且 \(m \le M\)。注意到 \([m, M]\) 构成了一条链。 将 \(m\) 和 \(M\) 从偏序集中删去，得到 \(P'\)。由于它们构成了一条链， 所以 \(m\) 和 \(M\) 不可能同时在最长反链中，所以最长反链的长度最多减 1。

• 情况一：如果 \(P'\) 的最长反链长度为 \(d - 1\)，根据归纳假设，\(P'\) 有一个大小为 \(d-1\) 的链覆盖。 把链 \([m, M]\) 加进去，就得到了一个大小为 \(d\) 的链覆盖。归纳成立。

• 情况二：\(P'\) 的最长反链长度仍是 \(d\)。取 \(P'\) 中的一条最长反链 \(A\)（\(|A| = d\)）， 用它把偏序集切开，定义

  \[S_+ = \{x : \exists a \in A,\ a \le x\},\qquad S_- = \{x : \exists a \in A,\ x \le a\}\]

  \(S_-\) 是 Hasse 图的下半截，\(S_+\) 是上半截。需要确认三件事：

  1. \(S_- \cup S_+ = S\)——即上述划分确实包含了 \(S\) 的所有元素。 理由：如果存在 \(x \notin S_- \cup S_+\)，则说明 \(x\) 与 \(A\) 中所有元素均不可比， 此时反链 \(A\) 还可以加入 \(x\)，与 \(A\) 是最长反链矛盾；
  2. \(A = S_- \cap S_+\)；
  3. \(S_+\) 和 \(S_-\) 都缺少 \(m\) 或者 \(M\)，即大小比 \(|S|\) 小。

  注意到偏序集 \(S_+\) 和 \(S_-\) 都有最长反链 \(A\)，并且根据第三条性质它们的规模都严格小于 \(|S|\)， 因此可以利用归纳假设分别得到 \(S_+\) 和 \(S_-\) 的大小为 \(d\) 的最小链覆盖。

  对于 \(S_+\) 的链覆盖中的 \(d\) 条链，不难证明链的底端一定是 \(A\) 的元素； 对于 \(S_-\) 也是类似的（链的顶端是 \(A\) 的元素）。 因此可以用 \(A\) 中的元素作为中介，把 \(S_-\) 和 \(S_+\) 的两个链覆盖接起来， 得到一个大小为 \(d\) 的链覆盖。\(\blacksquare\)

为什么这个证明比 Mirsky 的复杂得多：Mirsky 定理的分层函数 \(f\) 是「天然存在」的， 而 Dilworth 定理必须构造链覆盖，链之间会互相牵制。 这也解释了 111.7 开头那段——两者不是简单的对偶关系。

Dilworth 定理在序列上的形态

把 111.5 的翻译反过来用：

\[\text{最少用几个「不下降子序列」覆盖整个序列} = \text{最长严格下降子序列的长度}\]

覆盖用的子序列类型	答案 = 最长的
不下降	严格下降子序列
严格上升	不上升子序列
不上升	严格上升子序列
严格下降	不下降子序列

记忆口诀：把类型「严格化 / 松弛化 + 方向反转」一次。

---

111.8　最长上升子序列的 \(O(n\log n)\) 写法

上面所有定理最终都落到一件事上：求某种单调子序列的最长长度。 \(O(n^2)\) 的 DP 见 102-线性DP，这里给贪心 + 二分的版本。

# [片段]
from bisect import bisect_left, bisect_right


def lis_strict(a):
    """最长**严格上升**子序列的长度。O(n log n)。"""
    tails = []                       # tails[i] = 长度 i+1 的上升子序列的最小结尾
                                     # 每个长度只留最小的结尾，后面才最容易接得下去
    for v in a:
        i = bisect_left(tails, v)    # ★ 严格上升用 bisect_left
                                     # 定位到第一个 >= v 的位置：它接不动 v，正好被替换
        if i == len(tails):
            tails.append(v)          # v 比所有结尾都大，能把最长的那条再延长一位
        else:
            tails[i] = v             # 否则把这个长度的结尾换成更小的 v，长度不变
    return len(tails)                # tails 的长度即答案；它本身不是任何一条真实子序列


def lnds(a):
    """最长**不下降**子序列的长度。O(n log n)。"""
    tails = []
    for v in a:
        i = bisect_right(tails, v)   # ★ 不下降用 bisect_right（相等可以接上去）
                                     # 跳过所有等于 v 的结尾，让 v 接在它们后面而不是挤掉
        if i == len(tails):
            tails.append(v)
        else:
            tails[i] = v
    return len(tails)                # tails 全程单调不减，所以二分始终有效

bisect_left 与 bisect_right 的选择，是 LIS 一族唯一的记忆点：

想求	用	记忆
严格上升	bisect_left	相等的要被替换掉（不能接）
不下降	bisect_right	相等的可以接在后面
严格下降	把序列取负，求严格上升
不上升	把序列取负，求不下降

「取负」是处理下降方向的标准技巧：lis_strict([-x for x in a])。

tails 不是真正的某条子序列，只是每个长度的最优结尾值。 要还原具体方案需要额外记录前驱，见 102-线性DP。

---

111.9　可行规模判断

做法	复杂度	Python 可行的 \(n\)
\(O(n^2)\) DP 求 LIS	\(O(n^2)\)	\(n \le 5\times10^3\) ✅（\(2.5\times10^7\) 次比较，2 秒险）
bisect 版 LIS	\(O(n\log n)\)，bisect 在 C 层	\(n \le 10^6\) ✅ 轻松
树状数组版 LIS（带权值/需要下标信息时）	\(O(n\log n)\)，循环在 Python 层	\(n \le 2\times10^5\) ⚠️
构造具体的反链覆盖方案	\(O(n\log n)\) + 分组	\(n \le 3\times10^5\) ✅
一般偏序集上求最长链（DAG DP）	\(O(V+E)\)	\(E \le 10^6\) ✅

bisect 版是唯一能上大规模的写法：整个二分在 C 层完成， Python 层每个元素只有一次 bisect 调用和一次赋值。

---

111.10　例题

BISHI133 最长不下降子序列（简单）

\(1 \le n \le 5\times10^3\)，\(1 \le a_i \le 10^6\)。求最长不下降子序列的长度。 时限：C/C++ 1 秒，其他语言 2 秒。 题面见 BISHI133 原题（牛客）。

✅ 题解见 solutions/BISHI133.py， 与下面这份写法一致，已在牛客用 Python 3 通过，并由 scripts/verify_docs.py 用官方样例复测。

\(n\) 只有 \(5\times10^3\)，\(O(n^2)\) 的 DP 也能过（\(2.5\times10^7\) 次比较，2 秒下贴着上限）。 但既然 bisect 版更短更快，没有理由不用。

注意题目要的是「不下降」，所以用 bisect_right。

import sys
from bisect import bisect_right


def main():
    data = sys.stdin.buffer.read().split()  # 一次读完，避免逐行 input() 的开销
    n = int(data[0])
    tails = []                               # tails[i]：长度 i+1 的不下降子序列的最小结尾
                                             # 它始终单调不减，所以可以直接二分
    for tok in data[1:1 + n]:                # 只取前 n 个数，多余的空白 token 自然被忽略
        v = int(tok)
        i = bisect_right(tails, v)           # ★ 不下降 -> bisect_right
                                             # 跳过等于 v 的结尾，相等元素可以接在一起
        if i == len(tails):
            tails.append(v)                  # 能接到最长的后面，长度 +1
        else:
            tails[i] = v                     # 否则把这个长度的结尾换成更小的 v
    sys.stdout.write(str(len(tails)) + "\n")  # 答案是 tails 的长度，不是它的内容


main()

样例复核：1 2 4 2 3 4

读入	bisect_right 位置	tails
1	0 == len → append	[1]
2	1 == len → append	[1,2]
4	2 == len → append	[1,2,4]
2	2 < len → 替换	[1,2,2]
3	3 == len → append	[1,2,2,3]
4	4 == len → append	[1,2,2,3,4]

长度 5 ✓（对应子序列 \(\{1,2,2,3,4\}\)）。

用错 bisect_left 会怎样？ 读到第二个 2 时会替换掉位置 1 而不是位置 2， 最终得到 [1,2,3,4]，输出 4——WA，而且样例二 5 4 3 2 1 仍然输出 1，看不出问题。 这就是为什么必须把「严格 / 非严格」和 left / right 的对应关系背下来。

本章视角：这题问的是「最长链」（不下降子序列 = 链）。 由 Mirsky 定理，它同时也回答了另一个问题： 把这个序列拆成最少多少个「严格下降子序列」？答案就是这个 5。 一份代码，两道题的答案。

BISHI9 田忌赛马（中等）

三局两胜，速度严格大于才算赢。已知齐威王三匹马的出场顺序 \(v_1,v_2,v_3\)， 田忌有三匹马 \(a_1,a_2,a_3\)（顺序可任意调整），问田忌能否获胜。 \(1 \le v_i, a_i \le 9\)。 题面见 BISHI9 原题（牛客）。

✅ 题解见 solutions/BISHI9.py，已通过官方样例验证。

\(n = 3\)，\(3! = 6\) 种排列，直接枚举。

from itertools import permutations

v = list(map(int, input().split()))          # 齐威王三匹马，出场顺序固定
a = list(map(int, input().split()))          # 田忌三匹马，顺序可以任意安排

# 枚举田忌三匹马的所有出场顺序，只要有一种能赢下至少两局即可
# p 与 v 按位置配对，x > y 是严格大于（相等算平局，不计入胜场）
# bool 在求和时按 1/0 计算，sum(...) 就是这一种排列下赢的局数
ok = any(sum(x > y for x, y in zip(p, v)) >= 2 for p in permutations(a))
print("Yes" if ok else "No")

两个坑：

1. 严格大于才算赢，速度相等是平局，不计入任何一方；
2. 三局两胜 = 赢的局数 \(\ge 2\)，平局不算赢。

这题和偏序集有什么关系？ 「田忌赛马」的一般形态（\(n\) 匹马，求田忌最多能赢几局）是一个二分图最大匹配问题， 而当匹配的偏好关系满足传递性时，它退化成贪心 + 排序： 双方都排序，用田忌最慢的马去消耗齐威王最快的马。

更深一层的联系是 König 定理：二分图的最大匹配 = 最小点覆盖， 而 Dilworth 定理的标准证明之一正是通过 König 定理完成的 （把偏序集拆成二分图，最小链覆盖 = \(n\) − 最大匹配）。 这条路线本章没有展开，但它解释了为什么「最少链覆盖」类问题 常常能转化成匹配或网络流。

\(n = 3\) 的本题当然用不上这些——能暴力就暴力，这也是一条重要的判断。

两道例题的定位说明

大纲把 BISHI133 和 BISHI9 列为本章例题，但要诚实地说： 牛客题单里没有真正的 Dilworth 定理题。这两题的作用是：

题	在本章的角色
BISHI133	提供「最长链」的标准实现，Mirsky 定理的另一半答案免费附赠
BISHI9	提供「\(n\) 极小时别想复杂」的对照，并牵出 König 定理的联系

如果想真正练手 Dilworth，推荐洛谷 P1020（导弹拦截原题）和 P1091（合唱队形）。

---

111.11　识别信号：什么时候该想到本章

题面里出现	想到
「最少需要多少个不上升/不下降序列覆盖」	Dilworth / Mirsky，答案是对偶的 LIS
「最多能选出多少个两两不可比的元素」	最长反链
「盒子套盒子 / 信封套信封，最多套几层」	二维偏序的最长链
「最少分成几组，每组内部两两可比」	最小链覆盖 = 最长反链
「最少分成几组，每组内部两两不可比」	最小反链覆盖 = 最长链
二维/三维的 \((a_i \le a_j\) 且 \(b_i \le b_j)\)	偏序集，见 118 章

一个实用的自检：拿到「最少分组」题，先问自己「组内元素是两两可比还是两两不可比」。 可比 → 链 → Dilworth；不可比 → 反链 → Mirsky。选错定理答案会反过来。

---

111.12　本章速查

要点	结论
偏序集三条件	自反、反对称、传递
偏序 vs 全序	偏序允许「不可比」的元素对
Hasse 图	只画直接覆盖关系，传递边要删掉；一定是 DAG
链	两两可比的序列
反链	两两不可比的序列
Mirsky 定理	最小反链覆盖数 = 最长链长度
Dilworth 定理	最小链覆盖数 = 最长反链长度
两者关系	在 \((S,\le)\) / \((S,>)\) 上互为对偶；一般偏序集不能互推（整除关系的 \(\nmid\) 不传递）
Mirsky 的构造	按 \(f(x) =\)「从 \(x\) 出发的最长链长度」分层，每层一条反链
Dilworth 的证明	对 \(\|S\|\) 归纳，用最长反链把 Hasse 图切成 \(S_-\) / \(S_+\) 再拼接
序列 → 偏序集	元素记作 \((i, A_i)\)；\(i\) 增且 \(A\) 增 = 可比
不下降子序列	一条链
不上升子序列	一条反链
导弹拦截第二问	= 最长严格上升子序列长度
严格性翻转	覆盖用「不上升」→ 求「严格上升」；用「严格下降」→ 求「不下降」
LIS 严格上升	bisect_left
LIS 不下降	bisect_right
下降方向	序列取负，转成上升问题
tails 数组	不是真实子序列，只是各长度的最优结尾

数据规模 → Python 现实性（LIS 一族）
bisect 版，\(n \le 10^6\)
\(O(n^2)\) DP，\(n \le 5\times10^3\)
\(O(n^2)\) DP，\(n \ge 10^4\)
树状数组版（需下标信息），\(n \le 2\times10^5\)