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

这道题卡常，TLE82tps

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,block,now;
int cntt,cntq;
int in[N],pos[N],cnt[10*N],ans[N];
struct Node
{
    int l,r,id,ti;
} q[N];
struct Time
{
    int pos,col;
} t[N];
char opt;
int pl,pr,ti;
int read()
{
    int a=0,f=0;
    char c=getchar();
    for(; c<'0'||c>'9'; c=getchar())if(c=='-')f=1;
    for(; c>='0'&&c<='9'; c=getchar())a=a*10+c-'0';
    return f?-a:a;
}
bool cmp(Node x,Node y)
{
    if(pos[x.l]==pos[y.l])
    {
        if(pos[x.l]&1)
        {
            if(x.r==y.r)
                return x.ti<y.ti;
            else
                return x.r<y.r;
        }
        else
        {
            if(x.r==y.r)
                return x.ti<y.ti;
            else
                return x.r>y.r;
        }
    }
    else
        return x.l<y.l;
}
void add(int p)
{
    if(!cnt[in[p]])
        now++;
    cnt[in[p]]++;
}
void del(int p)
{
    cnt[in[p]]--;
    if(!cnt[in[p]])
        now--;
}
signed main()
{
    n=read();
    m=read();
    block=200;
    for(int i=1; i<=n; i++)
    {
        in[i]=read();
        pos[i]=(i-1)/block+1;
    }
    for(int i=1; i<=m; i++)
    {
        scanf("\n");
        opt=getchar();
        if(opt=='Q')
        {
            q[++cntq].l=read();
            q[cntq].r=read();
            q[cntq].id=cntq;
            q[cntq].ti=cntt;
        }
        else
        {
            t[++cntt].pos=read();
            t[cntt].col=read();
        }
    }
    sort(q+1,q+1+cntq,cmp);
    pl=1;
    pr=0;
    ti=0;
    for(int i=1;i<=cntq;i++)
    {
        while(pl<q[i].l)
            del(pl++);
        while(pl>q[i].l)
            add(--pl);
        while(pr<q[i].r)
            add(++pr);
        while(pr>q[i].r)
            del(pr--);
        while(ti<q[i].ti)
        {
            ti++;
            if(q[i].l<=t[ti].pos&&t[ti].pos<=q[i].r)
            {
                cnt[in[t[ti].pos]]--;
                if(!cnt[in[t[ti].pos]])
                    now--;
                if(!cnt[t[ti].col])
                    now++;
                cnt[t[ti].col]++;
            }
            swap(in[t[ti].pos],t[ti].col);
        }
        while(ti>q[i].ti)
        {
            if(q[i].l<=t[ti].pos&&t[ti].pos<=q[i].r)
            {
                cnt[in[t[ti].pos]]--;
                if(!cnt[in[t[ti].pos]])
                    now--;
                if(!cnt[t[ti].col])
                    now++;
                cnt[t[ti].col]++;
            }
            swap(in[t[ti].pos],t[ti].col);
            ti--;
        }
        ans[q[i].id]=now;
    }
    for(int i=1;i<=cntq;i++)
        printf("%lld\n",ans[i]);
    return 0;
}