莫队算法

namespace mo
{
    int n,q,blo;
    ll a[__],ans[__],res;
    struct query{int l,r,id;}qj[__];

    void sfd(){fup(i,1,n)scanf("%lld",a+i);}
    void sfq(){fup(i,1,q)scanf("%d%d",&qj[i].l,&qj[i].r),qj[i].id=i;}
    void pf(){fup(i,1,q)printf("%lld\n",ans[i]);}
    void add(int x)
    {
    }
    void cut(int x)
    {
    }
    bool cmp(const query& x,const query& y)
    {
        if(x.l/blo==y.l/blo)return x.r<y.r;
        return x.l<y.l;
    }
    void solve()
    {
        blo=sqrt(n+0.1);
        sort(qj+1,qj+q+1,cmp);
        int l=1,r=0;res=0;
        fup(i,1,q)
        {
            while(r<qj[i].r)++r,add(r);
            while(l>qj[i].l)--l,add(l);
            while(r>qj[i].r)cut(r),--r;
            while(l<qj[i].l)cut(l),++l;
            ans[qj[i].id]=res;
        }
    }
};

带修改莫队

const int __=10005;
int a[__],b[__],n,qdx=0,mdx=0,bsz;
int ans[__],times[1000005];

struct query
{
    int l,r,md,id;
    void set(int _l,int _r,int _md,int _id)
    {
        l=_l,r=_r,md=_md,id=_id;
    }
    bool operator<(const query &b)const
    {
        if(l/bsz!=b.l/bsz)return l<b.l;
        if(r/bsz!=b.r/bsz)return r<b.r;
        return id<b.id;
    }
}que[__];

struct modfiy
{
    int wz,x,y;
    void set(int _wz,int _x,int _y)
    {
        wz=_wz,x=_x,y=_y;
    }
}mod[__];

int res=0;

void add(int x)
{
    if(!times[x])++res;
    ++times[x];
}

void cut(int x)
{
    if(times[x]==1)--res;
    --times[x];
}

void upd(int l,int r,int t)
{
    if(l<=mod[t].wz && mod[t].wz<=r)
        cut(mod[t].x),add(mod[t].y);
    a[mod[t].wz]=mod[t].y;
}

void del(int l,int r,int t)
{
    if(l<=mod[t].wz && mod[t].wz<=r)
        add(mod[t].x),cut(mod[t].y);
    a[mod[t].wz]=mod[t].x;
}

void work()
{
    bsz=(int)pow(n,2.0/3);
    sort(que+1,que+1+qdx);
    int l=1,r=0,t=0;
    fup(i,1,qdx)
    {
        while(t<que[i].md)++t,upd(l,r,t);
        while(t>que[i].md)del(l,r,t),--t;
        while(l<que[i].l)cut(a[l]),++l;
        while(l>que[i].l)--l,add(a[l]);
        while(r<que[i].r)++r,add(a[r]);
        while(r>que[i].r)cut(a[r]),--r;
        ans[que[i].id]=res;
    }
}

int main()
{
    int q;sf("%d%d",&n,&q);
    fup(i,1,n)sf("%d",&a[i]),b[i]=a[i];
    fup(i,1,q)
    {
        char op[2];int l,r;
        sf("%s%d%d",op,&l,&r);
        if(op[0]=='Q')
            ++qdx,que[qdx].set(l,r,mdx,qdx);
        if(op[0]=='R')
            mod[++mdx].set(l,0,r);
    }
    fup(i,1,mdx)
    {
        mod[i].x=b[mod[i].wz];
        b[mod[i].wz]=mod[i].y;
    }
    work();
    fup(i,1,qdx)
        pf("%d\n",ans[i]);
    return 0;
}