浅谈莫队的小细节

· · 算法·理论

关于莫队

提起莫队，想必是很多人十分钟爱的暴力算法，毕竟在可以离线的部分区间询问问题当中，只需要花十分钟写一份简单的暴力，就可以获得 50,80 甚至是 100 的分数。

但是在学习简单的莫队的过程中，我也有一些问题以及自己的思考，写在这里分享给大家，希望对热爱或不热爱莫队的你都有帮助。

关于 l,r 的初始值

相信初学莫队，大家都对于 l = 1,r = 0 的写法十分不理解，为什么不能赋值成 l = 0,r = 0 呢？

在这里，我的理解是这样的（欢迎打脸）。

我们先来看莫队过程的代码，我的写法大体长这个样子：

int l = 1,r = 0;
for(int i = 1;i <= m;i++)
{
    int ll = q[i].l;
    int rr = q[i].r;
    while(l < ll) del(a[l]),l++;
    while(l > ll) l--,add(a[l]);
    while(r < rr) r++,add(a[r]);
    while(r > rr) del(a[r]),r--;
    ans[q[i].id] = sum;
}

我们考虑从初始状态需要依次将 l,r 移动到第一个询问处，在这个过程中，假设我们需要将 l,r 均向右移动，那么在这个过程中，我们需要执行下面语句：

    while(l < ll) del(a[l]),l++;
    while(r < rr) r++,add(a[r]);

我们注意观察 1 位置对答案的贡献，当 l = 1,r = 0 时，1 处贡献会由 l 减去一次，由 r 加上一次，不会产生影响。

而如果 l = 1,r = 1，就只有 l 减去一次贡献，而没有 r 加上一次贡献。同理，如果 l = 0,r = 0，那么就只有 r 加上一次贡献，而没有 l 减去，贡献都会错误。

当然，查询区间端点为 1 的时候自己考虑一下就不难发现时没有影响的。

因此，我们要将莫队初始化为 l = 1,r = 0。

关于一些贡献的计算

接下来的问题，并不一定只在莫队中适用，只是恰好最近多次遇到了这个问题，就写在这里，也算是自己一点见解。

先来看个例题。

P4462 [CQOI2018] 异或序列

这道题目，首先一个显然的 trick 是，异或操作是可以类似前缀和去求的，那么我们也就是需要求出区间中有多少对 x,y 满足 pre_x \oplus pre_y = k。

我们考虑如何在移动的过程中加入和删除贡献，不难发现，只要我们将一个数对 x,y 的贡献记录在 x 或者 y 其中一个上即可。那么我们每次加入一个数 x，直接查询对应的 y 的数量，这样 x,y 的贡献只会在插入 x 时被计算到。

如果还是不太明白，我们以删除操作为例，详细讲解一下。

如果此时我们扫描到了一个数 x，想要删除他的贡献。

将 x 对应的 y 分为两类：已经被删除的和未被删除的。

对于已经被删除的，在删除 y 的时候我们会查询到 x，因此 x,y 的贡献已经在 y 处被删除过了。对于没有被删除的 y，我们查询这些 y，并删除贡献，然后从序列中删除 x，那么再删到 y 时也不会查询到 x，不会重复或遗漏。

所以在做查询数对的题目时，我们就不需要考虑莫队插入和删除的顺序，只需要在插入或删除一个数字的时候，在目前的序列中查询并记录贡献即可，这样可以保证贡献被记录在后加入或删除的元素上，不重不漏。

下面还有一道比较难的题目，也是希望大家知道前面统计贡献方法，嫌麻烦的朋友可以直接跳过。

P12480 [集训队互测 2024] Classical Counting Problem

这道题目只听了做法，还没有写代码。

具体做法大家可以参考 这位大神的题解。

最后统计部分，我们需要扫描线扫描 r，将 r_{max} = r 的合法 l,r 对统计贡献。

我们考虑将贡献统计在 l 或 x 其中一个，那么我们插入 x 时直接查询 l，插入 l 时直接查询 x 计算贡献即可，这样可以做到不重不漏。

这部分主要介绍的是统计数对贡献的一种思路，希望对大家有所帮助。