莫队算法我早有耳闻。。可惜前不久才去学习。
但是自己看了看论文，也就 1h 左右，就能够全部理解了。
也就是说其实这个算法不难。。
好了，让我们进入正题。

我们首先来看一道例题：

Description

有n个数字，给出k，以及m个查询。
每次查询的格式是L，r，求L~r（左右包含）这个区间内数字的出现次数刚好是k的数字种数。
范围：n<=30000，k<=n，m<=30000，1<=L<r<=n，数列中元素大小<=n。
输入n，k，m，然后n个元素，然后m行查询，对于每一个询问，输出正确的答案。

Example input：

5 2 3
1 2 3 2 2
1 2
2 4
1 5

Example output：

0     //没有
1     //2
0     //没有（2太多了，也不算）

我们来考虑一下这题的解法。
首先肯定可以万能暴力，每次 L~r 枚举。时间复杂度 O（N*M）。
但是这样的暴力是没有前途的！我们来考虑一下新的暴力：
一开始指针区间 0->0，然后对于一个查询，我们将 Left 指针逐步更新成新的 L，Right 同理。
比如一开始 Left=2，Right=3，而 L=1,r=5。
那么我们 Left-1，并且把 Left 位置上的数字出现次数 +1.
Right+1，把 Right 位置上的数字出现次数 +1，直到 Right=5 为止。
框架：

add(x){  //把x位置的数字加入进来
    cnt[x]++;
    if (cnt[x]==k) ans++;
}

remove(x){  //把x位置的数字移出去
    cnt[x]--;
    if (cnt[x]==k-1) ans--;
}

然后以上面题目为例；这种方法需要离线处理，我们同理来看一下解法：

Left=Right=1; add(1);
ans=0;
for u=1 to m{
    while (Left<L[u]){  remove(Left); Left++;}
    while (Left>L[u]){  Left--; add(Left);}
    while (Right<r[u]){  Right++; add(Right};}
    while (Right>r[u]){  remove(Right); Right--;}
    output ans;
}

这里说明一下，其实 remove(Left);Left–;等等可以直接写成 remove(Left–)等等，我这么写是为了理解。
分析一下时间复杂度，我们可以从 Left 和 Right 的移动量来分析：
每一个新的询问，Left 和 Right 的移动量最大都会是 O（N）
所以这样子的方法时间复杂度仍然是 O（N*M），而且可能比上面的暴力更慢。
但是莫队算法的核心，就是从这么一个算法转变过来的。
现在来介绍一下莫队算法解决这道题:
对询问进行分块，我们知道 m 个询问，L 和 r 的范围都在 n 以内，我们根据 L 和 r 的大小来对询问分块。
比如 n=9，有以下的询问：

2 3
1 4
4 5
1 6
7 9
8 9
5 8
6 8

对于 n=9，我们以根号 n 为每个块 block 的大小，这里 block=3.
那么我们把 1~3 分成一组，46，79.
对于每一个询问（L，r），我们以 L 的范围来决定这个询问在哪一个块。
然后每一个独自的块内，我们让询问 r 更小的排在更前面。
那么上面的询问就可以分组成：

(2,3)/(1,4)/(1,6)和
(4,5)/(5,8)/(6,8)和
(7,9)/(8,9)

这一步的排序操作，我们可以在排序的时候加入判断条件 cmp：

bool cmp(Query x,Query y){
if ((x/block)!=(y/block))
    return x.L<y.L;        //不同块的时候
return x.r<y.r;      //同一块的时候
}

排序之后，我们再来分析一下时间复杂度；接下来我们会看到神奇的事情！！
刚才分析此方法的时候，我们是从 L 和 R 的偏移量分析的；我们仍然用这种方法来分析。
考虑一下在同一个块的时候。由于 L 的范围是确定的，所以每次 L 的偏移量是 O（√ N）
但是 r 的范围没有确定；r 的偏移量是 O（N）。
那么从一个块到另一个块呢?
明显地，r 我们不需要作考虑，仍然是 O（N）。
而 L 明显最多也是 2√ N，而且这种情况下，很快就会到下下一块。所以也是 O（√ N）
由于有 √ N（根号 N）个块，所以 r 的总偏移量是 O（N√ N）
而 M 个询问，每个询问都可以让 L 偏移 O（√ N），所以 L 的总偏移量 O（M*√ N）
注意了，时间复杂度分析的时候一定要注意，r 的偏移量和询问数目是没有直接关系的。
而 L 则恰恰相反；L 的偏移量我们刚才也说明了，它和块的个数没有直接关系。
所以总的时间复杂度是：
O（(N+M)*√ N）

很神奇地看到了，我们仅仅改变了一下问题求解的次序，就让时间复杂度大幅度下降！
当然在这个说明过程中我们也看到了，事实上，莫队是一个必须离线的算法。
意味着一些题目如果强制在线，那么莫队就无能为力了。

代码就不总结了，可以看上面的分块的地方，也可以看一些莫队的题目的题解。