本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-07-20 20:50:18

关于莫队

提起莫队，想必是很多人十分钟爱的暴力算法，毕竟在可以离线的部分区间询问问题当中，只需要花十分钟写一份简单的暴力，就可以获得 $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$ 计算贡献即可，这样可以做到不重不漏。

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