根号分治和莫队

FJ_00460 · 2025-03-23 19:36:48 · 个人记录

根号分治与莫队

根号分治是一种奇怪的分块

• 根号分治算法是一种用于优化数据结构和算法复杂度的技术。

• 对于题目中的某两个约束，它们总是相互制约的，并且这种制约是“乘积”关系——步长和项数，总有一个不能太大。

• 针对这两个情况分别设计算法，然后将两种算法结合起来，就能获得一个完整的解决问题的算法。

• 大多数数据结构都擅长处理“连续区间”的询问，而不擅长间隔区间之间的询问。

• 令区间间隔为 d ，对于 d \le \sqrt n 的情况预存部分和 ，对于 d > \sqrt n 的情况暴力扫描，就可以保证算法时间复杂度为O(n \sqrt n)

莫队

• 莫涛发明的，解决区间查询的离线算法，基于根号分治，复杂度为 O (n \sqrt n) 。
• 一般来说，如果可以在O(n) 内从[l, r] 的答案转移到 [l - 1, r], [l + 1, r], [l, r - 1], [l, r + 1] 这四个与之紧邻的区间的答案，则可以考虑使用莫队。

莫队思想

• 分块+排序，通过合理排序查询顺序，减少区间指针移动次数。

• 精髓在于排序，以确保时间复杂度

• 普通莫队是基于分块的离线算法，用于解决区间查询。

• 使用范围

  • 只询问不修改
  • 允许离线
  • 在已知[l, r]的情况下能O(1)得到 [l - 1, r], [l + 1, r], [l, r - 1], [l, r + 1]的答案。

• 若满足掉件，就可以在O(n \sqrt n)的复杂度内求出所有询问的姐（前提是n与m同阶，理解为n = m）。

莫队实现

• 将所有询问读入进来后进行离线操作
  • 将这些询问排序，否则就是TMD暴力
  • 顺序处理这些询问，暴力的从上一个区间答案转移到下一个区间答案，即左右指针一步步移动。

排序

• 现将n个数的序列分块，分成\sqrt n 个块
• 然后，将询问的左端点按块从小到大排序
• 相同的再按右端点排序
• 优化：奇偶性排序，就是让奇数块和偶数块的排序相反。例如，左端点L都在奇数块，则对R从大到小排序，若L在偶数块，则对R从小到大排序（反之亦可）。

why?

奇偶性排序用于减少指针移动的总次数，从而降低时间复杂度

莫队基本思想是将数组分块，按左端点所在块排序，同块内按右端点升序排序，这样左指针在块间移动时，右端点尽可能单调递增，减少来回移动

但同一块内的查询若全部按右端点升序排序，可能会出现以下问题：

• 左指针在块内从左到右移动时，右端点先递增到块末尾，下一个查询的左指针跳回块开头时，右端点可能需要跳回左边，导致右端点反复横跳，增加移动次数

奇偶性排序的优化逻辑

规则是：

• 奇数块内的查询，按右端点升序排序
• 偶数块内的查询， 按右端点降序排序

关键优化在于

• 块间切换时，右端点移动方向交替： 如处理完奇数块（右端点升序到最大）后，切换到下一个偶数块时，右端点会从当前最大值跳转到偶数块的右端点（降序起点），随后逐步向左移动，避免了右端点先右移再左移的麻烦。

复杂度

单独考虑左端点：复杂度为O(m \sqrt n)

单独考虑右端点，复杂度为O(n \sqrt n)

综上，时间复杂度为O(m \sqrt n + n \sqrt n)，因为n, m同阶，所以是O(2n \sqrt n)。

不同阶时

复杂度为O( n * n / m)

步骤

块大小 block = \sqrt n

维护变量：

• cnt[x]:x在当前区间的出现次数
• ans：当前区间的不同数个数