【数据结构】莫队

莫队是一种优雅的暴力。它采用了分块的思想，依靠移动询问的左右端点并维护答案的原理，解决一些区间查询的问题。

莫队的题目在洛谷中难度评级很高，但它的原理很容易理解，代码实现也相对简单。莫队的要点是 O(1) 或均摊O(1)更新答案，遇到综合应用时先想想能不能转化出更新答案的方法，如果不能，那还是用别的数据结构吧。

以下是几个讲解莫队及有关知识的文章（以下文章内容非本人编写，仅是搜集了网上内容）：

分块入门莫队算法——从入门到黑题日报:莫队算法初探

二维矩阵中的莫队回滚莫队拓展日报:莫队的在线化改造

本题单是莫队算法的学习题单。在学习莫队之前，最好先学习分块。本题单包含各类莫队的模板、简单应用、混合应用。虽然往年NOI系列竞赛中，只能用莫队通过的题目不多，但莫队在时限不严的情况下仍能通过大多数数据甚至AC，而且相比于其他复杂的数据结构更易于在考场上写出。在CF比赛，Ynoi等线上比赛中，莫队则有高的出现率。很多题目也可以用类似莫队的思想来通过。

如果对本题单的选用题目，题目解析，语言描述有建议的，请及时联系我。

题目列表（建议按顺序做）

为了给各位留下足够的思维空间和思维难度，我对于以下题目并没有给出具体做法。本题单未选用双倍经验或做法极其类似的题目。

普通莫队

SP3267 莫队模板
P1494 简单的一个应用
P3709 一个应用(题意：求区间众数的出现次数）
CF617E 将区间用前缀“和”来表示
P3245 采用后缀思想。注意当 gcd(10,p)≠1 时需要做特殊处理

带修莫队

P1903 带修莫队模板
CF940F 简单的带修莫队，注意复杂度的证明
CF1476G 比较难的一个应用，注意推导特殊性质。难点在于统计答案。考虑定义一个数的出现次数的出现次数（即 cnt_i 的出现次数）,对这个数组进行统计。

回滚莫队

AT1219 回滚莫队模板
P6072 回滚莫队+01trie
P4137 只减不加的回滚莫队
P5386 回滚莫队结合序列分块，序列的每个块内单独维护

树上莫队

P3379 LCA，树上莫队的必备前置知识
SP10707 树上莫队模板
P4689 树上莫队
P4074 树上带修莫队

综合应用

P4477 先对问题进行简化，并考虑对于简化后的问题使用其它数据结构（如线段树）。最后加上莫队处理就可以了
SP744 莫队思想的应用，像莫队一样维护左右端点。
CF1000F 莫队+一些技巧（值域分块，栈……）可能需要卡常
P5268 莫队+差分
P3604 莫队+状态压缩
P4396 莫队+值域分块
P3674 莫队+bitset的简单技巧
P5112 莫队+字符串哈希
P4688 莫队+bitset，拆解询问

二次离线莫队

P4887 二次离线莫队模板（扫描线+队列）
P5398 需要用到根号分治，需要卡常
P5047 一个应用