https://www.luogu.com.cn/problem/P1903

const int N = 1000010;
ll n, m, ans[N], pos[N];
int cnt[N], len, mq, mc, a[N];
int res = 0;
struct Q
{
    int id, l, r, t;
}q[N];
struct Time
{
    int old, now;
}ti[N];
int  get(int  x) { return x / len; }
bool cmp(Q x, Q y)
{
    int al = get(x.l), bl = get(y.l);
    int ar = get(x.r), br = get(y.r);
    if (al != bl) return al < bl;
    if (ar != br) return ar < br;
    return x.t < y.t;
}
void add(int x)
{
    cnt[x]++;
    if (cnt[x] == 1) res++;
}
void det(int x)
{
    cnt[x]--;
    if (cnt[x] == 0) res--;
}
void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++)
    {
        string s;
        int x, y;
        cin >> s >> x >> y;
        if (s == "Q") mq++,q[mq] = { mq,x,y,mc };
        else ti[++mc] = { x,y };
    }
    len = cbrt((double)n * max(1, mc)) + 1;
    sort(q + 1, q + 1 + mq, cmp);

    for (int j = 0, i = 1, t = 0, k = 1; k <= mq; k++)
    {
        int  id = q[k].id, l = q[k].l, r = q[k].r, tm = q[k].t;
        while (i > l) i--, add(a[i]);
        while (j < r) j++, add(a[j]);
        while (l > i) det(a[i]), i++;
        while (j > r) det(a[j]), j--;
        while (t < tm)
        {
            t++;
            int xb = ti[t].old;
            if (i <= xb && xb <= j)
            {
                det(a[xb]);
                add(ti[t].now);
            }
            swap(a[xb], ti[t].now);
        }
        while (t > tm)
        {
            int xb = ti[t].old;
            if (i <= xb && xb <= j)
            {
                det(a[xb]);
                add(ti[t].now);
            }
            swap(a[xb], ti[t].now);
            t--;
        }
        ans[id] = res;
    }
    for (int i = 1; i <= mq; i++) cout << ans[i] << '\n';
}