P2824 [HEOI2016/TJOI2016] 排序 题解

题意： 给定长度为 $n$ 的排列，接下 $m$ 次操作，每次将下标 [$l_i$,$r_i$] 升序或者降序排序，求所有操作完成后的下标 $q$ 的值。

如果直接使用数据结构维护的话，要维护的值的种数太多，且很难pushup_down，考虑能否通过判断确定 $a_q$ 的范围。如果目前考虑一个值 $x$，怎么判断 $x$ 与 $a_q$ 的大小关系？考虑简化序列，因为只需要确定大小关系，可以将大于等于 $x$ 的数赋为 $1$，小于的为 $0$，那么序列变成了 0/1 序列，对于每次排序将 $1$ 放最后就可以了，由于值域小，这个可以拿线段树维护。最后在 $q$ 位置上的值为 $1$ 就是 $x<=a_q$，否则大。我们发现这具有单调性，于是直接二分 check 就完了。

至于时间复杂度：二分 O(log)，离线操作 O(mlog)，总的是 O($m\times log^2 n$)。