1. 从暴力到优雅理解莫队算法的核心思想如果你刷过一些在线评测平台OJ的题目尤其是那些关于区间查询的问题你大概率见过“莫队”这个名字。它听起来有点神秘不像“动态规划”或“二分查找”那样直观。我第一次遇到它时是在一道要求多次查询某个区间内不同数字个数的题目上。最朴素的想法对于每次查询我都遍历一次区间用一个哈希表或者叫计数器来统计时间复杂度是 O(N*Q)N 是数组长度Q 是查询次数。当 N 和 Q 都达到 10^5 这个量级时这个 O(10^10) 的复杂度显然会超时。莫队算法就是为了解决这类离线区间查询问题而生的。它的核心思想非常巧妙通过合理地重新排列查询的顺序并利用上一次查询的结果来增量式地计算当前查询的答案从而将时间复杂度从 O(N*Q) 降低到大约 O((NQ) * sqrt(N))。这里的“离线”意味着我们预先知道所有要处理的查询可以自由安排处理它们的顺序而不是必须按照提问的顺序来回答。我们可以用一个生活化的类比来理解想象你是一个仓库管理员仓库是一排长长的货架数组货架上放着各种商品数组元素。现在有很多张采购单查询每张单子要求你统计从第 L 个货架到第 R 个货架之间一共有多少种不同的商品区间内不同数字的个数。暴力法每来一张单子你就从 L 走到 R一边走一边清点。处理完一张单子后回到仓库门口等待下一张单子再重新走过去。你走了很多重复的路。莫队法你拿到所有采购单后不是按提交顺序处理而是聪明地给它们排了个队。你从第一张单子指定的位置开始走处理完后你不是回到起点而是直接“蠕动”到下一张单子指定的位置。比如你刚才在统计 [3, 10] 区间的商品下一张单子要查 [4, 12] 区间你只需要向右多走两步从位置11走到12同时向左少走一步从位置3退到4并相应地更新你的统计结果。这样你走的总路程时间复杂度就大大减少了。这个“蠕动”的过程就是莫队算法的精髓维护一个当前区间[cur_l, cur_r]和对应的答案ans。当要处理下一个查询[L, R]时我们通过四个while循环让cur_l和cur_r分别移动到L和R并在移动的过程中更新ans。while(cur_l L) add(--cur_l);// 左指针向左扩展加入新元素while(cur_r R) add(cur_r);// 右指针向右扩展加入新元素while(cur_l L) del(cur_l);// 左指针向右收缩移除元素while(cur_r R) del(cur_r--);// 右指针向左收缩移除元素这里的add(pos)和del(pos)函数就是根据位置pos上的值来更新我们维护的答案数据结构比如计数器、和、或其他复杂状态。那么最关键的问题来了我们如何给这些查询排序才能让“蠕动”的总距离最短如果胡乱排序可能从一个很左的区间跳到一个很右的区间指针移动距离依然很大效率提升就不明显。莫队的解决方案是分块排序。2. 分块排序莫队高效运转的引擎分块排序是莫队算法的灵魂所在它决定了指针移动的效率。其规则非常简单却极其有效将整个数组分成若干块block。通常块的大小block_size取sqrt(N)向下取整。例如数组长度 N100000那么block_size ≈ 316总块数约为 316。对于每个查询[L, R]首先按照L所在的块编号进行升序排序。也就是说所有左端点L落在第 0 块的查询排在最前面然后是第 1 块依此类推。对于左端点L在同一块内的所有查询再按照右端点R进行排序。这里有一个重要的优化点为了进一步减少指针的摆动对于奇数编号的块第1、3、5...块内部按R升序排序对于偶数编号的块第0、2、4...块内部按R降序排序。这就是常说的“奇偶化排序”或“蛇形排序”。这样排序后当处理完一个块内最后一个查询右端点在最右端后处理下一个块时右指针不需要一下子从最右端拉回到最左端而是可能已经在比较靠左的位置减少了移动距离。为什么这样排序是高效的直观理解是它保证了左指针cur_l在块内变化时移动范围被限制在约sqrt(N)的长度内。而右指针cur_r在整个处理过程中总体上只会单调地向右移动尽管在奇偶排序下会有一些折返在整个算法过程中右指针移动的总次数大约是 O(N * sqrt(N))。左指针在块内移动是 O(sqrt(N)) 每次总共 Q 次查询所以左指针移动也是 O(Q * sqrt(N))。综合起来总时间复杂度就是 O((NQ) * sqrt(N))。注意块大小的选择并非一成不变。理论最优值sqrt(N)是一个很好的起点但在实际题目中特别是当 Q 和 N 规模不同时可以微调。一个更通用的经验公式是block_size N / sqrt(Q)或block_size pow(N, 2.0/3)对于带修改的莫队。在竞赛中直接取block_size sqrt(N)或block_size 500对于 N~1e5在绝大多数情况下都能很好地工作。让我们用代码来具体实现这个排序逻辑。假设我们有一个结构体Query来存储每次查询。struct Query { int l, r, id; // id 用于记录原始查询顺序以便最后按序输出答案 }; int block_size; // 块大小 bool cmp(const Query a, const Query b) { // 按左端点所在块排序 if (a.l / block_size ! b.l / block_size) return a.l / block_size b.l / block_size; // 在同一块内奇偶化排序 if ((a.l / block_size) 1) // 奇数块 return a.r b.r; else // 偶数块 return a.r b.r; }排序完成后我们初始化cur_l 1,cur_r 0,ans 0这是一个空区间[1, 0]表示还没有任何元素。然后按排序后的顺序依次处理每个查询通过上述四个while循环调整区间并更新答案最后将答案存入res[query.id]。3. 核心操作add 与 del 函数的实现逻辑add(pos)和del(pos)是莫队算法的血肉它们定义了如何根据元素的增删来更新我们维护的答案。不同的题目这两个函数的实现完全不同。我们以最经典的例题SPOJ DQUERY - D-query为例题目要求多次查询区间内不同数字的个数。我们需要维护什么状态一个计数器数组cnt[x]记录当前区间内数值x出现的次数。当前答案ans记录当前区间内cnt[x] 0的x的个数即不同数字的个数。那么add和del的逻辑就非常清晰了add(pos)将位置pos上的值val arr[pos]加入当前区间。cnt[val]。如果cnt[val]从 0 变为 1说明这个数字新出现了那么ans。del(pos)将位置pos上的值val arr[pos]从当前区间移除。cnt[val]--。如果cnt[val]从 1 变为 0说明这个数字完全消失了那么ans--。代码实现如下int cnt[MAX_VAL]; // 假设数值范围是 MAX_VAL int ans; // 当前答案 int arr[MAXN]; // 原始数组 void add(int pos) { int val arr[pos]; if (cnt[val] 0) { ans; // 新出现一个不同的数 } cnt[val]; } void del(int pos) { int val arr[pos]; cnt[val]--; if (cnt[val] 0) { ans--; // 有一个数完全消失了 } }这就是最基本的形态。然而实际问题往往更复杂。例如查询可能是区间内出现次数为偶数的数字个数、或者是某种配对的数量如逆序对。这时add和del的逻辑就需要更精巧的设计维护的状态也可能更复杂比如需要维护每个数字出现次数的奇偶性或者维护一个 Fenwick Tree树状数组来快速计算贡献。实操心得在实现add和del时务必想清楚状态变化的边界条件。像上面的例子判断是0还是1非常关键。一个常见的错误是写成if (--cnt[val] 0) ans--;这看起来简洁但你必须确保cnt[val]在减之前是大于0的。在莫队算法中由于我们的移动是连续的、合法的这个条件通常满足但养成先操作再判断的习惯更安全。另外如果数值范围很大如 1e9就需要先用离散化Discretization将数值映射到 1~N 的范围内这样才能用数组cnt来存储。4. 从模板到实战解决“区间众数”问题掌握了基础莫队后我们来看一个稍微进阶的应用求区间众数出现次数最多的元素的出现次数。注意是求次数而不是求是哪个数因为众数可能不唯一。题目可以描述为给定一个数组多次查询每次问区间[L, R]内出现次数最多的数字出现了几次。这个问题比统计不同数字个数要难因为增加或删除一个数字时我们维护的“最大出现次数”可能会变化而且这个变化可能不是简单的加减1。例如当前区间众数出现次数是5数字A当我们加入一个数字B时B的出现次数从4变成了5那么现在众数出现次数依然是5但众数集合里多了一个B。如果我们删除了一个数字AA的出现次数从5变成4而另一个数字C的出现次数是4那么众数出现次数可能还是5如果还有其他数字也可能下降到4。我们需要维护更复杂的状态cnt[x]: 数值 x 在当前区间出现的次数。freq[t]:出现次数为 t 的数值有多少个。这是一个非常重要的辅助数组。current_max: 当前区间内最大的t即众数的出现次数。现在分析add(pos)和del(pos)add(pos)设val arr[pos]。旧次数old_cnt cnt[val]。将cnt[val]加1得到新次数new_cnt。因为val的次数从old_cnt变为了new_cnt所以freq[old_cnt]要减1freq[new_cnt]要加1。更新current_max如果new_cnt current_max那么current_max new_cnt。否则如果old_cnt current_max且freq[old_cnt]在减1之后变成了0说明旧的众数次数已经没有任何数字达到了那么我们需要将current_max减1因为现在最高的出现次数至少是current_max - 1。注意这里不能直接current_max--因为可能current_max-1这个次数也没有数字达到。稳妥的做法是在每次del操作后如果freq[current_max] 0就执行current_max--。这是一个延迟更新的技巧。del(pos)逻辑对称。old_cnt cnt[val]。cnt[val]--得到new_cnt。freq[old_cnt]--,freq[new_cnt]注意如果new_cnt 0。关键点检查freq[current_max]是否变为0。如果是则current_max--。因为删除操作只可能减少或维持最大出现次数不可能增加它。代码实现时freq数组的大小需要开到N1因为出现次数最多为区间长度。current_max的初始化是0。int cnt[MAX_VAL], freq[MAXN]; int current_max; void add(int pos) { int val arr[pos]; int old_cnt cnt[val]; cnt[val]; int new_cnt cnt[val]; freq[old_cnt]--; freq[new_cnt]; if (new_cnt current_max) { current_max new_cnt; } } void del(int pos) { int val arr[pos]; int old_cnt cnt[val]; cnt[val]--; int new_cnt cnt[val]; freq[old_cnt]--; if (new_cnt 0) { freq[new_cnt]; } // 延迟更新 current_max if (freq[current_max] 0) { current_max--; } }这个例子展示了莫队如何维护一个非简单聚合的状态。核心思想是不仅要维护每个值的计数还要维护计数的分布情况从而在 O(1) 时间内更新全局最值。踩坑实录在实现“区间众数”时我最开始犯的一个错误是在add函数中也加入了if (freq[current_max] 0) current_max--;的逻辑。这是错误的因为add操作只会增加或保持current_max绝不会减少它。这个检查只在del操作后才需要进行。另一个易错点是freq数组的下标边界new_cnt可能为0此时freq[0]其实没有意义我们也不关心出现0次的数有多少个所以del中要对new_cnt 0才执行freq[new_cnt]避免数组越界或逻辑混乱。5. 带修改的莫队引入时间维度标准的莫队只能处理静态数组的查询。如果题目中穿插着修改操作比如“将位置p的值改为x”我们就需要带修改的莫队Modifiable Mos Algorithm也有人称之为“三维莫队”。其核心思想是引入时间戳维度。我们将所有操作查询和修改按顺序编号。一个查询现在由三个参数确定(L, R, t)其中t表示在这个查询之前我们已经执行了前t个修改操作。算法在处理查询时不仅要移动[L, R]区间指针还要将“当前时间”cur_t通过执行或回退修改操作移动到目标时间t。排序规则也需要调整。我们依然对数组分块块大小通常取pow(N, 2.0/3)。排序优先级为左端点L所在的块。右端点R所在的块注意这里是对R再次分块块大小与L相同。时间戳t。这样三个指针(cur_l, cur_r, cur_t)移动的总复杂度可以控制在 O(N^(5/3)) 左右这比暴力 O(N*Q) 要好得多。实现上我们需要记录每个修改操作(pos, old_val, new_val)。当时间指针需要前进cur_t t时我们就按顺序执行这些修改。如果修改的位置pos位于当前区间[cur_l, cur_r]内我们需要先调用del(pos)移除旧值的影响然后更新数组值再调用add(pos)加入新值的影响。如果pos不在当前区间内我们只需要更新数组的值因为不影响当前统计的答案。时间指针回退cur_t t时逻辑相反我们需要将修改逆操作。带修改莫队的代码框架更复杂调试也更困难。一个关键技巧是修改操作本身要记录它被应用后的新值也要能还原到旧值所以通常把修改操作存储为(pos, pre_val, cur_val)执行时将arr[pos]设为cur_val回退时设回pre_val。个人体会带修改莫队是我觉得莫队系列中最考验细节实现能力的。它像在三维空间里“蠕动”很容易写错add/del与修改执行的顺序。我的经验是严格遵循“先移动区间指针再移动时间指针”的原则并且在移动时间指针时仔细判断修改位置是否在区间内。写完后可以用小数据暴力程序对拍来验证正确性。另外块大小的选择对带修改莫队性能影响更大pow(N, 2.0/3)是一个理论值有时微调比如取int(ceil(pow(N, 2.0/3)))能获得更好的实际运行效果。6. 树上莫队将问题转化到欧拉序上莫队不仅能处理线性序列还能处理树上的路径查询。这就是树上莫队。常见的应用是查询树上两点u, v之间路径上的节点信息例如不同颜色的节点数。关键技巧是利用树的欧拉序Euler Tour Order。我们对树进行一次DFS记录每个节点第一次进入的时间戳in[u]和离开的时间戳out[u]。这样树上任意两点u和v之间的路径可以映射到欧拉序上的一个区间但需要分类讨论假设in[u] in[v]。如果u是v的祖先即lca(u, v) u那么路径u-v上的点对应欧拉序区间[in[u], in[v]]上只出现一次的节点。如果u和v没有祖先关系那么路径对应欧拉序区间[out[u], in[v]]上只出现一次的节点再加上u和v的最近公共祖先LCA。这样树上路径查询就转化为了序列上的区间查询并且这个区间内的每个节点如果出现次数为奇数次在欧拉序中进入和离开各算一次则它就在路径上。我们可以用一个used数组标记节点是否在当前统计区间内add和del操作通过翻转used[x]的状态来模拟节点的加入和移除。具体到莫队实现我们处理的是欧拉序列长度是2N。对于每个查询(u, v)我们计算出对应的欧拉序区间[L, R]以及是否需要额外考虑 LCA 节点。使用标准莫队处理这些区间查询。add(pos)和del(pos)操作的是欧拉序中pos位置对应的节点node。操作是相同的翻转used[node]。如果翻转后used[node]为真即该节点被计入则更新答案例如cnt[color[node]]并检查是否新颜色如果为假则反向更新答案。注意事项树上莫队最容易出错的地方在于LCA的处理。在第二种情况u和v无祖先关系下我们计算的区间[out[u], in[v]]不包含LCA节点因为LCA的进入时间早于out[u]离开时间晚于in[v]。所以在得到区间答案后必须手动把LCA节点的贡献加进去。同时在add/del函数中对于欧拉序上的节点我们通过翻转标记来计数这保证了路径上的点只被计算一次。实现时建议先将LCA预先通过倍增或Tarjan算法求好并存储。7. 回滚莫队应对“删点困难”的场景有些问题中add操作很容易实现但del操作却非常困难或者时间复杂度很高。例如维护区间最大值。加入一个数可以很快更新最大值但删除一个数后如果被删除的正好是最大值我们需要知道次大值是多少这需要维护一个复杂的数据结构如可删除堆使得单次操作无法保证 O(1)。回滚莫队Rollback Mos Algorithm就是为了解决这类“删点难”的问题。它的核心思想是避免执行del操作。如何做到呢我们调整排序和指针移动策略排序规则不变按左端点分块块内右端点升序。对于每一个块i我们处理所有左端点在这个块内的查询。初始化将莫队的右指针cur_r设置在当前块i的右边界即(i1)*block_size - 1左指针cur_l设置在这个右边界的右边一位即cur_r 1。这是一个空区间。对于这个块内的每个查询[L, R] a. 由于块内查询按R升序所以R总是大于等于上一个查询的R。因此我们可以安全地只使用add操作将cur_r向右移动到R。 b. 关键的来了对于左指针cur_l我们需要将它移动到L。因为L在当前块内移动距离不超过block_size即sqrt(N)。我们采用临时回滚的方式 - 先记录下当前cur_l移动前的状态包括ans和相关的计数器如cnt数组。 - 然后我们只使用add操作将cur_l从当前位置向左移动到L注意cur_l初始在块右边界外所以是向左移动。在这个过程中我们更新一个“临时答案”和“临时计数器”。 - 得到这个查询的答案后我们回滚将cur_l移回原来的位置并且利用之前保存的状态恢复ans和全局计数器。这样我们就避免了del操作。处理完当前块的所有查询后我们彻底清空所有状态移动到下一个块重复步骤3-4。可以看到回滚莫队牺牲了一些常数时间需要保存和恢复状态但将难以实现的del操作转化为了add操作和状态回滚。它的时间复杂度依然是 O((NQ) * sqrt(N))。一个典型的应用是求区间内相同数字的最大间隔即最远的两个相同数字的距离。add一个数时我们可以更新这个数第一次和最后一次出现的位置从而更新最大间隔。但del一个数时如果它恰好是构成最大间隔的端点我们很难快速找出新的最大间隔。使用回滚莫队我们只需要实现add对于左指针的移动我们通过临时扩展和回滚来处理。经验技巧实现回滚莫队时状态保存和恢复要小心。对于简单的计数器数组我们可以用memcpy或vector赋值来备份和恢复。但更通用的做法是在向左移动cur_l进行“临时扩展”时记录下所有被修改过的变量比如哪些cnt值被改变了改变前的值是什么在回滚时再将这些变量改回去。这类似于一个微型的“事务”操作。另外块大小的选择可以更激进一些因为左指针移动的成本变高了需要回滚而右指针移动依然是单调的。有时取block_size N / sqrt(Q)能获得更好的平衡。