首页 > 代码库 > BZOJ2120 数颜色 分块+二分法
BZOJ2120 数颜色 分块+二分法
题意：给定一个颜色序列，维护：1、单点修改 2、区间查询不同颜色的种数
题解：
定义f[i]为i左边第一个和i颜色相同的位置，用分块来维护f。
询问：看区间中有多少个位置的f[i]<l
更新：暴力枚举p左右最近的与p颜色相同的位置，更新即可
#include <cmath>#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;const int MAXS=100+2;const int MAXC=1000000+2;struct BLOCK{ int a[MAXS],b[MAXS],c[MAXS];}block[MAXS];int N,M,S,C,f[MAXC];char s[3];void Change(int x,int c){ int p=(x-1)/S+1,m=(1+S)>>1; for(int l=1,r=S;l<r;m=(l+r)>>1){ if(block[p].b[m]<block[p].a[x-(p-1)*S]) l=m+1; else r=m; } block[p].b[m]=c; while(m!=1 && block[p].b[m-1]>block[p].b[m]) swap(block[p].b[m-1],block[p].b[m]),m--; while(m!=S && block[p].b[m+1]<block[p].b[m]) swap(block[p].b[m+1],block[p].b[m]),m++; block[p].a[x-(p-1)*S]=c;}void Update(int x,int c){ int p=(x-1)/S+1,t=-1; for(int i=x+1;i<=N;i++){ if(block[(i-1)/S+1].c[i-(i-1)/S*S]==block[p].c[x-(p-1)*S]){ Change(i,block[p].a[x-(p-1)*S]); break; } } for(int i=x+1;i<=N;i++) if(block[(i-1)/S+1].c[i-(i-1)/S*S]==c){ Change(i,x); break; } Change(x,-1); for(int i=x-1;i;i--) if(block[(i-1)/S+1].c[i-(i-1)/S*S]==c){ Change(x,i); break; } block[p].c[x-S*(p-1)]=c;}int Find(int p,int t){ int m=(1+S)>>1,l=1,r=S; while(l<r){ if(block[p].b[m]>=t) r=m-1; else l=m+1; m=(l+r)>>1; } if(block[p].b[l]>=t) l--; return l;}int Query(int l,int r){ int ret=0,m=(1+S)>>1,t=l; if((l-1)%S){ int p=(l-1)/S+1; for(int i=l-S*(p-1);i<=S && i<=r-S*(p-1);i++) if(block[p].a[i]<t) ret++; l=S*p+1; } while(l+S-1<=r) ret+=Find((l-1)/S+1,t),l+=S; if(r%S){ int p=l/S+1; for(int i=1;i<=r-S*(p-1);i++) if(block[p].a[i]<t) ret++; } return ret;}int main(){ memset(f,-1,sizeof(f)); memset(block,0X7F,sizeof(block)); scanf("%d %d",&N,&M),S=ceil(sqrt((double)N)); for(int i=1,j=1,k=1,c;i<=N;i++,j++){ scanf("%d",&block[k].c[j]); block[k].a[j]=block[k].b[j]=f[block[k].c[j]],f[block[k].c[j]]=i; if(j==S || i==N){ sort(block[k].b+1,block[k].b+j+1); j=0,k++; } } C=(N%S?N/S+1:N/S); for(int i=1,a,b;i<=M;i++){ scanf("%s %d %d",s,&a,&b); if(s[0]==‘R‘) Update(a,b); if(s[0]==‘Q‘) printf("%d\n",Query(a,b)); } return 0;}
BZOJ2120 数颜色 分块+二分法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。