首先，你要会二维偏序（最长上升子序列），这样就可以了（三维偏序等不需要）。
这里引入一个重要的关于偏序的定理：狄尔沃斯（Dilworth）定理。
-
偏序：对于一个集合 \(S\)，偏序是它上面的一个二元关系 \(\preceq\)，满足自反性 \(\forall a\in S,a\preceq a\)，传递性 \(\forall a,b,c\in S(a\preceq b\wedge b⪯c)\Longrightarrow a\preceq c\)，以及反对称性 \(\forall a,b\in S(a\preceq b\wedge b\preceq a)\Longrightarrow a=b\)。
-
链：对于集合 \(S\) 的子集 \(T\)，如果 \(T\) 中任意两个元素均可比（即 \(\forall a,b\in T,a\preceq b\vee b\preceq a\)），则称 \(T\) 为链，称 \(|T|\) 为链的长度。
-
反链：对于集合 \(S\) 的子集 \(T\)，如果 \(T\) 中任意两个元素均不可比（即 \(\forall a,b\in T,a\not\preceq b\wedge b\not\preceq a\)），则称 \(T\) 为反链，称 \(|T|\) 为反链的长度。
-
最小链/反链划分：将 \(S\) 划分为最少的集合 \(T_1,T_2,\cdots,T_k\)，使得所有 \(T_i\) 均为链/反链，这个链/反链划分的大小为 \(k\)。
狄尔沃斯定理的叙述为：对于任意偏序集 \(S\)，最长反链长度等于最小链划分，最长链长度等于最小反链划分（证明不在此赘述，如有需要请自行查找资料）。
这个定理很抽象，我们来看一个简单一点的例子。
给定一个长度为 \(n\) 的序列 \(a\)，需要你求出其最长不上升子序列长度，以及最少能够划分成多少个不上升子序列（\(1\le n\le 10^5\)）。
第一问很好做，对于第二问，考虑狄尔沃斯定理，一个很常见的手法就是将一个序列转化为点对 \((i,a_i)\)，再定义偏序关系 \((x_1,y_1)\preceq (x_2,y_2)\Longleftrightarrow x_1\le x_2\;\wedge y_1\ge y_2\)，容易发现这种偏序关系中的链代表一个不上升子序列，反链代表一个上升子序列。狄尔沃斯定理告诉我们，最长链长度等于最小反链划分，最小反链划分就是第二问的答案，最长链的长度就是最长上升子序列的长度，那么第二问的答案就是最长上升子序列的长度。
是不是对狄尔沃斯定理有了一定的了解，再来看一道题。
标签：偏序,preceq,长度,forall,简单,序列,一些,反链 From： https://www.cnblogs.com/lrx-blogs/p/18571111定义一个序列长度为 \(n\) 的序列 \(a\) 对应一个图 \(G\) 如下生成：
- \(G\) 有 \(n\) 个点；
- 如果 \(i,j\) 满足 \(i<j\wedge a_i>a_j\)，则 \(G\) 中有 \(i\leftrightarrow j\) 的无向边。
如果 \(G\) 是二分图，称 \(a\) 是 bipartite array。
给定一个长度为 \(n\) 的排列 \(a\)，判断能否通过将一些数改成其相反数而使得排列变为 bipartite array。如果可以，输出方案。