数颜色问题

解题思路

本题需要实现两个操作，一个是询问某一段区间中不同数的个数，一个是修改某个位置上的数。

对于询问某一段区间中不同数的个数，可以用一个基础莫队实现，将所有查询按照某种顺序排列，每次用上一个查询的信息计算当前查询的信息，就能得出全部查询的结果。

如果加上修改操作，其实就相当于在加上一维，原本序列是一维的，我们加上一个时间戳，假设有 $t$ 个修改操作，则时间戳就从 $0 \sim t$，对于 $0$ 表示没有修改过的数组，对于 $1$ 表示进行完第一个修改操作之后的数组，对于 $2$ 表示进行完第二个修改操作之后的数组，以此类推。

然后对于每个查询 $[l ,r]$，假设当前查询在第 $k$ 个修改操作之后，第 $k+1$ 个修改操作之前，那么就给当前查询一个时间戳 $k$，即 $[l, r, k]$，表示当前查询要在进行完第 $k$ 个修改操作之后的数组中查询。

这样对于每个查询 $[l, r, k]$，我们都要从上一个查询 $[i, j, t]$ 的信息计算出来，先将 $i$ 移动到 $l$，将 $j$ 移动到 $r$，再将 $t$ 移动到 $k$，就能得到当前查询的信息，维护的信息还是一个 $cnt$ 数组表示每个数出现的次数，一个 $res$ 表示不同数的个数。将 $i, j$ 移动到 $l, r$ 比较容易实现，就是将移动过程中遇到的数加入或删除，同时还要更新 $res$。$i, j$ 每移动一次，都只需要 $O(1)$ 的时间去维护对应的信息。那么如何修改 $t$ 呢，如果此时 $t + 1$，说明多了一个修改操作，而一个修改操作只会修改一个位置上的数，如果这个数在我们的查询区间外，则不会对查询区间中的信息产生影响，所以不需要做任何修改。如果这个数在我们的查询区间内，说明查询区间中会删掉某一个数，然后再加入一个新的数，只需要对应维护信息即可，而这两个操作也是 $O(1)$ 的时间。当 $t-1$ 时同理。

这里在移动 $t$ 时有一个小细节，就是 $t$ 向后移动之后，此时如果往回移动，那么此时我们需要将原本修改掉的数再修改回来，一种方法是对于每个位置上的数，记录一下他修改之前的数是多少。而这里也有一个比较取巧的方式，本身我们用一个数组记录了每一个修改操作需要修改的数，在 $t$ 后移的时候，我们将当前数组中对应位置的数 $x$ 和对应修改操作中要修改的数 $x’$ 进行交换，此时数组中的数变成了 $x’$，而修改操作中记录的数变成了 $x$，让我们要往回走时，就会反回来将 $x’$ 重新放回修改操作中，将 $x$ 重新放回数组中，这样就能在不存储额外变量的情况下完美实现操作。

到此为止，已经有了整个问题的大致做法，接下来还有一个关键的问题就是如何排序可以使得这三个指针总移动的次数不会太多。如果某一个指针是递增的话，那么他就不需要来回走，就是 $O(n)$ 的时间，但是我们最多也只能让某一个指针单调，而对于剩余两个指针就需要用分块去做。

因此对于所有查询先按照 $l$ 所在块的编号从小到大排序，再按照 $r$ 所在块的编号从小到大排序，再按照 $t$ 从小到大排序。通过三个关键字依次进行排序。确定了排序方法后，还需要确定每个块的大小，需要确定最合理的块的大小使得总的时间复杂度尽可能的小。

设块的大小为 $a$，则块的数量为 $\frac{n}{a}$，对于 $l$ 指针，块内移动的次数最多是 $am$，块与块之间移动的次数最多是 $2n$，因此 $l$ 的时间复杂度为 $O(am+n)$。对于 $t$ 指针，块内是单调的，因此块内最多移动 $t$ 次，而由于进行了两次分块，因此块的情况一共有 $\frac{n^2}{a^2}$ 种，所以 $t$ 的时间复杂度为 $O(t\frac{n^2}{a^2})$。对于 $r$ 指针，块内移动的次数最多是 $am$，块与块之间移动的次数最多是 $\frac{n^2}{a}$，因此 $r$ 的时间复杂度为 $O(am+\frac{n^2}{a})$。

取所有操作中时间复杂度最大的两个 $am$ 和 $t\frac{n^2}{a^2}$，由于 $n=m$，因此得出 $a=\sqrt[3]{nt}$，此时时间复杂度最优为 $O(\sqrt[3]{n^4t})$，大概 $10^6$ 级别，不是很大。

C++ 代码

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

using namespace std;

const int N = 10010, S = 1000010;

struct Query
{
    int id, l, r, t; //编号、左端点、右端点、在进行完几次修改操作之后
}q[N]; //存储所有查询操作

struct Modify
{
    int p, c; //要修改的位置、要修改的值
}c[N]; //存储所有修改操作
int qcnt, mcnt; //查询次数、修改次数

int n, m, len; //序列长度、操作次数、块的长度
int a[N], cnt[S], res[N]; //原序列、每个数在当前区间出现的次数、每个查询的结果
int id[N]; //每个下标所在的块编号

//先按 l 所在块的编号从小到大排序，再按 r 所在块的编号从小到大排序，再按 t 从小到大排序
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.r] != id[b.r]) return id[a.r] < id[b.r];
    return a.t < b.t;
}

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

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

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

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

    char op[2];
    int x, y;
    for(int i = 0; i < m; i++)
    {
        scanf("%s%d%d", op, &x, &y);
        if(*op == 'Q') qcnt++, q[qcnt] = {qcnt, x, y, mcnt};
        else c[++mcnt] = {x, y};
    }

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

    //将所有查询先按 l 所在块的编号从小到大排序，再按 r 所在块的编号从小到大排序，再按 t 从小到大排序
    sort(q + 1, q + 1 + qcnt, cmp);

    //带修改的莫队
    //指针 i, j, t 分别对应左端点、右端点、修改操作次数
    for(int k = 1, i = 1, j = 0, t = 0, ans = 0; k <= qcnt; k++)
    {
        int num = q[k].id, l = q[k].l, r = q[k].r, tm = q[k].t;
        while(j < r) add(a[++j], ans); //指针 j 右移
        while(j > r) del(a[j--], ans); //指针 j 左移
        while(i < l) del(a[i++], ans); //指针 i 右移
        while(i > l) add(a[--i], ans); //指针 i 左移
        while(t < tm) //指针 t 右移
        {
            t++;
            if(c[t].p >= i && c[t].p <= j)
            {
                del(a[c[t].p], ans);
                add(c[t].c, ans);
            }
            swap(a[c[t].p], c[t].c);
        }
        while(t > tm) //指针 t 左移
        {
            if(c[t].p >= i && c[t].p <= j)
            {
                del(a[c[t].p], ans);
                add(c[t].c, ans);
            }
            swap(a[c[t].p], c[t].c);
            t--;
        }
        res[num] = ans; //记录当前查询的答案
    }

    for(int i = 1; i <= qcnt; i++) printf("%d\n", res[i]);

    return 0;
}