2021年第十二届蓝桥杯 - 省赛 - C/C++大学B组 - I.双向排序

Ideas

题目中给出了两种操作：

1. 当 pi = 0 时，表示将 a1, a2, · · · , aqi 降序排列；
2. 当 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