题解：HH的项链

一、题目分析

本题给定一条由不同编号贝壳组成的项链，需要处理多个询问，每个询问求给定区间内不同贝壳的种类数。

二、解题思路

本题采用莫队算法来解决。莫队算法是一种离线算法，通过对询问区间进行排序，然后按序处理询问，利用双指针在区间上移动来计算答案，从而优化时间复杂度。

（一）数据结构与变量定义

const int N = 50010, M = 200010, S = 1000010;
int n, m, len;
int w[N], ans[M];
struct Query
{
    int id, l, r;
}q[M];
int cnt[S];

• N：定义项链长度的最大值。
• M：定义询问数量的最大值。
• S：定义贝壳编号的最大值。
• n：存储项链的实际长度。
• m：存储询问的数量。
• len：存储分块的长度。
• w[N]：数组，用于存储项链上贝壳的编号。
• ans[M]：数组，用于存储每个询问的答案。
• Query结构体：用于存储每个询问的信息，包括询问的编号id，区间左端点l和右端点r。
• cnt[S]：数组，用于记录每种贝壳编号在当前区间内出现的次数。

（二）辅助函数

1. 获取元素所属块的编号函数get：

int get(int x)
{
    return x / len;
}

根据元素的下标x，返回其所属块的编号。

1. 询问排序比较函数cmp：

bool cmp(const Query& a, const Query& b)
{
    int i = get(a.l), j = get(b.l);
    if (i != j) return i < j;
    return a.r < b.r;
}

用于对询问进行排序。先按区间左端点所属块的编号排序，若块编号相同，则按区间右端点排序。

（三）区间元素添加函数add

void add(int x, int& res)
{
    if (!cnt[x]) res ++ ;
    cnt[x] ++ ;
}

在当前区间添加一个贝壳编号为x的贝壳。如果该贝壳编号首次出现，则不同贝壳种类数res加1，然后更新该贝壳编号的出现次数。

（四）区间元素删除函数del

void del(int x, int& res)
{
    cnt[x] -- ;
    if (!cnt[x]) res -- ;
}

在当前区间删除一个贝壳编号为x的贝壳。减少该贝壳编号的出现次数，如果出现次数变为0，则不同贝壳种类数res减1。

（五）主函数main

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    scanf("%d", &m);
    len = max(1, (int)sqrt((double)n * n / m));

    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 = 0, j = 1, res = 0; k < m; k ++ )
    {
        int id = q[k].id, l = q[k].l, r = q[k].r;
        while (i < r) add(w[ ++ i], res);
        while (i > r) del(w[i -- ], res);
        while (j < l) del(w[j ++ ], res);
        while (j > l) add(w[ -- j], res);
        ans[id] = res;
    }

    for (int i = 0; i < m; i ++ ) printf("%d\n", ans[i]);
    return 0;
}

1. 读取项链长度n，项链上贝壳的编号，询问数量m，并计算分块的长度len。
2. 读取每个询问的区间，将询问信息存储到q数组中。
3. 对询问按照cmp函数定义的规则进行排序。
4. 初始化双指针i、j和答案变量res，按序处理每个询问：
   • 通过移动双指针i和j，调用add和del函数更新区间内不同贝壳的种类数res。
   • 将当前询问的答案存储到ans数组中。
5. 输出每个询问的答案。

四、时间复杂度和空间复杂度

（一）时间复杂度

• 初始化操作：读取项链和询问信息，时间复杂度为(O(n + m))。
• 排序操作：对询问进行排序，时间复杂度为(O(m\log m))。
• 处理询问操作：每个询问最多移动指针(2n)次，总共(m)个询问，时间复杂度为(O(m\sqrt{n}))（因为分块长度len约为(\sqrt{n^2 / m})）。
• 总的时间复杂度为(O(m\sqrt{n} + m\log m + n + m))，近似为(O(m\sqrt{n}))。

（二）空间复杂度

需要存储项链贝壳编号w[N]、询问信息q[M]、答案数组ans[M]以及贝壳编号计数数组cnt[S]，空间复杂度为(O(N + M + S)) 。