首页 > 代码库 > 【分块】bzoj2120 数颜色
【分块】bzoj2120 数颜色
分块，在每个点记录一下它之前离它最近的相同颜色的位置pre[i]，显然问题转化成了求[l,r]中pre[i]<l的值的个数。
这是分块擅长的，在每个块内记录有序表，查询时对零散的暴力，整块的二分即可。
修改时有点麻烦，设修改a[p]。
可能会对pre[p]产生影响；
可能会对p位置之后的第一个 与a[p]修改前相等的值 的pre 产生影响；
可能会对p位置之后的第一个 与a[p]修改后相等的值 的pre 产生影响。
细节蛮多，调了很久。<---蒟蒻。
1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int n,m,sz,sum,l[30],r[30],num[10001],pre[10001],preb[10001],a[10001],x,y,pos[1000001]; 7 int Res,Num;char C,CH[12]; 8 inline int G() 9 {10 Res=0;C=‘*‘; 11 while(C<‘0‘||C>‘9‘)C=getchar();12 while(C>=‘0‘&&C<=‘9‘){Res=Res*10+(C-‘0‘);C=getchar();}13 return Res;14 }15 inline void P(int x)16 {17 Num=0;if(!x){putchar(‘0‘);puts("");return;}18 while(x>0)CH[++Num]=x%10,x/=10;19 while(Num)putchar(CH[Num--]+48);20 puts("");21 }22 void makeblock()23 {24 sz=sqrt((double)n*log2(n)); if(!sz) sz=1;25 for(sum=1;sum*sz<n;sum++)26 {27 l[sum]=(sum-1)*sz+1;28 r[sum]=sum*sz;29 for(int i=l[sum];i<=r[sum];i++)30 num[i]=sum;31 }32 l[sum]=sz*(sum-1)+1;33 r[sum]=n;34 for(int i=l[sum];i<=r[sum];i++)35 num[i]=sum;36 }37 void makepre()38 {39 for(int i=1;i<=n;i++) {pre[i]=pos[a[i]]; pos[a[i]]=i;}40 memcpy(preb,pre,sizeof(pre));41 for(int i=1;i<=sum;i++) sort(pre+l[i],pre+r[i]+1);42 }43 inline void query()44 {45 int res=0;46 if(num[x]+1>=num[y]) {for(int i=x;i<=y;i++) if(preb[i]<x) res++;}47 else48 {49 for(int i=x;i<=r[num[x]];i++) if(preb[i]<x) res++;50 for(int i=l[num[y]];i<=y;i++) if(preb[i]<x) res++;51 for(int i=num[x]+1;i<num[y];i++) res+=lower_bound(pre+l[i],pre+r[i]+1,x)-(pre+l[i]);52 }53 P(res);54 }55 inline void update()56 {57 int t=0;58 for(int i=x+1;i<=n;i++)59 if(a[i]==y)60 {*lower_bound(pre+l[num[i]],pre+r[num[i]],preb[i])=x; preb[i]=x;61 sort(pre+l[num[i]],pre+r[num[i]]+1); break;}62 a[0]=y;63 for(int i=x-1;i>=0;i--)64 if(a[i]==y)65 {*lower_bound(pre+l[num[x]],pre+r[num[x]],preb[x])=i; preb[x]=i;66 sort(pre+l[num[x]],pre+r[num[x]]+1); break;}67 int t2=a[x]; a[x]=y;68 for(int i=x;i>=1;i--)69 if(a[i]==t2)70 {t=i; break;}71 for(int i=x+1;i<=n;i++)72 if(a[i]==t2)73 {*lower_bound(pre+l[num[i]],pre+r[num[i]],preb[i])=t; preb[i]=t;74 sort(pre+l[num[i]],pre+r[num[i]]+1); break;}75 }char op[1];76 int main()77 {78 n=G();m=G();79 for(int i=1;i<=n;i++) a[i]=G();80 makeblock(); makepre();81 for(int i=1;i<=m;i++)82 {83 scanf("%s",op);x=G();y=G();84 if(op[0]==‘Q‘) query();85 else update();86 }87 return 0;88 }
【分块】bzoj2120 数颜色
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。