本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-22 19:32:17

:::::info[闲话]{open} 来一篇严谨证明题解！ ::::: :::::info[题目基本信息] 考察：Dilworth 定理，线段树（提高+/省选-）。
题目简介：
给定 $\{s_n\},\{c_n\}$，定义 $a$ 可以包含 $b$ 当且仅当 $s_a\le c_b$，对于每一个 $k$，询问对于 $[1,k]$ 内的所有整数，每个整数可以钦定它包含最多一个数，问最少有几个数不被其它数包含。
数据范围：

• $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 定理] $S$ 的最长反链等于最小链覆盖数。
  ::::: :::::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$ 的这条反链内的元素一定两两不位于一个链，产生矛盾。

故 $S$ 的最小链覆盖数等于 $T$ 的最小链覆盖数加 $1$，传递得到 $S$ 的最小链覆盖数等于 $S$ 的最长反链长度，故在这种情况下命题成立。
当 $T$ 的最长反链等于 $S$ 的时，找到 $T$ 的最长反链 $P$，设集合 $S^-=\{x\in S|\exists p\in P,x\preceq p\},S^+=\{x\in S|\exists p\in P,p\preceq x\}$，那么有以下性质：

• $S^-\cup S^+=S$，否则存在一个元素与 $P$ 内元素不可比，那么 $P$ 还能加入这个元素变得更长。
• $S^-\cap S^+=P$，由偏序集的传递性（若 $\exists p_1,p_2\in P,p_1\ne p_2,p_2\preceq x\preceq p_1$，根据传递性马上就能推出矛盾）和自反性（若 $\exists p\in P,p\preceq x\land x\preceq p$，马上就能推出 $x=p$）容易得出。
• $|S^-|,|S^+|<|S|$，因为 $V\notin S^-$（否则与最大元条件矛盾，下同）且 $v\notin S^+$。

对 $S^-,S^+$ 应用归纳假设，然后就得出了 $S^-$ 和 $S^+$ 的 $S$ 的最小链覆盖数条链，同时每条链都包含了 $P$ 内的一个元素，将 $S^-$ 和 $S^+$ 的最小链覆盖内的链一一对应拼接即可构造。
证毕。 ::::: 好的我们将这个问题转化为最长反链，我们注意到对于 $i,j$，它们不能互相包含当且仅当 $(c_i,s_i]$ 和 $(c_j,s_j]$ 有交集，然后我们每次在线段树上对 $(c_i,s_i]$ 区间加 $1$ 查询全局最大值即可。
然后我们就做完了此题。
时间复杂度为 $\Theta(n\log n)$，空间复杂度为 $\Theta(n)$。

code