P2824 [HEOI2016/TJOI2016] 排序 题解

saikrilll · 2025-01-04 19:19:29 · 个人记录

题意： 给定长度为 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)。