莫队学习笔记

一、基础

1.应用条件

1.区间询问，不修改
2.更新区间时左右端点拓展1位和收缩1位均可O(1)实现

2.时间复杂度：O((m+n)\sqrt n)

3.实现方法

对询问离线处理。先将序列按\sqrt n分块，再按询问区间左端点所属块升序为第一关键字，右端点升序为第二关键字排序。每次由上一个区间移动左右端点到下一个区间，每次移动更新答案。最后统一回答。

4.例题

洛谷 P2709 小B的询问

5.练习

洛谷 P1494 小 Z 的袜子

二、回滚莫队

1.应用条件

1.区间询问，不修改
2.更新区间时左右端点拓展1位可O(1)实现或收缩1位可O(1)实现

2.时间复杂度：O((m+n)\sqrt n)

3.实现方法 & 4.1 例题1

这里

4.2 例题2

WC2022T2 秃子酋长

5.练习

洛谷 P5906 模板

三、带修莫队

1.应用条件

1.区间询问，带修改
2.更新区间时左右端点拓展1位和收缩1位均可O(1)实现

2.时间复杂度：O(n^{5/3}) (n,m同级)

3.实现方法

对区间增加一维t表示询问前修改次数，分块。令块大小为a,按L所属块升序为第一关键字，R所属块升序为第二关键字，t升序为第三关键字排序。时间复杂度:

1.t移动：O(n^2t/a^2) (t \le n)

2.同一r块中l,r移动：O(am)

3.l块移动，r的总移动：O(n^2/a)

取a=n^{2/3}，有时间复杂度O(n^{5/3})

4.例题

洛谷 P1903 数颜色 / 维护队列

5.练习

CF940F Machine Learning