【数据结构】莫队

莫队是一种优雅的暴力。它采用了分块的思想，依靠移动询问的左右端点并维护答案的原理，解决一些区间查询的问题。 莫队的题目在洛谷中难度评级很高，但它的原理很容易理解，代码实现也相对简单。莫队的要点是 $O(1)$ 或均摊O(1)更新答案，遇到综合应用时先想想能不能转化出更新答案的方法，如果不能，那还是用别的数据结构吧。 以下是几个讲解莫队及有关知识的文章（以下文章内容非本人编写，仅是搜集了网上内容）： #### [分块入门](https://www.cnblogs.com/cn-suqingnian/p/9302143.html) [莫队算法——从入门到黑题](https://www.cnblogs.com/WAMonster/p/10118934.html) [日报:莫队算法初探](https://www.luogu.com.cn/blog/codesonic/mosalgorithm) #### [二维矩阵中的莫队](https://www.cnblogs.com/ouuan/p/2DMoDui.html) [回滚莫队拓展](https://www.cnblogs.com/Parsnip/p/10969989.html) [日报:莫队的在线化改造](https://www.luogu.com.cn/blog/asadashino/moqueue) 本题单是莫队算法的学习题单。在学习莫队之前，最好先学习分块。本题单包含各类莫队的模板、简单应用、混合应用。虽然往年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 一个应用