首页 > 代码库 > bzoj2120: 数颜色 [莫队][分块]
bzoj2120: 数颜色 [莫队][分块]
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
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
4
3
4
HINT
对于100%的数据,N≤10000,M≤10000,修改操作不多于1000次,所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
带修改莫队膜版
没写过莫队就写带修改心中慌张
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 8 struct ask{ 9 int L,R,id,tm;10 };11 12 struct req{13 int ps,cl,pre;14 };15 16 const int maxn=10005,maxnum=1000005,maxm=200005,maxr=1005;17 18 int CL=1,CR=0,ans=0,tim,n,m,k,cnt=0,sz=0;19 int color[maxn],num[maxnum];20 int las[maxn],answer[maxm];21 bool vis[maxn];22 ask e[maxm];23 req w[maxr];24 25 inline bool cmp(const ask &n1,const ask &n2){26 return (n1.L/tim)==(n2.L/tim)?n1.R<n2.R:n1.L<n2.L;27 }28 29 void cala(int x){30 if(vis[x]){31 if((--num[color[x]])==0) --ans;32 }33 else{34 if((++num[color[x]])==1) ++ans;35 }36 vis[x]=!vis[x];37 }38 39 void change(int x,int c){40 if(vis[x]){ cala(x); color[x]=c; cala(x); }41 else color[x]=c;42 }43 44 int main(){45 //freopen("temp.in","r",stdin);46 char opt[2];47 int x,y;48 scanf("%d%d",&n,&m);49 tim=sqrt(n);50 51 for(int i=1;i<=n;i++){52 scanf("%d",&color[i]);53 las[i]=color[i];54 }55 56 for(int i=0;i<m;i++){57 scanf("%s%d%d",opt,&x,&y);58 if(opt[0]==‘R‘){59 w[++cnt].ps=x;60 w[cnt].cl=y;61 w[cnt].pre=las[x];62 las[x]=y;63 }64 else{65 e[++sz].L=x;66 e[sz].R=y;67 e[sz].id=sz;68 e[sz].tm=cnt;69 }70 }71 72 sort(e+1,e+1+sz,cmp);73 74 for(int i=1;i<=sz;i++){75 for(int j=e[i-1].tm+1;j<=e[i].tm;j++)76 change(w[j].ps,w[j].cl);77 for(int j=e[i-1].tm;j>=e[i].tm+1;j--)78 change(w[j].ps,w[j].pre);79 80 int l=e[i].L,r=e[i].R;81 while(CL<l) cala(CL++);82 while(CL>l) cala(--CL);83 while(CR<r) cala(++CR);84 while(CR>r) cala(CR--);85 86 answer[e[i].id]=ans;87 }88 89 for(int i=1;i<=sz;i++)90 printf("%d\n",answer[i]);91 return 0;92 }
bzoj2120: 数颜色 [莫队][分块]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。