一道自己想到的题。

有一个序列 $a_1, \dots, a_n$。有 $m$ 次操作，每一次对某一个区间 $[l_i, r_i]$ 进行排序。最后输出结果。以下是我的思路：

• 暴力是 $O(mn\log n)$ 的。
• 维护有序段，并在有序段被切割时用 nth_element，可做到 $O(mn)$。
• 用平衡树，考虑类似 Splay 的区间反转打懒标记，可是下传是 $O(n)$ 的。
• 维护有序段，需要一种数据结构，可以按排名分裂和任意合并，且复杂度均为亚线性的，我不知道是否存在这种数据结构。
• 看起来随机数据中所有被排序的数据大致呈单调递增，所以有序段不会很多，可以乱搞？（不知道能不能被卡掉）

如果已经有原题了，可以发一下题目链接。