OI-wiki 莫队二次离线算法详解：把莫队转移再次离线，用差分与扫描线突破 O(1) 转移瓶颈-北京尧图网络

OI-wiki 莫队二次离线算法详解把莫队转移再次离线用差分与扫描线突破 O(1) 转移瓶颈【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读莫队算法擅长处理「区间询问、单次转移 $O(1)$」的题目但现实中很多区间统计问题如区间逆序对数、区间内「Abbi 值」之和在移动端点时单次转移代价高达 $O(\log n)$ 甚至更高直接套用莫队会让总复杂度退化。莫队二次离线Mos Algorithm with Secondary Offline正是为此设计的优化技巧它观察到转移的贡献往往可以差分于是把莫队的每一次指针移动「再次离线」下来用扫描线批量处理配合值域分块把单次查询压到 $O(1)$。阅读本文后你将掌握二次离线的核心思想、四方向转移的差分写法、空间优化技巧并能读懂 OI-wiki 仓库中两份完整的 P5047 与 P5501 参考实现。适用范围与核心思想何时需要使用二次离线普通莫队的成立前提是从区间 $[l,r]$ 的答案可以 $O(1)$ 扩展到相邻区间 $[l-1,r],[l1,r],[l,r1],[l,r-1]$。一旦单次转移不是 $O(1)$比如需要查询「某个数在区间内的排名」每次转移至少是 $O(\log n)$此时直接使用莫队——即使调整块长——也会导致复杂度不正确。二次离线解决这一问题的切入点是转移产生的贡献如果可以差分就把这些转移拆开离线下来用其它算法批量处理从而绕开单次转移的昂贵代价。差分的基本记号设 $f(x,l,r)$ 表示 $x$ 关于区间 $[l,r]$ 产生的贡献。当把当前区间 $[l,r]$ 扩展到 $[l,r1]$ 时我们要求的是 $f(a_{r1},l,r)$。若该函数关于区间可差分则$$ f(a_{r1},l,r)f(a_{r1},1,r)-f(a_{r1},1,l-1) $$其中第一项 $f(a_{r1},1,r)$ 是前缀形式可以针对每个 $r$ 预处理出来本质上是 $O(n)$ 次顺序插入第二项 $f(a_{r1},1,l-1)$ 是带参数的前缀查询把每一项离线存到对应的位置 $l-1$ 上从小到大枚举端点用扫描线批量处理。其余三个转移方向$r$ 缩小、$l$ 拓展、$l$ 缩小都可以类似处理。这种「在莫队这个离线算法之上将转移再次离线处理」的算法就叫莫队二次离线。例题一区间逆序对数Luogu P5047题目与差分建模Luogu P5047 「Ynoi2019 模拟赛」Yuno loves sqrt technology II 要求给定长为 $n$ 的序列 $a$$m$ 次询问每次查询一个区间的逆序对数。数据范围 $1\le n,m\le 10^5$$0\le a_i\le 10^9$。直接莫队每次转移至少是 $O(\log n)$ 的需要查询排名。观察可知每次转移要求的信息是「一个数在某个区间内的排名」而这一信息关于区间可以差分因此考虑二次离线。设 $f(x,r)$ 表示 $[1,r]$ 区间内比 $a_x$ 大的数的个数$g(x,r)$ 表示 $[1,r]$ 区间内比 $a_x$ 小的数的个数。四种指针移动带来的答案变化量可以写作移动方向变化量表达式$[l,r]$ 拓展至 $[l,r1]$$f(r1,r)-f(r1,l-1)$$[l,r]$ 缩小至 $[l,r-1]$$-f(r,r-1)f(r,l-1)$$[l,r]$ 拓展至 $[l-1,r]$$g(l-1,r)-g(l-1,l-2)$$[l,r]$ 缩小至 $[l1,r]$$-g(l,r)g(l,l-1)$预处理与二次离线式子中的 $f(x,x-1)$ 与 $g(x,x-1)$ 这类「前缀对自身」的项可以使用树状数组提前 $O(n\log n)$ 预处理出来其余的 $f(x,p)$ 与 $g(x,p)$ 项将 $x$ 离线存在端点 $p$ 上按端点顺序批量处理。空间优化技巧处理每个询问时离线到 $p$ 上的 $x$ 其实都是连续的一段对应指针一次连续滑动因此不必把每次移动都存下来只需存下调整的这一段。这样空间从总移动次数 $O(n\sqrt{m})$ 下降到询问数 $O(m)$。值域分块与复杂度二次离线下来的问题是向一个集合中插入数查询某个数在集合中的排名。莫队总共移动端点的次数是 $O(n\sqrt{m})$而数组总长只有 $O(n)$因此使用 $O(\sqrt{n})$ 插入、$O(1)$ 查询的值域分块来平衡复杂度。最终本题在 $O(n\sqrt{m}n\sqrt{n})$ 的时间复杂度与 $O(nm)$ 的空间复杂度下解决。代码逐段解析参考实现见仓库 docs/misc/code/mo-algo-secondary-offline/mo-algo-secondary-offline_1.cpp。constexpr int MAX 1e5 5; constexpr int MAXX 4e2 5; constexpr int MX 1e5;MAX为序列长度上限MAXX为值域分块的块数上限MX为值域上限此处利用了 $n\le 10^5$ 且离散化后的值域恰为 $[1,n]$。值域分块init、mdf、qryvoid init() { sz sqrt(MX); for (int i 1; i sz; i) { st[i] (MX / sz) * (i - 1) 1; ed[i] (MX / sz) * i; } ed[sz] MX; for (int i 1; i sz; i) { for (int j st[i]; j ed[i]; j) bl[j] i; } } void mdf(int x) { for (int i bl[x]; i sz; i) b1[i]; // 块级后缀计数 for (int i x; i ed[bl[x]]; i) b2[i]; // 块内前缀计数 } int qry(int x) { if (!x) return 0; return b1[bl[x] - 1] b2[x]; // 整块前缀块内前缀O(1) 查询排名 }mdf为 $O(\sqrt{n})$ 插入b1维护「大于等于某块」的整块计数b2维护「块内从 $x$ 到块尾」的散块计数qry(x)返回集合中 $\le x$ 的元素个数实现 $O(1)$ 排名查询。离散化与预处理std::sort(b 1, b n 1); int len std::unique(b 1, b n 1) - b - 1; for (int i 1; i n; i) a[i] std::lower_bound(b 1, b len 1, a[i]) - b; for (int i 1; i n; i) { p1[i] qry(a[i] - 1); // 前缀中小于 a[i] 的个数 p2[i] qry(n) - qry(a[i]); // 前缀中大于 a[i] 的个数 mdf(a[i]); }这里p1[i]即 $g(i,i-1)$$[1,i-1]$ 中比 $a_i$ 小的数p2[i]即 $f(i,i-1)$$[1,i-1]$ 中比 $a_i$ 大的数正是上述表格中可预处理的第一类项。莫队排序与离线收集核心部分bool cmp(Q a, Q b) { if (a.l / _sz ! b.l / _sz) return a.l b.l; return ((a.l / _sz) 1) ? a.r b.r : a.r b.r; // 奇偶化排序 }块长取_sz sqrt(m)并使用奇偶化排序与普通莫队优化一致详见 docs/misc/mo-algo.md减少右指针移动次数。for (int i 1, L 1, R 0; i m; i) { int l q[i].l, r q[i].r; if (L l) v[R].push_back({l, L - 1, i, 1, 0}); // 左指针左移的“附加段” while (L l) { --L; q[i].ans - p1[L]; } if (R r) v[L - 1].push_back({R 1, r, i, -1, 1}); // 右指针右移的“附加段” while (R r) { R; q[i].ans p2[R]; } if (L l) v[R].push_back({L, l - 1, i, -1, 0}); while (L l) { q[i].ans p1[L]; L; } if (R r) v[L - 1].push_back({r 1, R, i, 1, 1}); while (R r) { q[i].ans - p2[R]; --R; } }每个while循环只累加「可预处理项」$p1/p2$来自 $f(x,x-1)$ 型前缀每个if把「需要二次离线的项」对应的连续下标区间以结构体N{l, r, id, x, y}存入v[p]其中x为符号$\pm1$y区分是查「比它小的个数」$g$ 类还是「比它大的个数」$f$ 类。这就是空间从 $O(n\sqrt{m})$ 优化到 $O(m)$ 的关键——每段只存一个区间而非逐点存储。扫描线批量处理for (int i 1; i n; i) { mdf(a[i]); for (N j : v[i]) { for (int k j.l; k j.r; k) { if (j.y 0) q[j.id].ans j.x * qry(a[k] - 1); // 统计小于 a[k] 的 else q[j.id].ans j.x * (i - qry(a[k])); // 统计大于 a[k] 的 } } }枚举端点 $i$ 时逐个插入 $a_i$然后处理挂在 $i$ 上的所有二次离线段每个位置 $k$ 的贡献用 $O(1)$ 的值域分块查询直接算出。注意此时qry(a[k]-1)对应 $g(k,i)$、i - qry(a[k])对应 $f(k,i)$与差分式严格对应。答案还原for (int i 2; i m; i) q[i].ans q[i - 1].ans; // 前缀和还原 for (int i 1; i m; i) ans[q[i].id] q[i].ans;关键注意事项二次离线求得的是每次移动的答案变化量而非答案本身必须对其做前缀和才能得到最终答案。仓库中给出了配套的样例数据 docs/misc/examples/mo-algo-secondary-offline/mo-algo-secondary-offline_1.in 与_1.ans可用来验证实现正确性。例题二区间 Abbi 值之和Luogu P5501题目与差分建模Luogu P5501 「LnOI2019」来者不拒去者不追要求多次询问区间 $[l,r]$ 中所有数的「Abbi 值」之和。Abbi 值定义为若 $a_i$ 在询问区间 $[l,r]$ 中是第 $k$ 小则它的 Abbi 值等于 $ka_i$。设 $f(x,r)$ 为 $[1,r]$ 中比 $a_x$ 大的数之和$g(x,r)$ 为 $[1,r]$ 中比 $a_x$ 大的数的个数。向右移动右端点时产生的贡献为$$ f(r,r-1)-f(r,l-1)a_r\left(r-l1-\left(g(r,r-1)-g(r,l-1)\right)\right) $$其余方向同理。与例题一相同上式中的 $f(r,r-1)$ 与 $g(r,r-1)$ 可以直接预处理其余项离线到另一端点上做扫描线。实现要点与复杂度参考实现见仓库 docs/misc/code/mo-algo-secondary-offline/mo-algo-secondary-offline_2.cpp。与例题一相比本实现做了三处调整值域分块同时维护个数与和。mdf(x)在更新块计数sm1/sm2的同时累加sm3/sm4对应数值之和qry返回个数、_qry返回数值之和从而 $O(1)$ 同时回答「比 $x$ 小的个数」和「比 $x$ 小的数之和」void mdf(ll x) { sm x; for (int i bl[x]; i sz; i) { sm1[i]; sm3[i] x; } for (int i x; i ed[bl[x]]; i) { sm2[i]; sm4[i] x; } } ll qry(ll x) { return sm1[bl[x] - 1] sm2[x]; } // 个数 ll _qry(ll x) { return sm3[bl[x] - 1] sm4[x]; } // 数值和预处理项。pre[i] qry(a[i] - 1) * a[i] sm - _qry(a[i])表示$[1,i-1]$ 中比 $a_i$ 小的数个数乘以 $a_i$加上比 $a_i$ 大的数之和——这正是移动端点时可以直接代入的「前缀贡献」。块长与最终答案。块长取_sz n / sqrt(m)由于 Abbi 值是「每个元素自身的值 $\times$ 排名」之和最终答案需要在变化量前缀和的基础上加上区间元素值总和用前缀和s[i]差分得到ans[q[i].id] q[i].ans s[q[i].r] - s[q[i].l - 1];从代码结构看本实现处理的依旧是 $O(n)$ 次插入、$O(n\sqrt{m})$ 次排名的二次离线问题因此同样使用值域分块解决整体复杂度与例题一同阶。实战要点总结差分是前提只有当单次转移的贡献能写成「关于区间端点可差分」的形式时二次离线才适用。典型信号是题目要求的信息本身是「排名」「比某数大/小的个数或和」这类可作差量。两类项分开处理形如 $f(x,x-1)$ 的「前缀自身」项直接预处理形如 $f(x,p)$$p$ 是历史端点的项离线到 $p$ 上扫描线批量算。空间优化指针连续滑动产生的待离线项是一段连续区间按「段」存储可把空间从 $O(n\sqrt{m})$ 压到 $O(m)$。值域分块打辅助总移动次数 $O(n\sqrt{m})$ 而插入次数只有 $O(n)$用 $O(\sqrt{n})$ 插入、$O(1)$ 查询的值域分块即可平衡无需树状数组的 $O(\log n)$。答案前缀和二次离线得到的是每次移动的变化量必须对询问依次前缀和并注意回答时按原顺序还原如例题二的额外区间和。可与普通莫队优化叠加排序仍可沿用普通莫队的奇偶化排序参见 docs/misc/mo-algo.md块长一般取 $n/\sqrt{m}$ 量级实践中以数据范围为准。参考资料docs/misc/mo-algo.md普通莫队的排序、复杂度分析与奇偶化优化是二次离线的前置知识。docs/misc/mo-algo-secondary-offline/mo-algo-secondary-offline_1.cppP5047 完整实现。docs/misc/mo-algo-secondary-offline/mo-algo-secondary-offline_2.cppP5501 完整实现。docs/misc/examples/mo-algo-secondary-offline/两份代码对应的样例输入输出可用于自测验证。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

OI-wiki 莫队二次离线算法详解：把莫队转移再次离线，用差分与扫描线突破 O(1) 转移瓶颈

相关推荐

嵌入式面试高频考点三维能力模型解析

3毛钱芯片的BOM优化与低功耗设计实践

使用 Go 迭代器（iter.Seq）进行多重集比较：深入解析 lo 库 it.ElementsMatch 的实现与应用

更多资讯

Stable Diffusion Forge 本地部署完整指南：3 步跑通 AI 绘图，数据全程本地闭环

跨平台桌面便签开发实录：从Electron到Tauri的技术选型与踩坑指南

无人机BMS与电机驱动中的精密采样电阻选型指南

氮化镓充电器原理与实战指南：高频开关如何提升功率密度

C#截图工具开发实战：从全屏到定时与窗口识别

Tolaria 富文本代码块 Shiki 语言直注册方案：基于 @shikijs/langs 的懒加载语法扩展与别名规范化

今日更新

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？