OI Wiki 莫队算法如何离线处理序列上的区间询问【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki当你有一组区间询问且满足两个条件——可以离线处理、从区间[l,r]的答案能在 $O(1)$ 内扩展到相邻区间[l-1,r]、[l1,r]、[l,r1]、[l,r-1]——就可以用 OI-wiki 中的莫队算法把全部询问的答案在 $O(n\sqrt{n})$ 内求出假设 $nm$。典型任务是 「国家集训队」小 Z 的袜子给定长度为 $n$ 的序列和 $m$ 个询问[l,r]求在区间内随机取两个不同位置、两数相等的概率。以下内容全部来自仓库中的 莫队算法 及其配套代码、样例目标是让你能按文档完成一次完整实现并用样例数据核对结果。适用前提什么题能用莫队在写代码前先确认题目满足 文档 给出的形式条件询问可以离线所有询问已知可以重新排序最后再按原顺序输出答案可以在 $O(1)$ 内从当前区间推一步到相邻区间。也就是说你需要实现一个move(pos, sign)把端点移动一步时$O(1)$ 更新当前答案nowAns。如果加入容易、删除困难或反过来普通莫队不适用可改用 回滚莫队它只在 $O(n\sqrt{m})$ 内使用单向操作另一方向交给回滚如果询问带单点修改需要 带修改的莫队如果是子矩阵询问是 二维莫队。本文只走普通莫队这一条主路径。核心模板排序 双指针移动莫队的做法是把所有询问按排序规则重排顺序处理每个询问都从上一个询问的区间出发暴力移动l、r两个端点到目标位置每移动一步就更新答案。排序规则对区间[l,r]以 $l$ 所在块的编号为第一关键字、$r$ 为第二关键字从小到大排序。块大小文档给出的基本取法是BLOCK_SIZE int(ceil(pow(n, 0.5)));但块长设定对复杂度影响很大设块长为 $S$总复杂度是 $O(n^2/S mS)$取 $S n/\sqrt{m}$ 时最优为 $O(n\sqrt{m})$。文档特别警告若 $m$ 与 $\sqrt{n}$ 同阶却把块长误设为 $\sqrt{n}$可以构造出 $O(n\sqrt{n})$ 而不是 $O(n^{5/4})$ 的数据。所以 $m$ 明显小于 $n$ 时应按 $n/\sqrt{m}$ 取块长。主循环模板见 mo-algo.md 的实现一节void move(int pos, int sign) { // update nowAns } void solve() { BLOCK_SIZE int(ceil(pow(n, 0.5))); sort(querys, querys m); for (int i 0; i m; i) { const query q querys[i]; while (l q.l) move(--l, 1); while (r q.r) move(r, 1); while (l q.l) move(l, -1); while (r q.r) move(r--, -1); ans[q.id] nowAns; } }第一个询问直接暴力算出$O(n)$之后的询问全部靠移动端点转移。关键坑四个 while 循环的顺序不能乱写由于l和--r的存在四个循环的先后位置关系很关键文档强调不能随意改变它们之间的位置关系。原理是移动过程相当于“加入[1,r]、删除[1,l-1]”若某时刻出现 $l r1$就会有元素的加入次数为负——用set之类结构维护区间元素时就会触发“删除不存在的元素”的错误。文档对 24 种排列逐一检验过只有 6 种正确共同特点是前两步扩大区间l--或r、后两步缩小区间l或r--。上面模板的顺序先加左、加右再减左、减右就是其中之一。完整例题小 Z 的袜子文档中的完整参考代码 实现了这道题可以直接取来编译运行。它的要点col[i]代码中cnt记录颜色 $i$ 的当前出现次数sum记录可行的配对方案数加入位置i时配对数增加cnt[i]即 $\binom{a1}{2}-\binom{a}{2}a$ 的化简结果删除时先减再扣cnt[i]答案为sum / C(r-l1, 2)用gcd约分后以a/b输出区间长度为 1 时直接记答案0/1不走移动循环块大小取maxn sqrt(n)比较函数同时实现了下面的奇偶化排序。完整的加删逻辑摘自 mo-algo_1.cppvoid add(int i) { sum cnt[i]; cnt[i]; } void del(int i) { cnt[i]--; sum - cnt[i]; }移动端点与输出部分for (int i 0, l 1, r 0; i m; i) { // 具体实现 if (a[i].l a[i].r) { ans1[a[i].id] 0, ans2[a[i].id] 1; continue; } while (l a[i].l) add(c[--l]); while (r a[i].r) add(c[r]); while (l a[i].l) del(c[l]); while (r a[i].r) del(c[r--]); ans1[a[i].id] sum; ans2[a[i].id] (long long)(r - l 1) * (r - l) / 2; } for (int i 0; i m; i) { if (ans1[i] ! 0) { long long g gcd(ans1[i], ans2[i]); ans1[i] / g, ans2[i] / g; } else ans2[i] 1; cout ans1[i] / ans2[i] \n; }注意四个while的顺序是l--、r、l、r--先扩大、后缩小正是上一节说的正确写法。用仓库样例核对结果仓库自带这道题的样例输入 mo-algo_1.in 和标准答案 mo-algo_1.ans样例输入6 4 1 2 3 3 3 2 2 6 1 3 3 5 1 6文档给出的对应答案即.ans文件内容4 个询问按原顺序输出2/5 0/1 1/1 4/15验证方法把 mo-algo_1.cpp 用 C 编译器编译例如g -O2 mo-algo_1.cpp -o mo运行./mo mo-algo_1.in输出与上面.ans文件逐行一致即说明实现正确。lr的询问本样例的第 2 问1 3并非此类但1/3中区间3 5等由主循环处理走的是模板里单元素特判分支两类分支都被样例覆盖到了。可选优化奇偶化排序文档指出一处可省下的指针移动处理完奇数块后r指针不必先退回 1 再前进可以在返回途中顺带处理偶数块的询问。做法是——奇数块的询问r升序偶数块的询问r降序一般能让程序快 30% 左右。参考代码 已经内置了这一优化比较函数为struct query { int l, r, id; bool operator(const query x) const { // 重载运算符 if (l / maxn ! x.l / maxn) return l x.l; return (l / maxn) 1 ? r x.r : r x.r; } } a[N];文档同时给出了不压行的等价写法并附了一个必须注意的细节不能写成r x.r或r x.r。sort要求严格弱序若出现a b与b a同时为真会直接运行错误文档链接到了 常见错误 中“会导致 RE”一节。压行版同理需要r x.r的特判否则在同一奇数块且r相等时会出现同样问题。边界与扩展路径块长务必按规模计算$n$、$m$ 同阶取 $\sqrt{n}$ 即可$m$ 远小于 $n$ 时取 $n/\sqrt{m}$否则复杂度会明显劣化文档给出的 $O(n\sqrt{n})$ vs $O(n^{5/4})$ 反例。转移必须是 $O(1)$模板的复杂度结论建立在move为 $O(1)$ 的前提上若单步转移代价高$O(n\sqrt{n})$ 不再成立。询问带修改见 带修改的莫队块长取 $n^{2/3}$按左端点块、右端点块、时间三个关键字排序总复杂度 $O(n^{5/3})$$n,m,t$ 同阶时。只有单向操作可实现见 回滚莫队复杂度 $O(n\sqrt{m})$块长取 $n/\sqrt{m}$。子矩阵询问见 二维莫队块长 $B n \cdot q^{-1/4}$文档特别提示计算结果可能为 0需要特判。莫队算法本身还有背景介绍可阅读 莫队算法导言。以上各条路径都围绕同一件事——把区间询问离线排序后用双指针转移——按你的题目是否带修改、删除是否可实现、询问维数是 1 还是 2 来选择对应版本即可。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考