还是那句话,不想写题了就胡一胡做法。
显然看 LIS 的奇偶性来决定最后答案如何划分。
如果 LIS 是偶数,那么必定有解,因为肯定可以将其分成两个部分,并合理选择元素放入,使得两个子序列 LIS 不会变长。具体证明考虑 Dilworth 定理。
如果 LIS 是奇数,那么必定要找到一个不在 LIS 里的元素划分进两个集合里的任意一个,有一个结论是,设 LIS 长度为 \(m\),那么你需要选出的点 \(u\) 的包含 LIS 长度至少为 \(\frac{m + 1}{2}\),判断是否存在这样的 \(u\) 即可。