莫队二次离线
综述
有时我们会遇见一些题目，这些题目看起来很适合使用莫队算法处理，但是他们的单次转移并非是 𝑂(1)O(1)
的，这时直接使用莫队即使调整块长，也会导致复杂度不正确．
此时，如果每次转移对答案的贡献可以进行差分，我们就可以将这些转移拆开离线下来，使用其它算法批量处理．
我们用 𝑓(𝑥,𝑙,𝑟)f(x,l,r) 表示 𝑥x 关于 [𝑙,𝑟][l,r] 产生的贡献．
如我们在将当前区间 [𝑙,𝑟][l,r] 扩展到 [𝑙,𝑟 +1][l,r+1] 时，我们要求的是 𝑓(𝑎𝑟+1,𝑙,𝑟)f(ar+1,l,r)．如果可以差分，我们可以将其写成 𝑓(𝑎𝑟+1,1,𝑟) −𝑓(𝑎𝑟+1,1,𝑙 −1)f(ar+1,1,r)−f(ar+1,1,l−1)，其中第一项我们可以对于每个 𝑟r 都预处理出来，后一项我们可以把每个这样的项都离线存到对应的 𝑙 −1l−1 上，然后从小到大枚举并扫描线处理．其它几个转移的方向也都可以类似地处理．
这一在莫队这个离线算法上，将转移再次离线处理的算法叫做莫队二次离线．
我们结合实际题目来理解．
例题
[Luogu P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II](https://www.luogu.com.cn/problem/P5047)
给你一个长为 𝑛n 的序列 𝑎a，𝑚m 次询问，每次查询一个区间的逆序对数．
数据范围：1 ≤𝑛,𝑚 ≤1051≤n,m≤105，0 ≤𝑎𝑖 ≤1090≤ai≤109．
直接莫队每次转移至少是 𝑂(log𝑛)O(logn) 的，观察可以发现我们每次转移要求的信息是「一个数在某个区间内的排名」，而这一信息关于区间可以差分，因此考虑二次离线．
我们将 [𝑙,𝑟][l,r] 拓展到 [𝑙,𝑟 +1][l,r+1]，要求的是 在 [𝑙,𝑟][l,r] 区间内有多少比 𝑎𝑟+1ar+1 大的数． 我们用 𝑓(𝑥,𝑟)f(x,r) 表示 [1,𝑟][1,r] 区间内比 𝑎𝑥ax 大的数，𝑔(𝑥,𝑟)g(x,r) 表示 [1,𝑟][1,r] 区间内比 𝑎𝑥ax 小的数．则答案的变化量可以写作 𝑓(𝑟 +1,𝑟) −𝑓(𝑟 +1,𝑙 −1)f(r+1,r)−f(r+1,l−1)．
同理 [𝑙,𝑟][l,r] 缩小至 [𝑙,𝑟 −1][l,r−1] 的变化量可以写作 −𝑓(𝑟,𝑟 −1) +𝑓(𝑟,𝑙 −1)−f(r,r−1)+f(r,l−1)；[𝑙,𝑟][l,r] 拓展到 [𝑙 −1,𝑟][l−1,r] 可以写作 𝑔(𝑙 −1,𝑟) −𝑔(𝑙 −1,𝑙 −2)g(l−1,r)−g(l−1,l−2),[𝑙,𝑟][l,r] 缩小至 [𝑙 +1,𝑟][l+1,r] 可以写作 −𝑔(𝑙,𝑟) +𝑔(𝑙,𝑙 −1)−g(l,r)+g(l,l−1)．
对于这些式子中的 𝑓(𝑥,𝑥 −1)f(x,x−1) 和 𝑔(𝑥,𝑥 −1)g(x,x−1)，我们可以使用树状数组提前 𝑂(𝑛log𝑛)O(nlogn) 预处理出来；对于其余的 𝑓(𝑥,𝑝)f(x,p) 和 𝑔(𝑥,𝑝)g(x,p) 项，我们将 𝑥x 离线存在 𝑙l 进行批量处理．
这里有一个优化空间的技巧：我们发现处理每个询问时，离线到 𝑝p 上的 𝑥x 都是连续的一段，因此我们不需要把每次移动都存下，只需要存下调整的一段即可．这样我们的空间可以从总次数 𝑂(𝑛√𝑚)O(nm) 下降到询问数 𝑂(𝑚)O(m)．
现在我们来处理我们二次离线下来的问题：向一个集合中加入数，查询一个数在集合中的排名．莫队总共移动端点的次数是 𝑂(𝑛√𝑚)O(nm) 的，而数组总共只有 𝑂(𝑛)O(n) 的长度，因此我们考虑使用 𝑂(√𝑛)O(n) 插入、𝑂(1)O(1) 查询的值域分块解决这个问题．
至此，我们在 𝑂(𝑛√𝑚 +𝑛√𝑛)O(nm+nn) 的时间复杂度和 𝑂(𝑛 +𝑚)O(n+m) 的空间复杂度下解决了此题．
最后值得注意的是，我们求得的是每次的答案变化量而非答案本身，需要对其进行前缀和才能得到最终的答案．
示例代码
---|---
[Luogu P5501 [LnOI2019] 来者不拒，去者不追](https://www.luogu.com.cn/problem/P5501)
多次询问区间中 [𝑙,𝑟][l,r] 中所有数的「Abbi 值」之和．
Abbi 值定义为：若 𝑎𝑖ai 在询问区间 [𝑙,𝑟][l,r] 中是第 𝑘k 小，那么它的「Abbi 值」等于 𝑘𝑎𝑖kai．
我们不妨令 𝑓(𝑥,𝑟)f(x,r) 是 [1,𝑟][1,r] 中比 𝑎𝑥ax 大的数之和，𝑔(𝑥,𝑟)g(x,r) 是 [1,𝑟][1,r] 中比 𝑎𝑥ax 大的数的数量，那么我们向右移动右端点时，产生的贡献为 𝑓(𝑟,𝑟 −1) −𝑓(𝑟,𝑙 −1) +𝑎𝑟(𝑟 −𝑙 +1 −(𝑔(𝑟,𝑟 −1) −𝑔(𝑟,𝑙 −1)))f(r,r−1)−f(r,l−1)+ar(r−l+1−(g(r,r−1)−g(r,l−1)))，其它几个方向可同理写出，在此不加赘述．
上式中的 𝑓(𝑟,𝑟 −1)f(r,r−1) 和 𝑔(𝑟,𝑟 −1)g(r,r−1) 依旧可以进行预处理，其余的离线到另一端点上，进行扫描线处理．不难发现我们要处理的依然是 𝑂(𝑛)O(n) 次插入、𝑂(𝑛√𝑚)O(nm) 次询问排名的问题，因此同样使用值域分块解决．
示例代码
---|---
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：AtomAlpaca, Tiphereth-A, HeRaNO, Lyccrius, lyccrius, megakite 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用