社区讨论

关于区间排序的题目做法

jjifbtDinshey
学术版参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo7ku7mo
此快照首次捕获于
2023/10/27 03:28
2 年前
此快照最后确认于
2023/10/27 03:28
2 年前
查看原帖
一道自己想到的题。
有一个序列 a1,…,ana_1, \dots, a_n。有 mm 次操作，每一次对某一个区间 [li,ri][l_i, r_i] 进行排序。最后输出结果。以下是我的思路：
  • 暴力是 O(mnlog⁡n)O(mn\log n) 的。
  • 维护有序段，并在有序段被切割时用 nth_element，可做到 O(mn)O(mn)。
  • 用平衡树，考虑类似 Splay 的区间反转打懒标记，可是下传是 O(n)O(n) 的。
  • 维护有序段，需要一种数据结构，可以按排名分裂和任意合并，且复杂度均为亚线性的，我不知道是否存在这种数据结构。
  • 看起来随机数据中所有被排序的数据大致呈单调递增，所以有序段不会很多，可以乱搞？（不知道能不能被卡掉）
如果已经有原题了，可以发一下题目链接。

回复

共 4 条回复，欢迎继续交流。

正在加载回复...