（前人之述备矣，只是提供一种题解区没有的建图方式，如果我这个前半部分看不懂可以看看前面佬的）
analysis：
单栈排序，会有栈内元素递减的性质；如果 \(i < j, a_i > a_j\) ，并且还有 \(j < k, a_k < a_i\) 让 \(a_i\) 无法出栈，那么会NIE。
双栈排序也有上述性质，考虑相同的 \(i, j, k\) 满足上述条件，则会导致 \(a_i, a_j\) 不能同时放到一个栈中。
考虑直接连边，记 \(f_i = \max \limits_{j = i, a_j < a_i} ^ {n} {j}, i \rightarrow \{ j | j \in[i + 1, f_i], j > i\}\) ，可以过掉 NOIP2008双栈排序 ，然后考虑优化建边。
发现连边的条件是对”区间的值域后缀“连边，二维信息且一维为后缀形式，考虑建主席树，将下标放在线段树下标上，值放在版本上。
考虑二分图染色贪心（照搬），会发现一个问题，因为建单向边存在 \(x\) 和 \(y\) 的闭合子图中都有 \(z\)，但是可能在 \(x < y\) 时染到 \(x,z\)，我们希望同时染上 \(y\)。
考虑建双向边，但边不太好建双向（本来 \(O(n\log n)\) 空间就快炸了，两棵主席树可能不行）。
考虑其他办法，先不同时染 \(y\)，每次尝试染色，如果能够染较小的就染较小的颜色，如果都不行就判断NIE。
最后输出方案即可。
标签：连边,KOL,POI2010,双栈,NIE,P3497,考虑,排序 From： https://www.cnblogs.com/langligelangsblog/p/17932653.html