【BZOJ 2120】 数颜色

时间：2023-03-08 15:32:09

Description

墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔*有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？

Input

第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题*分。

Output

对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔*有几种不同颜色的画笔。

Sample Input

6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

Sample Output

4
4
3
4

HINT

对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

正解是什么？我不知道
参考hzwer的思路，这题可以暴力分块，因为修改少。
记录每个颜色的上一次出现在那，然后排个序。边上暴力查找比上一个比l小的点，块内二分
话说lower_bound是查询前闭后开的区间。。。
 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 const int N=;

 int bel[N],last[],size[N],pre[N],q[N],a[N],c[N];

 int num,n,m,l,r,p,col,ans;

 void build(){

     int block=sqrt(n);

     for(int i=;i<=n;i++){

         bel[i]=(i-)/block+;

         if(bel[i]>num) num=bel[i];

         size[bel[i]]++;

         pre[i]=last[a[i]];

         c[i]=pre[i];

         last[a[i]]=i;

     }

 }

 void reset(int x){

     for(int i=q[x-]+;i<=q[x];i++) pre[i]=c[i];

     sort(pre+q[x-]+,pre+q[x]+);

 }

 int find(int x,int y){

     int tmp=lower_bound(pre+q[x-]+,pre+q[x]+,y)-pre-q[x-]-;

     return tmp;

 }

 int ask(int l,int r){

     if(bel[l]==bel[r]){

         for(int i=l;i<=r;i++) if(c[i]<l) ans++;

     }

     else{

         for(int i=l;i<=q[bel[l]];i++) if(c[i]<l) ans++;

         for(int i=q[bel[r]-]+;i<=r;i++)

         if(c[i]<l) ans++;

     }

     for(int i=bel[l]+;i<bel[r];i++) ans+=find(i,l);

     return ans;

 }

 void change(int x,int y){

     for(int i=;i<=n;i++) last[a[i]]=;

     a[x]=y;

     for(int i=;i<=n;i++){

         int t=c[i];

         c[i]=last[a[i]];

         if(t!=c[i]) reset(bel[i]);

         last[a[i]]=i;

     }

 }

 int main(){

     scanf("%d%d",&n,&m);

     for(int i=;i<=n;i++) scanf("%d",&a[i]);

     build();

     for(int i=;i<=num;i++) q[i]=q[i-]+size[i];

     for(int i=;i<=num;i++)

     reset(i);

     char s[];

     for(int i=;i<=m;i++){

         scanf("%s",s);

         if(s[]=='Q'){

             ans=;

             scanf("%d%d",&l,&r);

             printf("%d\n",ask(l,r));

         }

         else{

             scanf("%d%d",&p,&col);

             change(p,col);

         }

     }

 }

相关文章