莫队算法是一种优雅的离线分块算法，由莫涛（Mo Tao）提出。
一、普通莫队
核心思想：将询问离线，按照某种顺序处理，利用上一次查询的结果快速计算下一次。
基本流程：
- 将数组分成 √n 块
- 询问排序：左端点所在块号优先，右端点次之
- 维护当前区间 [L, R]，通过增减元素来移动
- 复杂度 O(n√n)
排序的关键——奇偶优化：
struct Query {
int l, r, id;
bool operator<(const Query &q) const {
if (l/B != q.l/B) return l/B < q.l/B;
return (l/B) & 1 ? r > q.r : r < q.r; // 奇偶优化
}
};二、带修莫队
增加时间维度，支持单点修改：
- 分块大小：n^(2/3)
- 时间复杂度：O(n^(5/3))
- 移动顺序：L → R → 时间
三、树上莫队
将树上的路径查询转换为序列查询：
- 欧拉序（进栈序 + 出栈序）
- 路径查询 → 序列区间查询
- 注意 LCA 的处理
四、回滚莫队（不删除莫队）
当只能添加、不能删除时使用：
- 对每个块单独处理
- 清空 → 添加 → 回滚
五、莫队的技巧
- 值域分块：将莫队与分块结合，支持 O(1) 修改、O(√n) 查询
- bitset 优化：用 bitset 加速集合的交并操作
推荐练习：
- 普通莫队：洛谷 P1494 小Z的袜子
- 带修莫队：洛谷 P1903 数颜色
- 树上莫队：洛谷 SP10707 COT2
暂无评论，快来抢沙发吧~ 🛋️