普通莫队

简介

莫队是一种基于分块思想的离线算法，用于解决区间问题，适用范围如下：

1. 只有询问没有修改。
2. 允许离线。
3. 在已知询问\([l,r]\)答案的情况下可以\(O(1)\)得到\([l,r?1],[l,r+1],[l?1,r],[l+1,r]\)的答案。

满足以上三个条件就可以在\(O(n\sqrt{m}+mlogm)\)的时间复杂度下得到每个询问的解。

算法思想

莫队的精髓就在于通过对询问进行排序，并把询问的结果作为下一个询问求解的基础，使得暴力求解的复杂度得到保证。

上文中“适用范围”的第三点“在已知询问$ [l,r]$答案的情况下可以 \(O(1)\)得到\([l,r]\)的答案”即是“把询问的结果作为下一个询问求解的基础”的方法。

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

在这题中，用\(cnt_{i}\)表示当前处理的区间内颜色为\(i\)的袜子出现的次数，用\(\mathrm{len}\)表示当前处理的区间的长度，用\(x\)表示新增的那只袜子的颜色。

以已知区间\([l,r]\)的答案求解区间\([l,r+1]\)为例。分别处理分子和分母：

• 分母为任选两只袜子的组合总数，原先是\(\frac{\mathrm{len}(\mathrm{len}-1)}{2}\)，现在是\(\frac{\mathrm{len}(\mathrm{len}+1)}{2}\)，增加了\(\mathrm{len}\)

• 分子为两只袜子颜色相同的组合总数，比原来增加了\(cnt_{x}\)，即新增的这只袜子和原本就在当前区间内的相同颜色的袜子的组合。

因此，将一只颜色为\(x\)的袜子计入答案的函数就可以写出来了：

//fz表示分子，fm表示分母
inline void add(int x) {
    fz += cnt[x];
    cnt[x]++;
    fm += len;
    len++;
}

同理可以写出将一只颜色为\(x\)的袜子移出答案的函数：

inline void del(int x) {
    cnt[x]--;
    fz -= cnt[x];
    len++;
    fm -= len;
}

于是，我们就可以得到一个暴力的算法：用\(l\)和\(r\)分别记录当前区间的两个端点，然后用下面这段代码来更新答案（\(q[i].l,q[i].r\)代表正在处理的询问的两个端点，\(col[p]\)代表第\(p\)只袜子的颜色）：

while (l > q[i].l) add(col[--l]);
while (r < q[i].r) add(col[++r]);
while (l < q[i].l) del(col[l++]);
while (r > q[i].r) del(col[r--]);

然而，这个算法的时间复杂度是\(O(nm)\)的（因为最坏情况下每次\(l\)和\(r\)两个指针都要走\(O(n)\)的距离，而一共有\(m\)次询问），和暴力完全一样甚至跑的更慢。

别忘了，之前我说过，莫队的精髓就在于通过对询问进行排序，使得暴力求解的复杂度得到保证。

我们的目的是使\(l\)和\(r\)两个指针走过的总距离尽量的小，这时候就要用到分块的思想了。

把整个区间\([1,n]\)分成若干块，以询问的左端点所在块为第一关键字，以询问的右端点大小为第二关键字，对询问进行排序，那么：

• 对于同一块的询问，\(l\)指针每次最多移动块的大小，\(r\)指针的移动则是单调的，总共移动最多\(n\)。
• 对于不同块的询问，\(l\)每次换块时最多移动两倍块的大小，\(r\)每次换块时最多移动\(n\)。

总结：（用\(B\)表示块的大小）\(l\)指针每次移动\(O(B)\)，\(r\)指针每块移动\(O(n)\)。

所以：

• \(l\)的移动次数最多为询问数\(\times\)块的大小，即\(O(mB)\)。

• \(r\)的移动次数最多为块的个数×总区间大小，即\(O(n^2\div B)\)。

因此，总移动次数为\(O(mB+n^2/B)\)。

没错，这就是个双勾函数，所以当\(B=\sqrt{\frac{n^2}{m}}\)即\(\frac{n}{\sqrt{m}}\)时复杂度最小，为\(O(n\sqrt{m})\)。

剩下的最后一个问题：初始的当前区间是什么？

只要任意指定一个空区间就好了，如\(l=1,r=0\)。

所以，整个莫队算法就可以概括为：

1. 将询问记录下来。
2. 以\(\frac{n}{\sqrt{m}}\)
3. 为块的大小，以询问的左端点所在块为第一关键字，以询问的右端点大小为第二关键字，对询问进行排序。
4. 暴力处理每个询问。
5. 输出答案。

总的复杂度为\(O(n\sqrt{m}+mlogm)\)。

P.S. 网上很多教程说分块大小取\(\sqrt{n}\)最优，复杂度为\(O(n\sqrt{n})\)，这是不严谨的，当\(n,m\)差别较大时使用\(\sqrt{n}\)作为分块大小效率会明显偏低。

例题代码

[国家集训队]小Z的袜子AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;

const int MAXN=50005;
int n,m,B,fz,fm,len,col[MAXN],cnt[MAXN],ans[MAXN][2];
struct query {
    int l,r,id;
    bool operator < (query & b) {
        return l / B == b.l / B ? r < b.r : l < b.l;
    }
} q[MAXN];
inline void add(int x) {
    fz += cnt[x];
    cnt[x]++;
    fm += len;
    len++;
}
inline void del(int x) {
    cnt[x]--;
    fz -= cnt[x];
    len--;
    fm -= len;
}
inline int gcd(int a,int b) {
    return b == 0 ? a : gcd(b,a % b);
}
int main() {
    int g,l=1,r=0;
    scanf("%d%d",&n,&m);
    B=n/sqrt(m);
    for (int i=1; i<=n; i++)
        scanf("%d",&col[i]);
    for (int i=0; i<m; i++) {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    sort(q,q+m);
    for (int i=0; i<m; i++) {
        if (q[i].l == q[i].r) {
            ans[q[i].id][0]=0;
            ans[q[i].id][1]=1;
            continue;
        }
        while (l>q[i].l) add(col[--l]);
        while (r<q[i].r) add(col[++r]);
        while (l<q[i].l) del(col[l++]);
        while (r>q[i].r) del(col[r--]);
        g=gcd(fz,fm);
        ans[q[i].id][0]=fz / g;
        ans[q[i].id][1]=fm / g;
    }
    for (int i=0; i<m; i++)
        printf("%d/%d\n",ans[i][0],ans[i][1]);
    return 0;
}

其它例题

小B的询问

带修莫队

前面说过，普通的莫队只能解决没有修改的问题，那么带修改的问题怎么解决呢？带修莫队就是一种支持单点修改的莫队算法。

算法简介

还是对询问进行排序，每个询问除了左端点和右端点还要记录这次询问是在第几次修改之后（时间），以左端点所在块为第一关键字，以右端点所在块为第二关键字，以时间为第三关键字进行排序。

暴力查询时，如果当前修改数比询问的修改数少就把没修改的进行修改，反之回退。

（编辑：ASP站长网）