P3497

传送门 （前人之述备矣，只是提供一种题解区没有的建图方式，如果我这个前半部分看不懂可以看看前面佬的） analysis： 单栈排序，会有栈内元素递减的性质；如果 \(i < j, a_i > a_j\) ，并且还有 \(j < k, a_k < a_i\) 让 \(a_i\) 无法出栈，那么会NIE ......

题目 双栈排序 \(O(n\log n)\) 版，\(O(n^2)\) 可过弱化版P1155。 分析 经过长时间的手玩数据，可以发现某些点不可能在同一个栈中，考虑总结一个规律。 对于下标 \(i,j(1\le i<j\le n)\)，若 \(a_i>a_j\)，由于栈是后进先出，\(i,j\) 之间 ......