莫队

莫队是一个**离线**解决可以维护区间左右端点移动后答案的算法。在结合一些技巧后，莫队可以处理树上问题，支持带修改，也能处理插入简单删除难的特殊情况。其优秀的根号复杂度和并不算大的常数常常能在很多数据结构题中发挥作用。考场上，这个好记好用好写好调还很短的算法常常帮助你轻松拿到部分分甚至踩标算。 本题单不提供莫队教程，仅提供配套题目。 保证题单中的题我都AC过，如果您有好题，可以联系我，写完了会立马加，如果部分题目备注有误和有更多的建议也可以联系我。 如果您在看到题目后能很快想出做法，不一定要全部 AC。 # Warning 并不是所有题目都能用莫队通过。部分题目莫队非正解，需要大力卡常或者根本过不去。 当然，对于部分题目，莫队确实是正解，但是仍然需要卡常。本题单仅提供大致思路，对于部分细节，请移步题解区。 # Status * Last update : $2021.2.9$ * Update log since $2021.2$: $2021.2$：应该将站内所有题单里的莫队整理完了。 $2021.2.6$：添加了 Edu 的一道带修莫队。 $2021.2.9$：添加了 div.1 的一道树上莫队。 $2021.2.13$：发现 CF 上的一个 blog，里面有一些莫队题。 $2021.2.14$：添加了一道双倍经验。 $2021.2.15$：添加了一道比较水的题。 $2021.3.26$：？？？ $2021.4.15$：添加了 Edu 的一道需要卡常的莫队。 $2021.4.28$：删除了一道多倍经验 SP32900，添加了 CF 上的一道 $\sqrt n\log n$ 复杂度的莫队。 $2021.6.17$：添加了一道 THUPC 的二次离线莫队，将双倍经验全部移到了[这里](https://www.luogu.com.cn/training/79158)。 # Contents * Section 1 莫队是什么 * Section 2 莫队上树 * Section 3 带修莫队 * Section 4 回滚莫队 * Section 5 bitset上莫队 * Section 6 二次离线莫队 * Section 7 这也是莫队 * Section 8 杂题 # Section 1 * 莫队是什么 * $O(1)$ 移动端点的优良性质 * 分块排序询问的重要之处 ## [P3901](https://www.luogu.com.cn/problem/P3901) * 不是模板题，因为有一万种做法。 ## [SP1684](https://www.luogu.com.cn/problem/SP1684) * 模板题。 * 和 Uva11235 是双倍经验。 ## [P1972](https://www.luogu.com.cn/problem/P1972) * 模板题。 * 和 SP3267 是双倍经验。 * 需要吸氧。 * 实在过不去还是写一发正解吧…… ## [P1494](https://www.luogu.com.cn/problem/P1494) * 模板题。 * 注意到答案是合法方案除以总方案，维护合法方案数即可。 ## [P2709](https://www.luogu.com.cn/problem/P2709) * 模板题。 * $(x+1)^2-x^2=2x+1$ ## [CF877F](https://www.luogu.com.cn/problem/CF877F) * 模板题。 * 需要写一个离散化或者大力卡常。 ## [CF1000F](https://www.luogu.com.cn/problem/CF1000F) * 模板题。 * 需要火车头，正解并不是莫队。 ## [P4396](https://www.luogu.com.cn/problem/P4396) * 模板题。 * 和 P4867 是双倍经验。 * 需要套一个根号平衡的东西，不然多一只 $\log$ 会被卡。 * 留意一下 $O(\sqrt n)$ $O(1)$ 查询/修改的东西，这种在根号需要平衡复杂度的时候比较常见。 ## [CF220B](https://www.luogu.com.cn/problem/CF220B) * 模板题。 * 不懂为什么是紫题。 ## [CF633H](https://www.luogu.com.cn/problem/CF633H) * 待添加描述 # Section 2 * ~~一开始学的时候以为是树分块然后指针跳 father 和 son~~ * 莫队上树无非把树变成 Euler 序，因此并没有什么可怕的。 * 然而 Euler 序的思想非常有用。 ## [SP10707](https://www.luogu.com.cn/problem/SP10707) * 模板题。 ## [CF375D](https://www.luogu.com.cn/problem/CF375D) * 也是模板题。 ## [CF1479D](https://codeforces.ml/contest/1479/problem/D) * 没那么模板。 * 采用 One Occurrence 的均摊加上分块维护信息。 * 查询时序列分块，整块可以均摊分析，边角直接暴力即可。 * 稍微卡卡常。 其实普通莫队强行上树很无聊……所以请先收好这个知识点，往后看： 挖坑：[P4074](https://www.luogu.com.cn/problem/P4074)（section 3），[P4175](https://www.luogu.com.cn/problem/P4175)（section 3），[P6072](https://www.luogu.com.cn/problem/P6072)（section 4），[P4689](https://www.luogu.com.cn/problem/P4689)（section 7） # Section 3 * 修改就是多了一维时间而已。 * 但是这样分块要有两维。 * $O(n^\frac{5}{3})$ 的优秀复杂度 * 求求你了块长开 $n^{\frac{2}{3}}$ * ~~四维莫队，五维莫队~~ * ~~啊这，这跑的和 $O(n^2)$ 差不多快啊~~ ## [P1903](https://www.luogu.com.cn/problem/P1903) * 模板题。 * 和 UVA12345 是双倍经验。 ## [SP30906](https://www.luogu.com.cn/problem/SP30906) * 模板题。 * 没什么好说的。 ## [SP32952](https://www.luogu.com.cn/problem/SP32952) * 模板题。 ## [CF940F](https://www.luogu.com.cn/problem/CF940F) * 模板题。 * 通过证明答案上界的方法证明复杂度是对的。 ## [P4175](https://www.luogu.com.cn/problem/P4175) * 模板题。 * 这个题虽然 $O(n^\frac{5}{3}\log n)$ 也能过，但是还是建议大家写 $O(n^\frac{5}{3})$。 ## [P4074](https://www.luogu.com.cn/problem/P4074) * 模板题。 * 需要树上莫队的前置知识。 ## [CF1476G](https://www.luogu.com.cn/problem/CF1476G) * 模板题。 * 考虑维护 $ccnt$ 和 $ccnt$ 不为 $0$ 的所有下标，然后跑双指针。 * 由于 $\sum i\times ccnt_i\leq n$ 所以下标只有 $k$ 个，复杂度是对的。 # Section 4 * 插入 $O(1)$ 轻轻松松。 * 删除……好像要 $O(n)$…… * 能不能不删除啊。 * 还是运用分块的思想。 * 每一块让 $r$ 递增的同时把 $l$ 保持在最右边。 * 查询的时候临时拖动 $l$ 就可以了。 ## [P3709](https://www.luogu.com.cn/problem/P3709) * 题意是求区间众数的出现次数。 * 知道题意就是模板题了。 * 这题也可以通过求各个值的出现次数来用普通莫队解决。 * 和 P1997 SP32900 三倍经验。 * ~~你可以直接通过YLST3来四倍经验。~~ * ~~然而YLST是分块，要强制在线的QAQ~~ ## [AT1219](https://www.luogu.com.cn/problem/AT1219) * 模板题。 * ~~我这题写了个假的算法开 O2 过去了~~ ## [P5906](https://www.luogu.com.cn/problem/P5906) * 模板题。 * 双倍经验 SP20644 。 * SP20644 记得先求前缀和，然后稍微处理一些小细节 ## [P6072](https://www.luogu.com.cn/problem/P6072) * 转化题。 * 将路径化为两端到根的异或和的异或值。 * 通过在子树内找一条，子树外找一条的方式转化答案。 * 01-trie 求集合中两个数异或最大值。 ## [CF522D](https://www.luogu.com.cn/problem/CF522D) * 模板题。 * **卡了回滚莫队，请先用回滚莫队在CF上提交，理论上应该TLE on 28，然后再一发线段树水过去就行了QAQ** ## [(Ynoi2019)P6578](https://www.luogu.com.cn/problem/P6578) * 不是模板题。 * 第十分块，可能是题单中难度最大的题。 * 不难发现我们要维护 $a_i\leq x$ 的状态。 * 你发现把 $0$ 变成 $1$ 很好维护，$1$ 变成 $0$ 则很难维护。 * 考虑回滚莫队掉 $(t,x)$，其中 $t$ 是时间戳。 * 有亿点细节。 * 实操时询问分块替代回滚莫队就不用排序了。 ## [P5386](https://www.luogu.com.cn/problem/P5386) * 切了上面那道题之后就是双倍经验了。 * 考虑直接回滚莫队掉 $(x,y)$，这个就是一般回滚莫队，有手就行（ # Section 5 * bitset 有 $\frac{n}{64}$ 的优秀复杂度。 * 如果题目中有涉及到**几个数的和/差/积/max**等和值域相关的信息，且我们能接受 $O(n\sqrt n+\frac{n^2}{64})$ 的诡异复杂度，bitset 值得一试。 ## [P3674](https://www.luogu.com.cn/problem/P3674) * 模板题。 * 加减可以用 bitset 的 ``<<`` 和 ``>>`` 搞定，乘可以暴力。 ## [(Ynoi2017)P5355](https://www.luogu.com.cn/problem/P5355) * 看起来这个除法操作不太好弄。 * 然而你会发现除数 $>\sqrt n$ 的时候可以直接暴力。 * 除数 $\leq\sqrt n$ 的时候可以预处理一下。 ## [(Ynoi2011)P5313](https://www.luogu.com.cn/problem/P5313) * 区间膜 $b$ 相同的数的 $mex$ 的最大值。 * 不难发现 bitset 优化可以得到一个 $m\sqrt n+\frac{100000m}{64}$ 的东西。 * 然而 $b$ 太小了会被卡。 * 因此 $b$ 小于 $64$ 的时候单独莫队跑一遍。 * 这里的暴力复杂度是 $O(\text{能过})$，然而可以卡。 * 你也可以写一个回滚，复杂度是 $O(m\sqrt n\times\text{大常数})$，反而过不了。 * ~~建议快点写，说不定哪天你就要多些一个回滚莫队了~~ * 数据已加强。 # Section 6 * 把莫队过程中的查询再离线一下，因此是“二次离线”。 * 在计算**新加入元素对所有区间中元素**贡献时十分有用。 * 一个套路是将贡献容斥成 $[1,x]$ 对 $y$ 的贡献后计算。 * 二次离线莫队比较难写（相对前面的水题）。 * 个人建议调不出来的时候理解一下你的代码每一步在算什么。 ## [P4887](https://www.luogu.com.cn/problem/P4887) * 模板题。 * 这个题比较小清新。 ## [(Ynoi2019模拟赛)P5047](https://www.luogu.com.cn/problem/P5047) * 模板题。 * Section 1 最后一题里讲的根号平衡的数据结构忘了吗？没忘这里是可以用上来扔掉树状数组的一只 $\log$ 来达到 $O(n\sqrt n)$ 的复杂度。 ## [(Ynoi2018)P5398](https://www.luogu.com.cn/problem/P5398) * 第十四分块。 * 其实知道这是二次离线就很板子了。 * 计算贡献时拆贡献成因数和倍数。 * 特别注意，算贡献的时候不要算上自身的贡献，最后加回去。 * 卡常。 ## [P5501](https://www.luogu.com.cn/problem/P5501) * 模板题。 * 注意到 $x$ 的贡献是所有比 $x$ 大的数的和加上 $x$ 乘比 $x$ 小的数的数量加 $1$。 * 直接暴力维护两个贡献即可。 ## [(Ynoi2007)P7448](https://www.luogu.com.cn/problem/P7448) * 和 P7601 是双倍经验。 * 二次离线莫队后转化的问题需要分块套分块结构解决，具体可以看我的题解。 # Section 7 * 莫队的本质：移动端点，维护答案 ## [P3604](https://www.luogu.com.cn/problem/P3604) * 由于字符集不大，考虑直接压缩每个区间的状态成一个数。 ## [P5268](https://www.luogu.com.cn/problem/P5268) * $[l_1,r_1]$ 和 $[l_2,r_2]$ 的贡献可以拆成 $[1,r_1],[1,r_2]$ 和 $[1,l_1-1],[1,l_2-1]$ 的贡献减去 $[1,l_1-1],[1,r_2]$ 和 $[1,r_1],[1,l_2-1]$ 的贡献。 * 拆询问，$(l,r)$ 表示的是 $[1,l]$ 和 $[1,r]$ 的答案。 ## [P4462](https://www.luogu.com.cn/problem/P4462) * 前缀异或记录一下就好了。和 CF617E 是双倍经验。 * CF617E 记得数组开大一点。 * 注意 $k=0$ 的时候需要特殊处理一下。 ## [(Ynoi2016)P4689](https://www.luogu.com.cn/problem/P4689) * 模板题。 * 需要转化dfs序后求解，同上上题。 * 对于拆 $16$ 个询问的方法略微卡常。 * 卡不过去的同学可以试试随机选根，跑得飞快。 # Section 8 由于掌握套路之后莫队本身其实非常简单，因此想要出非板子题，只能将题目与别的知识结合，让你即使知道这是莫队也无从下手。 此部分需要一些其他知识点的小技巧。 ## [P3245](https://www.luogu.com.cn/problem/P3245) * 注意到数 $\overline{s_ls_{l+1}\cdots s_r}$ 可以看作 $\overline{s_ls_{l+1}\cdots s_n}-\overline{s_{r+1}s_{r+2}\cdots s_n}$，即两个后缀之差。 * 显然如果后缀差模 $p$ 为 $0$，这个数乘以 $10^{x}$ 后就一定是 $p$ 的倍数了，于是就可以莫队了。 * 注意 $p=2,5$ 的时候特判。 ## [(Ynoi2015)P5071](https://www.luogu.com.cn/problem/P5071) * 前置知识：Pollard-Rho * 先对于 $1000$ 以内的质数分解质因子。 * 然后再 Pollard-Rho 分解 $1000$ 以上的质因子。 * 离散化后莫队计算 $1000$ 以上质因子的答案。 * 前缀和计算 $1000$ 以内质因子的答案。 * 卡常难度在 PR 上。 ## [CF1511G](https://www.luogu.com.cn/problem/CF1511G) * 显然可以转化成 nim 问题。 * 考虑移动端点的时候已有的数的集合会发生什么。 * 全局 $\pm1$，全局异或和，插入删除可以倒建 trie $O(\log n)$ 做。 * 因此可以 $O(n\sqrt n\log n)$ 解决。 * 需要卡常。 ## [(Ynoi2015)P5072](https://www.luogu.com.cn/problem/P5072) * 这个题中莫队只是个工具，思维难度为主 * 先转化要求的东西成每个数的贡献。 * 转化后每个数的贡献就是 $x\times(2^{len}-2^{len-cnt_x})$ * 然而由于每次模数不同，我们不能直接维护答案，只能维护每个数的出现次数。 * 这个时候用一个根号分治的 trick，维护 $cnt<320$ 的数的和，以及 $cnt\geq320$ 的所有数，然后计算即可。 * 注意到这里需要使用光速幂消掉一只 $\log$。 # Section 9 To be continued......?