2021年第十二届蓝桥杯 - 省赛 - C/C++大学B组 - I.双向排序
题目中给出了两种操作：
当 pi = 0 时，表示将 a1, a2, · · · , aqi 降序排列；当 pi = 1 时，表示将 aqi , aqi+1, · · · , an 升序排列。按照题目暴力排序应该可以骗一点分，但如果想AC，就需要优化算法。可以根据测试用例的范围：1 ≤ n, m ≤ 100000，估计一下时间复杂度要控制在O(nlog n)。
首先对于连续的p=0，即：pi=0 qi=a；pi+1=0 qi+1=b。如果b>a，那么(pi, qi)的操作将无效，因为(pi+1, qi+1)已经将(pi, qi)的范围包含了。同理，如果pi+2=0; qi+2=c，而b>c，那么pi+2和qi+2的操作也将无效。
然后对于连续的p=1，即：pi=1 qi=a；pi+1=1 qi+1=b。同理，如果a ∀a∈[0, x]。
那么之后我们对[y, n]升序排列(y> n >> m;while (m--) {int p, q;cin >> p >> q;if (p == 0) {while (top && stk[top].first == 0) {q = max(q, stk[top--].second);}while (top >= 2 && stk[top - 1].second = 2 && stk[top - 1].second >= q) {// 如果当前操作比上一次相同操作的范围要大，那此次操作的前两次操作都将被无效化 top -= 2;}stk[++top] = {1, q};}}int left = 1, right = n, k = n;for (int i = 1; i stk[i].second && left