【学习笔记】震惊,全机房都会分块了,就我没有 (3)

思想很好懂。难点是边界的处理,需要大力分类讨论。

#include <bits/stdc++.h> #define int long long using namespace std; const int maxn=1e5+10; const int maxm=1e3+10; const int Mod=10007; int n,m,S,pos; int a[maxm][maxm],b[maxm][maxm],len[maxn]; inline int read(){ int x=0;bool fopt=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar())if(ch=='-')fopt=0; for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48; return fopt?x:-x; } inline void build(){ int x=0,cnt=m/S,lenth=0; if(m%S!=0)cnt++; m+=S;pos=0;S=sqrt(m);//注意最后一个块的大小 for(int i=1;i<=cnt;i++){ for(int j=1;j<=len[i];j++){ x++; int nowbelong=(x-1)/S+1; b[nowbelong][++lenth]=a[i][j]; a[i][j]=0; if(lenth>=S)lenth=0; } } cnt=m/S; if(m%S==0)cnt++; for(int i=1;i<cnt;i++){ len[i]=S; for(int j=1;j<=len[i];j++) a[i][j]=b[i][j]; } if(m%S==0)len[cnt]=S; else len[cnt]=m-S*S;//同上 for(int j=1;j<=len[cnt];j++) a[cnt][j]=b[cnt][j]; } signed main(){ n=m=read();S=sqrt(n); for(int i=1;i<=n;i++){ int x=read(); int nowbelong=(i-1)/S+1; a[nowbelong][++len[nowbelong]]=x; } for(int i=1;i<=n;i++){ int opt=read(),l=read(),r=read(),c=read(); if(opt==0){ pos++; int x=0,j; for(j=1;j<=S;j++){ if(x+len[j]>=l)break; else x+=len[j];//暴力查找 } len[j]++;l-=x; for(int i=len[j];i>l;i--) a[j][i]=a[j][i-1];//暴力后移 a[j][l]=r; if(pos>=S)build();//块太大了,直接重构 }else{ int x=0,j; for(j=1;j<=S;j++){ if(x+len[j]>=r)break; else x+=len[j]; } printf("%lld\n",a[j][r-x]); } } return 0; } 数列分块入门 7

区间乘法,区间加法,单点询问。

类似线段树的方法,维护两个标记即可。会线段树 2 就会这个。不会有人不会乘法分配律吧不会吧不会吧。

不同的是暴力维护散点的时候要先将标记下放,否则乘法会出问题(显然)。当标记下放之后,一定要把标记清零(乘法标记变成 1)。

由于模数较小,导致可能爆负,所以建议读入的时候就模一下。

#include <bits/stdc++.h> #define int long long using namespace std; const int maxn=1e5+10; const int Mod=10007; int n,S; int a[maxn]; inline int read(){ int x=0;bool fopt=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar())if(ch=='-')fopt=0; for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48; return fopt?x:-x; } int belong[maxn],sum[maxn],L[maxn],R[maxn]; int tagadd[maxn],tagmul[maxn]; void add(int l,int r,int c){ for(int i=L[belong[l]];i<=R[belong[l]];i++){ a[i]=(a[i]*tagmul[belong[l]]%Mod+tagadd[belong[l]]+Mod)%Mod; if(l<=i&&i<=r)a[i]=(a[i]+c+Mod)%Mod; } tagadd[belong[l]]=0;tagmul[belong[l]]=1; if(belong[l]!=belong[r]){ for(int i=L[belong[r]];i<=R[belong[r]];i++){ a[i]=(a[i]*tagmul[belong[r]]%Mod+tagadd[belong[r]]+Mod)%Mod; if(i<=r)a[i]=(a[i]+c+Mod)%Mod; } } tagadd[belong[r]]=0;tagmul[belong[r]]=1; for(int i=belong[l]+1;i<belong[r];i++) tagadd[i]=(tagadd[i]+c+Mod)%Mod; } void mul(int l,int r,int c){ for(int i=L[belong[l]];i<=R[belong[l]];i++){ a[i]=(a[i]*tagmul[belong[l]]%Mod+tagadd[belong[l]]+Mod)%Mod; if(l<=i&&i<=r)a[i]=(a[i]*c+Mod)%Mod; } tagadd[belong[l]]=0;tagmul[belong[l]]=1; if(belong[l]!=belong[r]){ for(int i=L[belong[r]];i<=R[belong[r]];i++){ a[i]=(a[i]*tagmul[belong[r]]%Mod+tagadd[belong[r]]+Mod)%Mod; if(i<=r)a[i]=(a[i]*c+Mod)%Mod; } } tagadd[belong[r]]=0;tagmul[belong[r]]=1; for(int i=belong[l]+1;i<belong[r];i++){ tagadd[i]=(tagadd[i]*c+Mod)%Mod;//加法标记也要乘c tagmul[i]=(tagmul[i]*c+Mod)%Mod; } } signed main(){ n=read();S=sqrt(n); for(int i=1;i<=n;i++) a[i]=read()%Mod; for(int i=1;i<=n;i++){ belong[i]=(i-1)/S+1; if(!L[belong[i]])L[belong[i]]=i; R[belong[i]]=i; tagadd[belong[i]]=0; tagmul[belong[i]]=1; } for(int i=1;i<=n;i++){ int opt=read(),l=read(),r=read(),c=read()%Mod; if(l>r)swap(l,r); if(opt==0){ add(l,r,c); }else if(opt==1){ mul(l,r,c); }else{ printf("%lld\n",(a[r]*tagmul[belong[r]]%Mod+tagadd[belong[r]])%Mod); } } return 0; } 数列分块入门 8

操作涉及区间询问等于一个数 \(c\) 的元素,并将这个区间的所有元素改为 \(c\)

区间推平,震惊,珂朵莉树

应该是这几道题里码量最大的(不过如此)。

我们维护的标记要有以下几种情况:

块内值不相等(INF),块内值相等但不是 \(c\)(相等的那个数),块内值相等且都是 \(c\)\(c\))。

注意 hzwer 的标程中第一种情况是 -1,不过我感觉可能 \(c=-1\),所以就改成 INF 了。

INF 的话,直接暴力扫一遍统计更新就可。最后还要统计一下是否更新标记。

第二种情况只需要更新,还是小块暴力改,大块改标记。

第三种情况直接更新答案了,不用更新。

大力分类讨论。

#include <bits/stdc++.h> #define int long long using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; int n,S; int a[maxn]; inline int read(){ int x=0;bool fopt=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar())if(ch=='-')fopt=0; for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48; return fopt?x:-x; } int belong[maxn],L[maxn],R[maxn],v[maxn]; inline void Solve(int l,int r,int c){ int ans=0; if(belong[l]==belong[r]){ if(v[belong[l]]==c)ans+=r-l+1; else{ if(v[belong[l]]!=INF){ for(int i=L[belong[l]];i<=R[belong[l]];i++) a[i]=v[belong[l]]; } for(int i=l;i<=r;i++) if(a[i]==c)ans++; else a[i]=c; bool flag=0; for(int i=L[belong[l]];i<=R[belong[l]];i++) if(a[i]!=c){ flag=1;break; } if(flag)v[belong[l]]=INF; else v[belong[l]]=c; } }else{ if(v[belong[l]]==c)ans+=R[belong[l]]-l+1; else{ if(v[belong[l]]!=INF){ for(int i=L[belong[l]];i<=R[belong[l]];i++) a[i]=v[belong[l]]; } for(int i=l;i<=R[belong[l]];i++) if(a[i]==c)ans++; else a[i]=c; bool flag=0; for(int i=L[belong[l]];i<=R[belong[l]];i++) if(a[i]!=c){ flag=1;break; } if(flag)v[belong[l]]=INF; else v[belong[l]]=c; } if(v[belong[r]]==c)ans+=r-L[belong[r]]+1; else{ if(v[belong[r]]!=INF){ for(int i=L[belong[r]];i<=R[belong[r]];i++) a[i]=v[belong[r]]; } for(int i=L[belong[r]];i<=r;i++) if(a[i]==c)ans++; else a[i]=c; bool flag=0; for(int i=L[belong[r]];i<=R[belong[r]];i++) if(a[i]!=c){ flag=1;break; } if(flag)v[belong[r]]=INF; else v[belong[r]]=c; } for(int i=belong[l]+1;i<belong[r];i++){ if(v[i]==c)ans+=S; else{ if(v[i]!=INF)v[i]=c; else{ for(int j=L[i];j<=R[i];j++) if(a[j]==c)ans++; else a[j]=c; bool flag=0; for(int j=L[i];j<=R[i];j++) if(a[j]!=c){ flag=1;break; } if(flag)v[i]=INF; else v[i]=c; } } } } printf("%lld\n",ans); } signed main(){ n=read();S=sqrt(n); for(int i=1;i<=n;i++){ a[i]=read(); belong[i]=(i-1)/S+1; if(!L[belong[i]])L[belong[i]]=i; R[belong[i]]=i; v[i]=INF; } for(int i=1;i<=n;i++){ int l=read(),r=read(),c=read(); Solve(l,r,c); } return 0; } 数列分块入门 9

求区间最小众数。

其实这个题我 TLE 92pts,据说离散化后改块长可过,但是这个代码已经能过蒲公英那道题了,就懒得改了。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpwygs.html