定义

给出序列 \(a\)，现有初始为空的序列 \(b\) 和 \(k\) 个初始为空的栈，你可以进行任意次以下两种操作：

1. 选择 \(x\)，若序列 \(a\) 非空，将 \(a_1\) 压入栈 \(x\)，并将其从序列 \(a\) 中删除。

2. 选择 \(x\)，若栈 \(x\) 非空，将栈 \(x\) 的栈顶元素加至序列 \(b\) 末端，并将其弹出。

若存在一种操作方案，使得无法进行任何操作时序列 \(b\) 单调不降，则称 \(a\) 是可 \(k\) 栈排序的。

判定

对于长度为 \(n\) 的序列 \(a\)，若有 \(i < j < k\) 满足 \(a_k < a_i < a_j\) 则连无向边 \((i, j)\)。

记最终得到的图为 \(G\)，\(a\) 是可 \(k\) 栈排序的当且仅当 \(G\) 是 \(k\) 部图。

必要性

考虑反证。

若 \(G\) 不是 \(k\) 部图且 \(a\) 是可 \(k\) 栈排序的，则在操作方案中必有 \(i < j < k\) 满足 \(a_k < a_i < a_j\)，且 \(a_i, a_j\) 被压入同一个栈。

当 \(a_j\) 被压入该栈时，因为 \(a_i < a_j\) 所以 \(a_i\) 必然已经出栈。此时 \(a_k\) 还未入栈，又因为 \(a_k < a_i\) 所以最终的 \(b\) 不可能单调不降，矛盾。

充分性

考虑构造证明。

找出 \(G\) 的一种 \(k\) 染色方案使得相邻的节点不同色，钦定颜色为 \(x\) 的节点对应的元素被压入栈 \(x\)。

当序列 \(a\) 非空时，不断将 \(a_1\) 压入对应的栈。

在把权值为 \(y\) 的元素压入栈 \(x\) 前，如果栈 \(x\) 非空且栈顶元素权值 \(z < y\)，则不断弹出栈顶。在把权值为 \(z\) 的栈顶元素弹出栈 \(x\) 前，如果其它栈不全为空且最小栈顶元素权值 \(< z\)，则不断弹出该最小栈顶。

序列 \(a\) 为空后，如果存在非空栈则不断弹出最小栈顶元素。

我们声称通过上述操作得到的序列 \(b\) 单调不降。

要证明序列 \(b\) 单调不降，只需证明每个元素出栈前所有权值严格小于它的元素已经出栈。

显然上述操作中每个元素出栈时它的权值都不大于还在栈中的任何元素，因此只需证明每个元素出栈时所有权值严格小于它的元素都已经入栈。

若权值为 \(z\) 的元素从栈 \(x\) 弹出：

如果该元素是因为一个权值为 \(y\) 的元素被压入栈 \(x\) 而弹出的，则必有 \(z < y\)。又因为这两个元素对应节点在 \(G\) 中不相邻，所以所有未入栈的元素权值都 \(\ge z\)。

如果该元素是因为一个权值为 \(y\) 的栈顶元素出栈而被弹出的，则必有 \(z < y\)。由上一段所有未入栈元素权值都 \(\ge y\)，因此所有未入栈的元素权值都 \(> z\)。

否则该元素是在序列 \(a\) 为空后被弹出的，没有未入栈的元素。

例题

POI2010 KOL-Railway

kczno1 的题解，如果没看懂可以参考一下 我在 POI2003 Mortorways 的题解。