什么时候用分块?
当你发现正常数据结构无法解决的时候(比如维度特别多,很不方便或者炸空间),或者复杂到要3个 $log$ 以上才能解决时。(主要还是得看数据范围,分块的做法一般都是 $O(\sqrt{n})$ 及以上的
如何分块?
定一个块长 $B$ ,整个序列就会被分成 $\floor{n/B}$ 块,对于末尾的不完整的块,可以直接暴力修改查询
对于一个区间,会分解成两个不完整的块和中间的一些完整的块,那么我们就可以暴力不完整的块,对于完整的块我们只需要打个标记就可以了
例题:
P2801 教主的魔法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
#include <bits/stdc++.h> #define int long long using namespace std; const int N=1e6+10,mod=1e9+7; int a[N],e[N],be[N]; int L[N],R[N],tag[N]; void make(int x){ //对块进行操作,每个块都排序,那么我们在查询的时候就可以直接二分出最接近c的数,然后O(1)求出答案 for(int i=L[x];i<=R[x];i++) e[i]=a[i]; //由于a还在修改的时候有用,所以我们要另开一个数组 sort(e+L[x],e+R[x]+1); } signed main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int n,q; cin>>n>>q; for(int i=1;i<=n;i++) cin>>a[i]; int len=sqrt(n),tot=(n+len-1)/len; //定义块长,分块 for(int i=1;i<=tot;i++){ L[i]=(i-1)*len+1,R[i]=min(n,i*len); //求出每个块的左端点和右端点 for(int j=L[i];j<=R[i];j++) be[j]=i; //be是belong,序列中的下标映射到块的下标 make(i); } while(q--){ char check; cin>>check; if(check=='M'){ int l,r,w; cin>>l>>r>>w; if(be[l]==be[r]){ //如果在同一个块,直接暴力 for(int i=l;i<=r;i++) a[i]+=w; make(be[l]); //修改完之后要更新 } else{ for(int i=l;i<=R[be[l]];i++) a[i]+=w; //两个不完整的块,暴力 for(int i=L[be[r]];i<=r;i++) a[i]+=w; make(be[l]),make(be[r]); for(int i=be[l]+1;i<=be[r]-1;i++) tag[i]+=w;//完整的块,标记 } } else{ int cnt=0,l,r,c; cin>>l>>r>>c; if(be[l]==be[r]) for(int i=l;i<=r;i++) cnt+=(a[i]+tag[be[i]]>=c); else{ for(int i=l;i<=R[be[l]];i++) cnt+=(a[i]+tag[be[i]]>=c); for(int i=L[be[r]];i<=r;i++) cnt+=(a[i]+tag[be[i]]>=c); for(int i=be[l]+1;i<=be[r]-1;i++) cnt+=e+1+R[i]-lower_bound(e+L[i],e+R[i]+1,c-tag[i]); } cout<<cnt<<endl; } } return 0; }
Farmer John's Favorite Function - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
由于从 $k$ 这个位置开始,向后推的话,会发现,当我们推到 $k+6$ 的时候基本上 $a_k$ 的修改的贡献就小于 $1$ 了,也就是说,对于每个修改的 $a_k$,他的影响范围最多到 $k+6$,可以把值设为 2e9 自己推一下就可以推出来,所以我们的块长至少是 $6$,但是考虑保险设为 $10$ 也一定不错,此时对于每一次查询,我们直接修改 $a_k$ 所在的块,并且记录贡献,由于贡献是递减的,有可能在区间中的某个点之前他的贡献是 $e_k+1$,所以我们要倒着推,我们设这个区分点为 $f_i$,从前向后推,如果说存在 $f_j >= 2e9$ 那么就无解,因为我们的数最大不超过 2e9,对于最后一块区间,我们直接暴力修改即可
#include <bits/stdc++.h> #define int long long using namespace std; const int N=1e6+10,mod=1e9+7,inf=2e9; int n,q,tot; int a[N],be[N],L[N],R[N],f[N],e[N]; int sqrtt(int x){ int x_=sqrtl(x); while(x_*x_>x) x_--; while((x_+1)*(x_+1)<=x) x_++; return x_; } void make(int x){ //开方,由于考虑浮点数影响,可以求稳更新一下sqrt(x) if(x==tot) return; e[x]=0; for(int i=L[x];i<=R[x];i++) e[x]=sqrtt(a[i]+e[x]); f[x]=e[x]+1; for(int i=R[x];i>=L[x]&&f[x]!=inf;i--) f[x]=min(inf,f[x]*f[x]-a[i]); } signed main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>q; for(int i=1;i<=n;i++) cin>>a[i]; int len=max((int)10,(int)sqrt(n)); tot=(n+len-1)/len; for(int i=1;i<=tot;i++){ L[i]=(i-1)*len+1,R[i]=min(n,i*len); for(int j=L[i];j<=R[i];j++) be[j]=i; make(i); } while(q--){ int k,x; cin>>k>>x; a[k]=x,make(be[k]); int res=0; for(int i=1;i<=tot-1;i++) res=e[i]+(res>=f[i]); for(int i=L[tot];i<=n;i++) res=sqrtt(res+a[i]); cout<<res<<endl; } return 0; }
标签:10,2e9,分块,--,len,int,long,区间 From: https://www.cnblogs.com/o-Sakurajimamai-o/p/18135420