博客食用更佳~ https://www.cnblogs.com/czyty114/p/14432462.html

$\;$
莫队是一类离线区间询问问题，经常应用于需要维护的信息无法合并时（如线段树等）
其核心思想是：维护两个指针$l,r$。在已知$[l,r]$这段区间的信息的前提下，两个指针分别移动到$l’,r’$的过程中，实时地维护答案。从而算出区间$[l,r]的信息$
$\;$

引入

$\;$
因为题目没有强制在线，所以莫队算法是将所有的询问按一定顺序排好序，并且一次询问是以上一次询问为基础。
我们可以把一次询问$l,r$看作二维平面上的一个点$(l,r)$，那我们在两次询问间$l,r$指针一共移动的距离，实质上是$(l_1,r_1)$,$(l_2,r_2)$间的曼哈顿距离
但求最小哈密尔顿路径又是无法做到的。所以我们需要找到一个合适的顺序，使得两指针移动的距离尽可能的小。
$\;$

核心

$\;$
假设现在给定你一个长为$n$的序列，$m$次询问，每次询问求$[l,r]$这段区间不同数的数量。
$n,m\leq 10^5$
对于这个问题来说，用线段树是很难去维护的。因为区间不同数的数量并不能很轻松地由左右子区间转移而来。
考虑将整个序列分块，每段长度为$\sqrt n$
这样每段询问区间的左右端点必定位于某个块中。
我们把区间左端点所属的块的编号作为第一关键字，右端点的位置作为第二关键字，将询问区间排序。
按照莫队的思想，我们按此顺序依次处理每一个区间，在两个指针的移动的过程中维护一个数组cnt，表示每一个数出现的次数。
若发现某个数cnt为由1减为0了，将答案减1，反之则加1
$\;$

时间复杂度

$\;$
我们发现算法中时间的瓶颈就在于，左右指针总共会移动多少次。我们分开来看：
(注意：这里我们假设m与n同阶)

左端点

$\;$
因为第一关键字是按左端点所在块排序的，所以左端点所在块是单调不降的。
对于目前左端点与上一个左端点同属一个块的情况：最多出现$n$次，但每一次两个点之间移动的距离不超过$\sqrt n$
因此：$O(n\sqrt n)$
对于目前左端点与上一个左端点不同属一个块的情况：最多出现$\sqrt n$次，但每一次两个点之间移动的距离不超过$n$
因此：$O(n\sqrt n)$
$\;$

右端点

$\;$
其位置作为第二关键字。因此若左端点有若干个位于同一个块中，此时右端点应该是单调不降的。
因此对于同一个块的左端点，右端点至多移动$n$次，而总共有$\sqrt n$个块
因此：$O(n\sqrt n)$
否则，若左端点不在同一个块中，右端点的位置就无法确定了。这样一次右端点至多移动$n$次
但这种情况至多出现$\sqrt n$次
因此：$O(n\sqrt n)$
$\;$
综上所述，莫队算法的时间复杂度为$O(n\sqrt n)$

Code

#include <bits/stdc++.h>

const int N = 50010, M = 200010;
int n, m, a[N], b[N], ans[M], id[N], sq, nn, cnt[N];
struct node {
    int pos, l, r;
}ask[M];
bool cmp(node a, node b) {
    if(id[a.l] != id[b.l]) return id[a.l] < id[b.l]; // 左端点所属块 
    return a.r < b.r; // 右端点所属位置 
}
int main() {
    scanf("%d", &n);
    sq = (int)sqrt(n);
    for(int i=1;i<=n;i++) id[i] = (int)ceil(i / sq); // 预处理每个点所属块的编号 
    for(int i=1;i<=n;i++) scanf("%d", &a[i]), b[i] = a[i];
    std::sort(b + 1, b + n + 1);
    nn = std::unique(b + 1, b + n + 1) - b - 1;
    for(int i=1;i<=n;i++) a[i] = std::lower_bound(b + 1, b + nn + 1, a[i]) - b;
    //----------------- 上面是离散化部分，不多赘述 
    scanf("%d", &m);
    for(int i=1;i<=m;i++) scanf("%d%d", &ask[i].l, &ask[i].r), ask[i].pos = i;
    std::sort(ask + 1, ask + m + 1, cmp);
    int x = 0, y = 0, res = 0; //x,y维护的是一直在移动两个指针 
    for(int i=1;i<=m;i++) {
        int l = ask[i].l, r = ask[i].r; // l,r是当前询问的两个左右端点 
        while(x < l) { // 左端点向右移，区间缩小 
            cnt[a[x]] --; if(!cnt[a[x]]) -- res;
            x ++;
        }

        while(x > l) { // 左端点向左移，区间变大 
            cnt[a[x - 1]] ++; if(cnt[a[x - 1]] == 1) ++ res;
            x --;
        }

        while(y < r) { // 右端点向右移，区间变大 
            cnt[a[y + 1]] ++; if(cnt[a[y + 1]] == 1) ++ res;
            y ++;
        }

        while(y > r) { // 右端点向左移，区间缩小 
            cnt[a[y]] --; if(!cnt[a[y]]) -- res;
            y --;
        }

        ans[ask[i].pos] = res; // 注意：i是排序后区间的编号，但并不是输入时询问的编号 
    }
    for(int i=1;i<=m;i++) printf("%d\n", ans[i]);
    return 0;
}