闲话少说。给出n个二维点，求一个最长序列满足对于序列中的任意两个点a、b有a.x<b.x && a.y<b.y。这个问题其实可以转换为求最少反链覆盖的问题，原因在上篇文章中已经讲了：存在两种偏序使得一种偏序定义下的链是另一种偏序定义下的反链。因此可以贪心，但复杂度是O(n^2)的。实际上还可以转换为求最长上升子序列，方法是对点集进行排序，y小的排前面，y相同时x大的排前面。拍完后取每个点的x坐标形成一个新序列，则原问题变为求这个序列的最长上升序列。为什么？只需要证新序列下任意两个元素之间的关系（是否满足偏序）与原二维平面上的点之间的关系是一致的。
如果变成3维呢？这时就不能贪心了，只能老老实实的Dilworth定理，建DAG用最小路径覆盖。当然用二维线段树DP也行。为啥不能贪心？因为不存在两种偏序。如果定义a.x<b.x && a.y<b.y && a.z<b.z为一种偏序，则其反链的关系不能构成另一种偏序，因为不具有传递性。试试就知道了。
今早起来突然想到这些。先记下。继续工作。。