专栏文章

浅谈莫队的小细节

xxuyunao
算法·理论参与者 8已保存评论 16

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
16 条
当前快照
1 份
快照标识符
@miotkio3
此快照首次捕获于
2025/12/03 00:55
3 个月前
此快照最后确认于
2025/12/03 00:55
3 个月前
查看原文

关于莫队

提起莫队，想必是很多人十分钟爱的暴力算法，毕竟在可以离线的部分区间询问问题当中，只需要花十分钟写一份简单的暴力，就可以获得 50,8050,80 甚至是 100100 的分数。
但是在学习简单的莫队的过程中，我也有一些问题以及自己的思考，写在这里分享给大家，希望对热爱或不热爱莫队的你都有帮助。

关于 l,rl,r 的初始值

相信初学莫队，大家都对于 l=1,r=0l = 1,r = 0 的写法十分不理解，为什么不能赋值成 l=0,r=0l = 0,r = 0 呢？
在这里，我的理解是这样的（欢迎打脸）。
我们先来看莫队过程的代码，我的写法大体长这个样子：
CPP
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,rl,r 移动到第一个询问处，在这个过程中，假设我们需要将 l,rl,r 均向右移动，那么在这个过程中，我们需要执行下面语句：
CPP
    while(l < ll) del(a[l]),l++;
    while(r < rr) r++,add(a[r]);
我们注意观察 11 位置对答案的贡献，当 l=1,r=0l = 1,r = 0 时，11 处贡献会由 ll 减去一次，由 rr 加上一次，不会产生影响。
而如果 l=1,r=1l = 1,r = 1，就只有 ll 减去一次贡献，而没有 rr 加上一次贡献。同理，如果 l=0,r=0l = 0,r = 0，那么就只有 rr 加上一次贡献，而没有 ll 减去，贡献都会错误。
当然，查询区间端点为 11 的时候自己考虑一下就不难发现时没有影响的。
因此，我们要将莫队初始化为 l=1,r=0l = 1,r = 0。

关于一些贡献的计算

接下来的问题，并不一定只在莫队中适用，只是恰好最近多次遇到了这个问题，就写在这里，也算是自己一点见解。
先来看个例题。
P4462 [CQOI2018] 异或序列
这道题目，首先一个显然的 trick 是，异或操作是可以类似前缀和去求的，那么我们也就是需要求出区间中有多少对 x,yx,y 满足 prex⊕prey=kpre_x \oplus pre_y = k。
我们考虑如何在移动的过程中加入和删除贡献，不难发现，只要我们将一个数对 x,yx,y 的贡献记录在 xx 或者 yy 其中一个上即可。那么我们每次加入一个数 xx，直接查询对应的 yy 的数量，这样 x,yx,y 的贡献只会在插入 xx 时被计算到。
如果还是不太明白，我们以删除操作为例，详细讲解一下。
如果此时我们扫描到了一个数 xx，想要删除他的贡献。
将 xx 对应的 yy 分为两类：已经被删除的和未被删除的。
对于已经被删除的，在删除 yy 的时候我们会查询到 xx，因此 x,yx,y 的贡献已经在 yy 处被删除过了。对于没有被删除的 yy，我们查询这些 yy，并删除贡献，然后从序列中删除 xx，那么再删到 yy 时也不会查询到 xx，不会重复或遗漏。
所以在做查询数对的题目时，我们就不需要考虑莫队插入和删除的顺序，只需要在插入或删除一个数字的时候，在目前的序列中查询并记录贡献即可，这样可以保证贡献被记录在后加入或删除的元素上，不重不漏。
下面还有一道比较难的题目，也是希望大家知道前面统计贡献方法，嫌麻烦的朋友可以直接跳过。
P12480 [集训队互测 2024] Classical Counting Problem
这道题目只听了做法，还没有写代码。
具体做法大家可以参考 这位大神的题解。
最后统计部分，我们需要扫描线扫描 rr，将 rmax=rr_{max} = r 的合法 l,rl,r 对统计贡献。
我们考虑将贡献统计在 ll 或 xx 其中一个，那么我们插入 xx 时直接查询 ll，插入 ll 时直接查询 xx 计算贡献即可，这样可以做到不重不漏。
这部分主要介绍的是统计数对贡献的一种思路，希望对大家有所帮助。

评论

共 16 条评论，欢迎与作者交流。

正在加载评论...