HH的项链问题

解题思路

本题的题意就是给我们一个序列，然后有很多询问，每次询问一段区间中不同的数字的个数。

首先考虑暴力如何去做，对于某一段区间，要想知道不同的数字的个数，我们可以用一个数组 $cnt$ 表示每个数出现的次数，首先枚举一下要查询的区间，统计一下每个数出现的次数。然后再扫描一下 $cnt$ 数组，其中非零位置的个数就是区间中不同的数字的个数。

设 $S = 10^6$，那么这个暴力做法的时间复杂度是 $O(nmS)$，时间复杂度非常的高。

这里有一个非常直观的优化，就是我们可以在统计每个数出现次数的同时去统计不同数字的个数，在统计的过程中，如果某个数是第一次出现，就表示出现了一个新的数字，这样就可以在统计的过程中求出不同数字的个数，将时间复杂度降为 $O(nm)$

虽然进行了一次非常大的优化，但是时间复杂度还是很高，依然会超时，因此还需要继续优化。

我们可以先将所有询问排个序，假设我们已经求出了前一个询问区间的 $cnt$ 信息，我们需要通过前一个询问区间的 $cnt$ 信息求出当前询问区间的 $cnt$ 信息。我们可以用一个双指针来求，用两个指针 $i, j$ 分别指向前一个询问区间的左、右端点，我们先用 $j$ 从前一个询问区间的右端点走到当前询问区间的右端点，此时 $j$ 走过的所有数都是应该加入的新数字，因此将每个数统计进 $cnt$ 数组，如果某个数是第一次出现，表示出现了一个新的不同的数字，就令不同数字的个数 $+1$。再用 $i$ 从前一个询问区间的左端点走到当前询问区间的左端点，此时 $i$ 走过的所有数都是应该从数组中移除的数字，如果某个数此时出现的次数清零了，表示移除了一个不同的数字，就令不同数字的个数 $-1$。这样我们每次就能通过前一个询问区间的信息得出当前询问区间的信息。此时这个算法的时间复杂度最坏情况下还是 $O(nm)$。

此时我们的算法是一个比较慢的离线暴力算法，此时要想继续进行优化，就需要考虑用莫队算法来进行优化。

而莫队算法的核心思想就是通过改变查询区间的顺序来将最坏情况下的时间复杂度降低。

首先考虑，如果有一组区间的右端点是递增的，这样当我们从前往后去求每个区间的答案时，区间右端点上的指针 $j$ 就只会向后走，不会往回走，这样 $j$ 走过的总数量就不是 $n^2$ 了，最多只会走 $n$ 次。因此如果我们在某种情况下让某一个端点单调，这样就能让某一个指针的时间复杂度变成 $O(n)$，但是两个指针不一定都能变成 $O(n)$，假设此时我们让右指针 $j$ 单调，那么左指针 $i$ 应该怎么办呢，这里就可以用分块思想来解决。

具体来说，就是将所有查询先按照左端点所在的块的编号从小到大排序，对于左端点所在块的编号相同的则按照右端点的下标从小到大排序。这样我们就能将所有的查询分成 $\sqrt{n}$ 块，每一块的长度都是 $\sqrt{n}$，在每一块内部，所有查询的右端点是递增的。此时我们再来分析一下时间复杂度，首先对于每一块内部，由于右端点是递增的，因此右端点走的总数不会超过 $n$，而一共 $\sqrt{n}$ 块，所以整个的右端点走的次数就是 $n\sqrt{n}$。而对于左端点，首先每个块内部的左端点移动，由于块的长度是 $\sqrt{n}$，因此左端点在块内部最多移动 $\sqrt{n}$ 次，而对于从前一个块移动到后一个块的左端点，最坏情况下就是跨越两个块的长度进行移动，因此最多也只有 $2\sqrt{n}$ 次。一共 $m$ 次询问，因此对于块内，最多移动 $m\sqrt{n}$ 次，对于块与块之间，由于只有 $\sqrt{n}$ 个块，最多跨越 $\sqrt{n}-1$ 次，因此块与块之间最多移动 $2n$ 次。

综上所述，总的时间复杂度应该是 $O(m\sqrt{n})$。是 $5 \times 10^7$ 的级别，有点大，这里可以考虑修改一下块的长度，设块的长度为 $a$，一共 $\frac{n}{a}$ 个块，那么右端点的时间复杂度为 $\frac{n^2}{a}$，左端点的时间复杂度为 $am$，联立等式可以计算出 $a = \sqrt{\frac{n^2}{m}}$ 最优，此时总的时间复杂度为 $O(\sqrt{n^2m})$，大概在 $2.2 \times 10^7$，相比之前低了一点，比较安全。

另外莫队算法有一个玄学优化，就是对于奇数块内部右端点按照从小到大排序，对于偶数块内部右端点按照从大到小排序，奇数块和偶数块可以互换，在某些时候可以快一点。

C++ 代码

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

using namespace std;

const int N = 50010, M = 200010, S = 1000010;

struct Query
{
    int id, l, r; //编号、左端点、右端点
}q[M]; //记录所有查询

int n, m, len; //序列长度、查询次数、块的长度
int a[N], res[M]; //原序列、每个查询的结果
int cnt[S]; //cnt[i] 表示当前 i 出现的次数
int id[N]; //id[i] 表示 i 所在的块的编号

//比较函数：所有查询先按照左端点所在块的编号从小到大排序，再按照右端点下标从小到大排序
bool cmp(const Query &a, const Query &b)
{
    if(id[a.l] != id[b.l]) return id[a.l] < id[b.l];
    if(id[a.l] & 1) return a.r < b.r; //奇数块按照右端点从小到大排序（玄学优化）
    return a.r > b.r; //偶数块按照右端点从大到小排序
}

void add(int x, int &res) //加入 x 并更新 res
{
    cnt[x]++;
    if(cnt[x] == 1) res++;
}

void del(int x, int &res) //删除 x 并更新 res
{
    cnt[x]--;
    if(!cnt[x]) res--;
}

int main()
{
    scanf("%d", &n);

    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    scanf("%d", &m);

    len = max(1, (int)sqrt((double)n * n / m)); //计算块的长度，最小为 1
    for(int i = 1; i <= n; i++) id[i] = (i - 1) / len; //预处理每个下标所在的块的编号

    for(int i = 0; i < m; i++)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        q[i] = {i, l, r};
    }

    //将所有查询先按照左端点所在块的编号从小到大排序，再按照右端点下标从小到大排序
    sort(q, q + m, cmp);

    //莫队算法
    for(int k = 0, i = 1, j = 0, ans = 0; k < m; k++) //[i, j] 对应当前的 cnt
    {
        int num = q[k].id, l = q[k].l, r = q[k].r;
        while(j < r) add(a[++j], ans); //j < r，则右指针右移至右端点并加入节点
        while(j > r) del(a[j--], ans); //j > r，则右指针左移至右端点并删除节点
        while(i < l) del(a[i++], ans); //i < l，则左指针右移至左端点并删除节点
        while(i > l) add(a[--i], ans); //i > l，则左指针左移至左端点并加入节点
        res[num] = ans; //记录当前查询的答案
    }

    //输出每个查询答案
    for(int i = 0; i < m; i++) printf("%d\n", res[i]);

    return 0;
}