莫队-普通莫队（学习笔记）

XichenOC · 2025-01-18 14:56:05 · 算法·理论

莫队

引言：

莫队是一种运用了分块思想的一种用来解决区间问题的算法，由于他是由国家集训队队长莫涛提出的算法，因此取名莫队。注意普通莫队的基本时间复杂度为 O(n\sqrt n)，并且他是一种离线算法，所以强制在线的算法不能使用

思想：

若我们想要知道某一区间内有多少种不同的值和每一种的个数。可以很容易想到维护一个 cnt[i]数组来表达第 i 种的个数，然后遍历区间来增加。

那我们可以简单做一个转换，维护两个指针，我们要使指针向我们的目标区间靠近，若经过的点在区间内，就加上，若该点没有意义那就减去，及：

其中 ll,rr指目标区间 l,r 指当前指针遍历到的区间。而我们只需要根据题目来维护加减的内容。

这样就将对区间的求解转换为对指针的转移。对于多个区间的求解，只需要找到一个最好的顺序使指针的移动次数最少。而莫队就是这样的一种顺序；

莫队过程：

莫队运用分块的思想，将整个区间分成 \sqrt n 个块，再将查询区间的左端点根据块来编号，最后进行排序。

• 若两个区间的左端点不在一个块里，就根据块从小到大排
• 否则如果当前块为奇数就根据右端点升序排
• 否则根据右端点降序排
  （的确很玄学，我也不知道为什么） 这样在离线求出答案即可

时间复杂度：O(n\sqrt n)
证明过程看这篇

例题

P1494 [国家集训队] 小 Z 的袜子

分析发现一个区间的取到相同的方案数：

总方案数为：

用莫队维护每一种的个数 cnt[i] 即可

模板代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=50010;
int a[N],cnt[N];
bool vis[N];
struct query{
    int l,r,id,k;
}q[N];
struct answer{
    int x,y;
}ans[N];
bool cmp(query x,query y){
    if(x.k!=y.k){
        return x.k<y.k;
    }
    else if(x.k&1){
        return x.r<y.r;
    }
    else{
        return x.r>y.r; 
    }
}
int sum;
void add(int i){
    sum+=cnt[i];
    cnt[i]++;
} 
void del(int i){
    cnt[i]--;
    sum-=cnt[i];
}
signed main(){
//  freopen("P1494_1.in","r",stdin);
//  freopen("P1494.out","w",stdout);
    int n,m,num=0;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(!vis[a[i]]){
            num++;
            vis[a[i]]=1;
        }
    }
    int len=sqrt(n);
    for(int i=1;i<=m;i++){
        int l,r;
        scanf("%lld%lld",&l,&r);
        q[i]={l,r,i,l/len};
    }

    sort(q+1,q+m+1,cmp);
    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)add(a[--l]);
        while(r<rr)add(a[++r]);
        while(l<ll)del(a[l++]);
        while(r>rr)del(a[r--]);
        ans[q[i].id]={sum,(r-l+1)*(r-l)/2};
    }
    for(int i=1;i<=m;i++){
        if(ans[i].y==0 || ans[i].x==0)ans[i].y=1;
        int gcd=__gcd(ans[i].x,ans[i].y);
        printf("%lld/%lld\n",ans[i].x/gcd,ans[i].y/gcd);
    }
} 

例题：

1.P2709 小B的询问 题解
2.P3709 大爷的字符串题 题解
3.P4462 [CQOI2018] 异或序列 题解