根号分治与莫队

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

• 根号分治算法是一种用于优化数据结构和算法复杂度的技术。
• 对于题目中的某两个约束，它们总是相互制约的，并且这种制约是“乘积”关系——步长和项数，总有一个不能太大。
• 针对这两个情况分别设计算法，然后将两种算法结合起来，就能获得一个完整的解决问题的算法。
• 大多数数据结构都擅长处理“连续区间”的询问，而不擅长间隔区间之间的询问。
• 令区间间隔为 $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?

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

奇偶性排序的优化逻辑

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

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

复杂度

不同阶时

步骤

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