介绍

莫队算法可以一个可高效解决绝大多数离线+无修改+区间查询问题的算法。这类问题具体是指：如果知道$[L,R]$的答案时，可以在$O(g(n))$的时间下得到$[L,R−1]$,$[L,R+1]$,$[L−1,R]$,$[L+1,R]$的答案的话，就可以$O(n\sqrt n · \mathrm{g}(n))$的时间内求出所有查询。

对于莫队算法我感觉就是暴力。由于预先知道所有的询问，因此可以合理的组织计算每个询问的顺序以此来降低复杂度。

假设我们算完$[L,R]$的答案后现在要算$[L′,R′]$的答案。由于可以在$O(1)$的时间下得到$[L,R−1]$,$[L,R+1]$,$[L−1,R]$,$[L+1,R]$的答案，所以计算$[L′,R′]$的答案耗时$|L−L′|+|R−R′|$。如果把询问$[L,R]$看做平面上的点$a(L,R)$，询问$[L′,R′]$看做点$b(L′,R′)$的话，那么时间开销就为两点的曼哈顿距离。

因此，如果将每个询问看做平面上的一个点，按一定顺序计算每个值，那开销就为曼哈顿距离的和。要计算到每个点，路径至少会形成一棵树。所以问题就变成了求二维平面的最小曼哈顿距离生成树。

这样只要顺着树边计算一次就OK了，可以证明时间复杂度为$O(n\sqrt{n})$（这个我不会证明），但是这种方法的编程复杂度稍微高了一点。

有一个比较优雅的替代品：先对序列分块，然后对于所有询问按照L所在块的大小排序，如果一样再按照R排序，最后再计算。为什么这样计算就可以降低复杂度呢?

一、i与i+1在同一块内，r单调递增，所以r是$O(n)$的。由于有$\sqrt{n}$块,所以这一部分时间复杂度是$O(n\sqrt{n})$；
二、i与i+1跨越一块，r最多变化n，由于有$\sqrt{n}$块，所以这一部分时间复杂度是$O(n\sqrt{n})$；
三、i与i+1在同一块内时，变化不超过$\sqrt{n}$，跨越一块也不会超过$\sqrt{n}$，不妨看作是$\sqrt{n}$。由于有n个数，所以时间复杂度是$O(n\sqrt{n})$；
于是就变成了$O(n\sqrt{n})$了。

例题（bzoj2038)

题意：

有n只袜子，每只袜子有不同的颜色，给出区间$[L,R]$，问在这个区间中有多大的概率抽到两只颜色相同的袜子。

思路：

假设区间$[L,R]$中有三种颜色，每种颜色的袜子只数分别为a,b,c。

则抽到两只颜色相同的袜子的概率为$\frac{a}{a+b+c}*\frac{a-1}{a+b+c-1}+\frac{b}{a+b+c}*\frac{b-1}{a+b+c-1}+\frac{c}{a+b+c}*\frac{c}{a+b+c-1}$，化简结果为$\frac{a^2+b^2+c^2-(a+b+c)}{(a+b+c)*(a+b+c-1)}=\frac{a^2+b^2+c^2-(R-L+1)}{(R-L+1)*(R-L)}$。

所以只要求每个区间内每种袜子的数目的平方和就可以了。

这时可以用莫队算法了。

代码：

typedef long long ll;
struct qnode
{
    int l,r,id;
}q[50010];
ll tot;
struct anode
{
    ll fz,fm;
}ans[50010];
int col[50010];
int pos[50010];//在哪一块里（用来对询问排序）
ll num[50010];//当前每种颜色的数目
bool cmp(qnode x,qnode y)
{
    if(pos[x.l]!=pos[y.l])return pos[x.l]<pos[y.l];
    return x.r<y.r;
}
void update(int id,int d)
{
    tot-=num[col[id]]*num[col[id]];
    num[col[id]]+=d;
    tot+=num[col[id]]*num[col[id]];
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int block=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&col[i]);
        pos[i]=(i-1)/block;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+1+m,cmp);
    memset(num,0,sizeof(num));
    int L=1,R=0;
    tot=0;
    for(int i=1;i<=m;i++)
    {
        int id=q[i].id;
        if(q[i].l==q[i].r)
        {
            ans[id].fz=0;
            ans[id].fm=1;
            continue;
        }
        if(q[i].l<L)
        {
            for(int j=L-1;j>=q[i].l;j--)
                update(j,1);   //区间增加
        }
        else
        {
            for(int j=L;j<=q[i].l-1;j++)
                update(j,-1);   //区间减少
        }
        L=q[i].l;
        if(q[i].r>R)
        {
            for(int j=R+1;j<=q[i].r;j++)
                update(j,1);
        }
        else
        {
            for(int j=R;j>=q[i].r+1;j--)
                update(j,-1);
        }
        R=q[i].r;
        ans[id].fz=tot-(q[i].r-q[i].l+1);
        ans[id].fm=(ll)(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
        ll temp=__gcd(ans[id].fz,ans[id].fm);
        ans[id].fz/=temp;ans[id].fm/=temp;
    }
    for(int i=1;i<=m;i++)
        printf("%lld/%lld\n",ans[i].fz,ans[i].fm);
    return 0;
}

总结

一般来说只要update函数根据题意作出修改就行了，其他都差不多。

小优化

如果l所在块的编号为奇数则按r升序排序，偶数则按r降序排序。

bool cmp(qnode x,qnode y)
{
    if(pos[x.l]!=pos[y.l])
        return pos[x.l]<pos[y.l];
    if(pos[x.l]&1==1)return x.r<y.r;
    return x.r>y.r;
}

update

惊了 while循环比for跑得快！考虑到莫队算法是一个很暴力的算法，还是尽可能要优化代码，所以改进一哈。

typedef long long ll;
struct qnode
{
    int l,r,id;
}q[50010];
ll tot;
struct anode
{
    ll fz,fm;
}ans[50010];
int col[50010];
int pos[50010];//在哪一块里（用来对询问排序）
ll num[50010];//当前每种颜色的数目
bool cmp(qnode x,qnode y)
{
    if(pos[x.l]!=pos[y.l])return pos[x.l]<pos[y.l];
    return x.r<y.r;
}
void update(int id,int d)
{
    tot-=num[col[id]]*num[col[id]];
    num[col[id]]+=d;
    tot+=num[col[id]]*num[col[id]];
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int block=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&col[i]);
        pos[i]=(i-1)/block;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id=i;
    }
    sort(q+1,q+1+m,cmp);
    memset(num,0,sizeof(num));
    int L=1,R=0;
    tot=0;
    for(int i=1;i<=m;i++)
    {
        int id=q[i].id;
        if(q[i].l==q[i].r)
        {
            ans[id].fz=0;
            ans[id].fm=1;
            continue;
        }
        while(L>q[i].l)
        {
            L--;
            update(L,1);
        }
        while(L<q[i].l)
        {
            update(L,-1);
            L++;
        }
        while(R<q[i].r)
        {
            R++;
            update(R,1);
        }
        while(R>q[i].r)
        {
            update(R,-1);
            R--;
        }
        ans[id].fz=tot-(q[i].r-q[i].l+1);
        ans[id].fm=(ll)(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
        ll temp=__gcd(ans[id].fz,ans[id].fm);
        ans[id].fz/=temp;ans[id].fm/=temp;
    }
    for(int i=1;i<=m;i++)
        printf("%lld/%lld\n",ans[i].fz,ans[i].fm);
    return 0;
}