【模板】普通莫队题解

Moya_Rao · 2026-03-24 17:43:32 · 题解

如果你要学习普通莫队，可以考虑先看一下我的普通莫队博客进行一个大致的了解。

以下部分内容节选自上述博客。

这题是一个普通莫队的板子题，在做它之前，我们要先知道什么是莫队，以及普通莫队的思想和实现。

什么是莫队？

莫队，是莫涛发明的一种解决区间查询等问题的算法，基于分块思想，时间复杂度 O(n \sqrt{q})。

通常的莫队题目都需要离线操作。如果题目强制在线就不能用莫队做了喵！

当题目可以在已知区间 [l,r] 的答案的情况下 O(k) 求出 [l,r+1],[l+1,r],[l,r-1],[l-1,r] 的答案（即相邻区间的答案），就可以用莫队在 O(kn\sqrt{q}) 的时间复杂度下求出所有 q 个询问分别的答案了。

通常 k 为 1，有时为 \log n。

普通莫队怎么做？

首先你肯定要想好如何快速求出相邻区间的答案，例如统计区间不同数字个数，可以用桶维护。

知道怎么求相邻区间答案还不够，因为你在查询的时候可能会在序列两端“左后横跳”，到头来可能都不如暴力。因此我们想到要优化。

导致查询的时候乱跳的原因是什么？显而易见，因为我们查询的顺序是乱的。如果对所有查询按照某种顺序排列，是不是就能让它少跳一点，速度也就快一些呢？

当然可以，但问题在于你要怎么排序。很容易想到以 l 为第一关键词、r 为第二关键词分别升序排序，但是这样做效果并不好，甚至依然不如暴力。

这里就不得不提到莫涛大神了。他给出的方法是——分块！

分块后，每个元素 i 都有它所属的块 bel_i 了，我们再按照 bel_l 为第一关键词，bel_r 为第二关键词排序。

为啥这样复杂度就能下降？那就来算算复杂度吧。对于 l，相邻两个区间移动的距离不会超过块长 B；对于 r，每个块的所有区间总共移动的距离不会超过序列总长度 n。假设询问 q 次，则左端点移动次数为 qB，右端点移动次数为 \frac{n^2}{B}，不难发现当 B 取 \sqrt{\frac{n^2}{q}} 时总移动次数最少。

此时，我们的时间复杂度均摊是 O(n \sqrt{q}) 的，能够通过 10^5 规模的题目了。说是有的时候 10^6 也能冲过去呢。

盗用借用知乎上某篇文章的动图展示一下莫队的移动过程。

我们发现这个过程中，当 l 移动到别的一个块中，r 都得左移好长一段，你不觉得这样非常浪费时间吗？是的，所以这里出现了一个优化：奇偶化排序。它是一个常数优化，表示，当 bel_l 是奇数时，若 l 相等，则按 r 升序排序，否则按 r 逆序排序。

这样能带来怎样的好处呢？来看看优化后的移动过程吧：

可以发现，当 l 在偶数块时，r 在往回走的过程中就能够把答案都算出来。这样就比原来没优化的做法快了整整一倍呀！还是很不错的吧。

这就是普通莫队做法的整个过程啦。

如何实现普通莫队？

莫队的核心其实在于 Add 和 Del 两个函数，其他部分基本都是一样的，直接套板子即可。

Add 和 Del 是两个什么函数？它们是用来计算相邻区间答案的函数。Add 函数有一个传参 p，表示这一轮移动把元素 p 纳入了区间中；Del 函数同样有一个传参 p，但含义不一样——相信你已经猜到了，这里是表示这一轮移动把元素 p 移出了区间。其处理方式一般都比较相似。

其他地方，一般就是相同的了：读入所有数组元素信息和查询信息——重点是查询，然后把查询信息排序（还是比较建议加上奇偶化排序这个优化的），最后就是愉快的莫队环节啦。

回到本题

我们只需要想好 Add 和 Del 函数的实现就能用普通莫队解决本题了。

那么，我们怎么实现纳入和移出元素 p 的效果呢？可以考虑维护桶来记录出现次数，并用一个变量 nowAns 实时记录当前状态下的答案。

纳入时就让桶对应位置增加，移出时就让桶对应位置减少即可。当然也要更新 nowAns，只需要考虑 a_p \oplus X 的值的个数即可。

参考代码

我无脑全 long long 了，其实有的是不必开的。

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
const int N = 1e5+5;
struct query{LL l,r,id;}q[N];
LL n,X,sq,a[N],m,L=1,R=0,c[N];
LL nowAns,ans[N];map<LL,LL> Ls;
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
bool cmp(query q1,query q2){
    if(q1.l/sq!=q2.l/sq)return q1.l<q2.l;
    if((q1.l/sq)&1)return q1.r<q2.r;else return q1.r>q2.r;
}
void Add(LL p){
    nowAns-=c[a[p]]*c[a[p]];c[a[p]]++;
    nowAns+=c[a[p]]*c[a[p]];return;
}
void Del(LL p){
    nowAns-=c[a[p]]*c[a[p]];c[a[p]]--;
    nowAns+=c[a[p]]*c[a[p]];return;
}
int main(){
    n=read(),m=read(),X=read();
    sq=sqrt(n);
    for(LL i=1;i<=n;i++)a[i]=read();
    for(LL i=1;i<=m;i++)
        q[i].l=read(),q[i].r=read(),q[i].id=i;
    sort(q+1,q+m+1,cmp);
    for(LL i=1;i<=m;i++){
        while(L>q[i].l)Add(--L);
        while(R<q[i].r)Add(++R);
        while(L<q[i].l)Del(L++);
        while(R>q[i].r)Del(R--);
        ans[q[i].id]=nowAns;
    }for(LL i=1;i<=m;i++)cout<<ans[i]<<"\n";
    return 0;
}

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！

【模板】普通莫队 题解