题解：数颜色

一、题目分析

本题给定一套(N)支彩色画笔的初始排列，需要处理(M)个操作，操作分为两种：一是查询指定区间内不同颜色画笔的数量；二是替换某一支画笔的颜色。

二、解题思路

本题采用带修莫队算法来解决。带修莫队算法是莫队算法的扩展，在处理区间查询的基础上，还能处理修改操作，通过对询问和修改操作进行合理排序，利用双指针和时间戳来维护区间信息，从而高效地计算答案。

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

const int N = 10010, S = 1000010;
int n, m, mq, mc, len;
int w[N], cnt[S], ans[N];
struct Query
{
    int id, l, r, t;
}q[N];
struct Modify
{
    int p, c;
}c[N];

• N：定义画笔数量的最大值。
• S：定义颜色编号的最大值。
• n：存储初始画笔的实际数量。
• m：存储操作的总数量。
• mq：存储查询操作的数量。
• mc：存储修改操作的数量。
• len：存储分块的长度。
• w[N]：数组，用于存储每支画笔的颜色。
• cnt[S]：数组，用于记录每种颜色在当前区间内出现的次数。
• ans[N]：数组，用于存储每个查询操作的答案。
• Query结构体：用于存储每个查询操作的信息，包括查询的编号id，区间左端点l，右端点r，以及该查询操作对应的时间戳（即执行该查询时已经进行的修改操作数量）t`。
• Modify结构体：用于存储每个修改操作的信息，包括要修改的画笔位置p和修改后的颜色c。

（二）辅助函数

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

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

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

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

bool cmp(const Query& a, const Query& b)
{
    int al = get(a.l), ar = get(a.r);
    int bl = get(b.l), br = get(b.r);
    if (al != bl) return al < bl;
    if (ar != br) return ar < br;
    return a.t < b.t;
}

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

（三）区间元素添加函数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%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    for (int i = 0; i < m; i ++ )
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (*op == 'Q') mq ++, q[mq] = {mq, a, b, mc};
        else c[ ++ mc] = {a, b};
    }

    len = cbrt((double)n * max(1 , mc)) + 1;
    sort(q + 1, q + mq + 1, cmp);

    for (int i = 0, j = 1, t = 0, k = 1, res = 0; k <= mq; k ++ )
    {
        int id = q[k].id, l = q[k].l, r = q[k].r, tm = q[k].t;
        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);
        while (t < tm)
        {
            t ++ ;
            if (c[t].p >= j && c[t].p <= i)
            {
                del(w[c[t].p], res);
                add(c[t].c, res);
            }
            swap(w[c[t].p], c[t].c);
        }
        while (t > tm)
        {
            if (c[t].p >= j && c[t].p <= i)
            {
                del(w[c[t].p], res);
                add(c[t].c, res);
            }
            swap(w[c[t].p], c[t].c);
            t -- ;
        }
        ans[id] = res;
    }

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

1. 读取画笔数量n和操作数量m，以及初始画笔的颜色。
2. 遍历每个操作，将查询操作和修改操作分别存储到q数组和c数组中，并记录查询操作的时间戳。
3. 计算分块的长度len（这里使用立方根来平衡时间复杂度），对查询操作按照cmp函数定义的规则进行排序。
4. 初始化双指针i、j，时间戳变量t，查询操作索引k和答案变量res，按序处理每个查询操作：
   • 通过移动双指针i和j，调用add和del函数更新区间内不同颜色的种类数res。
   • 根据当前查询操作的时间戳tm，向前或向后调整时间戳t，处理相应的修改操作：如果修改的画笔位置在当前区间内，需要更新区间内不同颜色的种类数res，并实际交换画笔颜色。
   • 将当前查询的答案存储到ans数组中。
5. 输出每个查询操作的答案。

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

（一）时间复杂度

• 初始化操作：读取画笔信息和操作信息，时间复杂度为(O(n + m))。
• 排序操作：对查询操作进行排序，时间复杂度为(O(mq\log mq))。
• 处理查询操作：每个查询最多移动指针(2n)次，处理修改操作的时间复杂度与指针移动和修改操作数量有关，总的时间复杂度为(O(mq \times n^{\frac{2}{3}}))（其中mq是查询操作数量，通过分块长度len的计算方式和算法特性得出）。
• 总的时间复杂度为(O(mq \times n^{\frac{2}{3}} + mq\log mq + n + m))，近似为(O(mq \times n^{\frac{2}{3}}))。

（二）空间复杂度

需要存储画笔颜色w[N]、查询操作q[N]、修改操作c[N]、颜色计数数组cnt[S]以及答案数组ans[N]，空间复杂度为(O(N + N + N + S + N)=O(N + S)) 。