这份代码

#include <bits/stdc++.h>
using namespace std;

const int N=10005;
const int M=1000005;

int n,m,cntq,cntm;
int len;
int arr[N];
int ans[N];
int cnt[M];

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

struct Query {
    int id,l,r,t;
} q[N];

struct Modify {
    int a,b;
} mod[N];

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

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

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

int main() {
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;++i) {
        scanf("%d",&arr[i]);
    }
    for (int i=1;i<=m;++i) {
        char op[2];
        int l,r;
        scanf("%s %d %d",op,&l,&r);
        if (*op=='Q') {
            ++cntq;
            q[cntq]={cntq,l,r,cntm};
        } else {
            ++cntm;
            mod[cntm]={l,r};
        }
    }
    sort(q+1,q+1+cntq,cmp);
    len=cbrt((double)n*max(cntm,1))+1;
    for (int k=1,i=0,j=1,t=0,s=0;k<=cntq;++k) {
        int id=q[k].id;
        int l=q[k].l;
        int r=q[k].r;
        int tt=q[k].t;
        while (i<r) add(arr[++i],s);
        while (i>r) del(arr[i--],s);
        while (j<l) del(arr[j++],s);
        while (j>l) add(arr[--j],s);
        while (t<tt) {
            ++t;
            if (mod[t].a>=j && mod[t].a<=i) {
                del(arr[mod[t].a],s);
                add(mod[t].b,s);
            }
            swap(arr[mod[t].a],mod[t].b);
        }
        while (t>tt) {
            if (mod[t].a>=j && mod[t].a<=i) {
                del(arr[mod[t].a],s);
                add(mod[t].b,s);
            }
            swap(arr[mod[t].a],mod[t].b);
            --t;
        }
        ans[id]=s;
    }
    for (int i=1;i<=cntq;++i) {
        printf("%d\n",ans[i]);
    }
    return 0;
}

为什么会比下面这个慢啊

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

using namespace std;

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];

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

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;
}

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

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", &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;
}