C113 带修莫队 P1903 [国家集训队] 数颜色 维护队列

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,mq,mr,a[N],B,cnt[N],ans[N],sum;
struct Qnode{ int l,r,id,tsp;}q[N];
bool cmp(const Qnode &n1,const Qnode &n2)
{
    if(n1.l/B != n2.l/B) return  n1.l<n2.l ;
    if(n1.r/B != n2.r/B)  return n1.r<n2.r ;
    return n1.tsp<n2.tsp;
}
struct Rnode{int p,c;}R[N];
void add(int x)
{
    if(!cnt[x])sum++;
    cnt[x]++;
}
void del(int x)
{
    cnt[x]--;
    if(!cnt[x])sum--;
}
int main()
{
    scanf("%d%d",&n,&m);
    B=pow(n,0.66);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    mq=mr=0;
    for(int i=1;i<=m;i++)
    {
        char s[2];int l,r;
        scanf("%s%d%d",s,&l,&r);
        if(s[0]=='Q') q[++mq]={l,r,mq,mr};
        else R[++mr]={l,r};
    }
    sort(q+1,q+1+mq,cmp);
    sum=0;memset(cnt,0,sizeof(cnt));
    for(int i=1,l=1,r=0,x=0;i<=mq;i++)
    {
        while(l>q[i].l) add(a[--l]);
        while(r<q[i].r) add(a[++r]);
        while(l<q[i].l) del(a[l++]);
        while(r>q[i].r) del(a[r--]);
        while(x<q[i].tsp)
        {
            int p=R[++x].p;
            if(l<=p && p<=r)del(a[p]),add(R[x].c);
            swap(a[p],R[x].c);
        }
        while(x>q[i].tsp)
        {
            int p=R[x].p;
            if(l<=p && p<=r)del(a[p]),add(R[x].c);
            swap(a[p],R[x--].c);
        }
        ans[q[i].id]=sum;
    }
    for(int i=1;i<=mq;i++)printf("%d\n",ans[i]);
    return 0;
}