BZOJ2120 数颜色_牛客博客

https://www.lydsy.com/JudgeOnline/problem.php?id=2120

题意：n个位置，每个位置一支笔，带有颜色，要求区间中不同颜色个数（带修改）
思路：带修改莫队。
注意一点，并不是一定划分块的大小为 $n^{\frac{2}{3}} </annotation> </semantics> </math>$ 时最优，比如这题,块的大小为 $\sqrt{n} </annotation> </semantics> </math>$ 时更优，因为修改次数较少。

#include<bits/stdc++.h>
using namespace std;
#define maxn (10000+10)

char command[5]; 
int n,m,SIZE,c[maxn],last[maxn],cnt[maxn*100];
int now_ans,ccnt,qcnt,ans[maxn];
int l,r,t;
struct Change{
    int x,c,last;
}C[maxn];
struct Query{
    int l,r,t,id;
    bool operator < (Query x)const{
        if(l/SIZE!=x.l/SIZE)return l/SIZE<x.l/SIZE;
        if(r/SIZE!=x.r/SIZE)l/SIZE<x.l/SIZE;
        return t<x.t;
    }
}Q[maxn];
//这个p是修改操作的编号
void moveTime(int p,int flag)
{
    if(flag==1){
        if(C[p].x>=l&&C[p].x<=r){
            cnt[C[p].c]++;
            if(cnt[C[p].c]==1)now_ans++;
            cnt[C[p].last]--;
            if(cnt[C[p].last]==0)now_ans--;
        }
        c[C[p].x]=C[p].c;
    }else{
        if(C[p].x>=l&&C[p].x<=r){
            cnt[C[p].c]--;
            if(cnt[C[p].c]==0)now_ans--;
            cnt[C[p].last]++;
            if(cnt[C[p].last]==1)now_ans++;
        }
        c[C[p].x]=C[p].last;
    }
}
//这个p是下标，位置
void move(int p,int flag)
{
    if(flag==1){
        cnt[c[p]]++;
        if(cnt[c[p]]==1)now_ans++;  
    }else{
        cnt[c[p]]--;
        if(cnt[c[p]]==0)now_ans--;
    }
}

int main()
{
    //freopen("input.in","r",stdin);
    cin>>n>>m;
    SIZE=pow(n,2.0/3);
    for(int i=1;i<=n;i++)scanf("%d",&c[i]),last[i]=c[i];
    for(int i=1;i<=m;i++)
    {
        scanf("%s",command);
        if(command[0]=='R'){
            ccnt++;
            scanf("%d%d",&C[ccnt].x,&C[ccnt].c);
            C[ccnt].last=last[C[ccnt].x];
            last[C[ccnt].x]=C[ccnt].c;
        }else{
            qcnt++;
            scanf("%d%d",&Q[qcnt].l,&Q[qcnt].r);
            Q[qcnt].t=ccnt;
            Q[qcnt].id=qcnt;
        }
    }
    sort(Q+1,Q+1+qcnt);
    l=Q[1].l,r=l-1,t=0;
    for(int i=1;i<=qcnt;i++)
    {   
        while(t<Q[i].t)moveTime(++t,1);
        while(t>Q[i].t)moveTime(t--,-1);
        while(l>Q[i].l)move(--l,1);
        while(r<Q[i].r)move(++r,1);
        while(l<Q[i].l)move(l++,-1);
        while(r>Q[i].r)move(r--,-1);
        ans[Q[i].id]=now_ans;
    }
    for(int i=1;i<=qcnt;i++)printf("%d\n",ans[i]);
    return 0;
}