在线莫队学习笔记

lyms_Hz17 · 2025-11-19 21:17:36 · 算法·理论

前言

（似乎叫诗乃莫队）

其实刚学莫队的时候就听说这个了，一直想学来着，在学了主席树后更想学了，然后……

一直到现在我都没学，但是很好造，直接造出来了，你来你也行。

下文分别是几个经典莫队的在线化改造。分别是莫队，带修莫队，回滚莫队，树上莫队。最后是一点点的卡常。

然后前两篇代码因为还处于摸索阶段所以码比较丑，最后一篇代码我还是比较满意的。

正文

先来按着我的理解概述一下在线莫队吧，是一个编码容易但是编码较长，常数较大但是常数好卡的东西。唯一较大的缺陷就是空间好劣……

例题：疯狂的颜色序列

一句话题意：区间数颜色，在线。

这个是出现在我们学校题库主席树专题里的题目，当时就非常想写莫队，可惜啊……

不过现在也来得及。

说是莫队，其实在线莫队在我看来就是个分块，但是不管是预处理的部分还是查询的部分都和莫队十分相似，所以称为莫队也好。

先约定一些东西吧：

令块长为 B，“莫队数组”为莫队需要维护的数组（废话），“莫队状态”指某个状态下的莫队数组及其答案。

大概的过程如下：

1. 预处理每块的“莫队数组”，在这题也就是每个颜色的出现次数，复杂度为 O(n\frac nB) 或 O(n\frac {n^2} {B^2})，原因一会另讲，这题可以做到 O(n\frac nB)。
2. 预处理块与块间的“莫队状态”的答案，复杂度是 O(n\frac nB)。
3. 整块间贡献直接查，然后用“莫队状态”辅助求出贡献，复杂度 O(mB)。

然后就没了，显然这题 B 取到 \frac {n} {\sqrt m} 最优。

在线莫队的空间复杂度通常很劣，会到达 O(n\sqrt n) 甚至更高，实在不行也许可以考虑 unordered_map 并祈祷别卡你（空间和时间都是）。

可以思考一下怎么实现，相信读者一定是会的。

不会做也没关系的说，下面带着代码再来过一遍流程：

for(int i = 1; md[i - 1].pos != n; i ++) {
    int L = B * (i - 1) + 1;
    md[i].pos = std::min(n, B * i);
    for(int j = L; j <= md[i].pos; j ++) lp[j] = i - 1, rp[j] = i; 
    for(int j = 1; j <= md[i].pos; j ++) ++ md[i].cnt[a[j]];
}