先看一道例题

BZOJ2038: [2009国家集训队]小Z的袜子(hose)

题目大意

给你一个数列，每次询问一个区间 $[l, r]$ ，在这个区间中随机取出两个数，这两个数相等的概率。
$N, M \leq 50000$

暴力？

首先我们想一想答案是多少。
很显然，对于一个区间，我们可以处理出每个数字出现的次数。
记 $i$ 出现的次数为 $n u m_{i}$ 。
那么，对于一个数字 $i$ ，选中两个 $i$ 的方案数为 $C_{n u m_{i}}^{2}$ 。
而总共的方案数有 $C_{r - l + 1}^{2}$ 。
所以，对于区间 $[l, r]$ ，答案为

\frac{\sum C_{n u m_{i}}^{2}}{C_{r - l + 1}^{2}}

所以，可以考虑每一次直接暴力计算，那么时间复杂度总共是

O (N M)

显然爆炸。

莫队算法

莫队算法用来干嘛？

莫队算法主要用来处理一堆的区间问题……

思想

对于一个状态 $[l, r]$ ，可以通过 $O (1)$ 的时间转移到 $[l - 1, r]$ 、 $[l, r + 1]$ 、 $[l + 1, r]$ 、 $[l, r - 1]$ 。
那么从一个询问 $[l, r]$ ，如果要转移到 $[l^{'}, r^{'}]$ ，花的时间复杂度就是 $| l - l^{'} | + | r - r^{'} |$ 。
但是，如果按照题目给定的顺序来做，那么，将会分分钟被卡爆。
So?What should we do?
有一个非常容易想到的做法叫最小生成树。不过，曼哈顿最小生成树用普通方法来跑是贼慢的。有一种 $O (N \lg N)$ 求曼哈顿最小生成树的方法，但是，我不会……
还有一个分块的做法。
设一个块的大小为 $k$ ，将所有的询问分块处理。
将询问排个序，以左端点所在的块为第一关键字，以右端点为第二关键字。
分析一下时间复杂度。
当一个询问转移到下一个询问时：
对于左端点，在同一个块中，那么最多跳 $k$ 次。否则，考虑计算所有跨块的情况，总共顶多只是 $N$ 次。所以，对于左端点，花的总时间是 $O (N k)$
对于右端点，在每一个块中，总共顶多跳 $n$ 次。如果是跨块的情况，每次顶多 $n$ 次。一共有 $\frac{N}{k}$ 个块，那么，对于右端点，时间复杂度为 $O (\frac{N^{2}}{k})$ 。
综上所述，总时间复杂度为 $O (N k + \frac{N^{2}}{k})$
利用平衡规划的思想，可知当 $k = \sqrt{N}$ 的时候，时间复杂度是最优的，为 $O (N \sqrt{N})$ 。

回到例题

显然，可以用莫队算法做。
每一次区间变动，就可以用 $O (1)$ 方法更改状态和答案。
所以一个裸莫队就行了。
据说，用曼哈顿最小生成树来做，最后的时间复杂度也是 $O (N \sqrt{N})$ 。而且曼哈顿最小生成树还难打。这个分块的方式，还是相当好打的，排完序之后就简单粗暴地干就行了。

代码

using namespace std;
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 50000
#define MAXM 50000
long long gcd(long long a,long long b){
    long long k;
    while (b){
        k=a%b;
        a=b;
        b=k;
    }
    return a;
}
int n,m;
int col[MAXN+1];
int unit;//块的大小
int be[MAXN+1];//表示每个点所在的块
struct Operation{
    int time,l,r;
} o[MAXM+1];
bool cmp(const Operation &x,const Operation &y){
    return be[x.l]<be[y.l] || be[x.l]==be[y.l] && x.r<y.r;
}
struct Answer{
    long long fz,fm;//分子，分母
    void yf(){//约分
        int g=gcd(fz,fm);
        fz/=g;
        fm/=g;
    }
} ans[MAXM+1];
int num[MAXN+1];
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i)
        scanf("%d",&col[i]);
    unit=sqrt(n);
    for (int i=1;i<=n;++i)
        be[i]=(i-1)/unit+1;
    for (int i=1;i<=m;++i)
        o[i].time=i,scanf("%d%d",&o[i].l,&o[i].r);
    sort(o+1,o+m+1,cmp);
    int nowl=1,nowr=0;
    long long nowfz=0;
    for (int i=1;i<=m;++i){
        while (nowl>o[i].l){
            nowl--;
            nowfz+=/*(num[col[nowl]]+1)*num[col[nowl]]-num[col[nowl]]*(num[col[nowl]]-1)>>1*/num[col[nowl]];
            num[col[nowl]]++;
        }
        while (nowr<o[i].r){
            nowr++;
            nowfz+=num[col[nowr]];
            num[col[nowr]]++;
        }
        while (nowl<o[i].l){
            nowfz-=/*num[col[nowl]]*(num[col[nowl]]-1)-(num[col[nowl]]-1)*(num[col[nowl]]-2)>>1*/num[col[nowl]]-1;
            num[col[nowl]]--;
            nowl++;
        }
        while (nowr>o[i].r){
            nowfz-=num[col[nowr]]-1;
            num[col[nowr]]--;
            nowr--;
        }
        ans[o[i].time]={nowfz,(long long)(o[i].r-o[i].l+1)*(o[i].r-o[i].l)>>1};
        ans[o[i].time].yf();
    }
    for (int i=1;i<=m;++i)
        printf("%lld/%lld
",ans[i].fz,ans[i].fm);
    return 0;
}

总结

莫队算法是个神奇的算法。
事实上，分块算法都很神奇。
如果一些题目做不出来，那就分块试一试吧！