企业官网建设流程全解析

分块是一种类似线段树的算法，便于区间、单点加法，区间、单点求值。

比如有一组元素A :1，2，3，2，5，6，5，7，9。

• 把它3个一块1，2，3 2，5，6 5，7，9。
• 假设要将第2个数到第7个数都加2。
• 我们发现第2块的数都要加2，我们不妨建一个数组tag，tag[k]表示第k块整体加的数。
• 原数组A变成1，4，5 2，5，6 7，7，9 tag[2]=2（边角不成整块的直接在原数组上加，成整块的在tag上标记）。
• 如果要我们求第5个数，第五个数属于第二块，用A[5]+tag[2]即可。

那么几个元素一块最好呢？设n个元素B个一块，每次加法要执行B+n/B次操作，要使这个值最小，B要等于根号n，所以这段程序的时间复杂度为O(根号n*操作次数)。

例题：

n个元素n此操作（n<50000）每次操作输入opt,l,r,c。若 opt=0，表示将位于 [l,r] 的之间的数字都加 c。若 opt=1，表示询问第r个数的值（l 和 c 忽略）。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=50000+10; int n; int B;//每块里元素个数 int tot;//块数 int L[N],R[N];//第k块的左右端点 int bel[N];//第i个元素属于bel[i]块 ll a[N];//原数组（不算tag） ll tag[N];//第k的标记tag[k] void init(){ B=sqrt(n)+1; tot=(n+B-1)/B;//向上取整 for(int k=1;k<=tot;k++){ //L[1]=1,R[1]=B //L[2]=B+1,R[2]=2B //... L[k]=(k-1)*B+1; R[k]=min(n,k*B); for(int i=L[k];i<=R[k];i++)bel[i]=k; } } void add(int l,int r,ll c){ int lb=bel[l],rb=bel[r]; if(lb==rb){//l,r都在一整块 for(int i=l;i<=r;i++)a[i]+=c; return; } for(int i=l;i<=R[lb];i++)a[i]+=c;//左边角料 ,无法打标记 for(int i=L[rb];i<=r;i++)a[i]+=c;//右边角料 ,无法打标记 for(int k=lb+1;k<=rb-1;k++)tag[k]+=c;//中间整块部分 } ll query(int r){//查询 return a[r]+tag[bel[r]]; } int main(){ cin>>n; init(); for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++){ int op,l,r; ll c; cin>>op>>l>>r>>c; if(!op)add(l,r,c); else cout<<query(r)<<endl; } return 0; }

区间加法区间求和：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=50000+10; int n,mod; int B;//每块里元素个数 int tot;//块数 int L[N],R[N];//第k块的左右端点 int bel[N];//第i个元素属于bel[i]块 ll a[N];//原数组（不算tag） ll tag[N];//第k的标记tag[k] ll sum[N];//sum[k]表示原数组第k块的和 void init(){ B=sqrt(n)+1; tot=(n+B-1)/B; for(int k=1;k<=tot;k++){ L[k]=(k-1)*B+1; R[k]=min(n,k*B); for(int i=L[k];i<=R[k];i++)bel[i]=k; } } void add(int l,int r,ll c){ int lb=bel[l],rb=bel[r]; if(lb==rb){ for(int i=l;i<=r;i++){ a[i]+=c; sum[lb]+=c; } return; } for(int i=l;i<=R[lb];i++){ a[i]+=c; sum[lb]+=c; } for(int i=L[rb];i<=r;i++){ a[i]+=c; sum[rb]+=c; } for(int k=lb+1;k<=rb-1;k++){ tag[k]+=c; } } __int128 query(int l,int r,int c){ int lb=bel[l],rb=bel[r]; __int128 ans=0; if(lb==rb){ for(int i=l;i<=r;i++)ans=ans+a[i]+tag[lb]; return ans; } for(int i=l;i<=R[lb];i++)ans=ans+a[i]+tag[lb]; for(int i=L[rb];i<=r;i++)ans=ans+a[i]+tag[rb]; for(int k=lb+1;k<=rb-1;k++)ans+=sum[k]+(__int128)tag[k]*(R[k]-L[k]+1); return ans; } int main(){ cin>>n; init(); for(int i=1;i<=n;i++){ cin>>a[i]; sum[bel[i]]+=a[i]; } for(int i=1;i<=n;i++){ int op,l,r; ll c; cin>>op>>l>>r>>c; mod=c+1; if(!op)add(l,r,c); else cout<<(ll)(((query(l,r,c)%mod)+mod)%mod)<<endl; } return 0; }

求区间内小余c平方的个数：

这是分块经典例题，维护数组v，也是B个元素一块每块内的元素时刻与原数组对应，但不同的是对于块内元素是单调递增的。在查询的时候，暴力查询边角元素（不成整块），查询整块时用二分查询v数组对应块中小余c*c-tag[k]的元素。

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=50000+10; int n,mod; int B;//每块里元素个数 int tot;//块数 int L[N],R[N];//第k块的左右端点 int bel[N];//第i个元素属于bel[i]块 ll a[N];//原数组（不算tag） ll tag[N];//第k的标记tag[k] ll v[N]; void resort(int k){//维护v数组 for(int i=L[k];i<=R[k];i++)v[i]=a[i]; sort(v+L[k],v+R[k]+1); } void init(){ B=sqrt(n)+1; tot=(n+B-1)/B; for(int k=1;k<=tot;k++){ L[k]=(k-1)*B+1; R[k]=min(n,k*B); for(int i=L[k];i<=R[k];i++)bel[i]=k; } } void add(int l,int r,ll c){ int lb=bel[l],rb=bel[r]; if(lb==rb){ for(int i=l;i<=r;i++)a[i]+=c; resort(lb); return; } for(int i=l;i<=R[lb];i++)a[i]+=c; for(int i=L[rb];i<=r;i++)a[i]+=c; resort(lb); resort(rb); for(int k=lb+1;k<=rb-1;k++)tag[k]+=c; } int count_less_block(int k,ll x){//二分查询v数组块内小余x-tag[k]的个数 ll need=x-tag[k]; return lower_bound(v+L[k],v+R[k]+1,need)-(v+L[k]); } ll query(int l,int r,ll x){ int lb=bel[l],rb=bel[r]; int ans=0; if(lb==rb){ for(int i=l;i<=r;i++){ if(a[i]+tag[lb]<x)ans++; } return ans; } //暴力查询不成块的元素 for(int i=l;i<=R[lb];i++){ if(a[i]+tag[lb]<x)ans++; } for(int i=L[rb];i<=r;i++){ if(a[i]+tag[rb]<x)ans++; } for(int k=lb+1;k<=rb-1;k++)ans+=count_less_block(k,x); return ans; } int main(){ cin>>n; init(); for(int i=1;i<=n;i++)cin>>a[i]; for(int k=1;k<=tot;k++)resort(k); for(int i=1;i<=n;i++){ int op,l,r; ll c; cin>>op>>l>>r>>c; if(!op)add(l,r,c); else cout<<query(l,r,c*c)<<endl; } return 0; }

谢谢观看。