黃老師的博客http://hzwer.com/8053.html

模板：

const int N=1e5+5; int a[N],belong[N]/*屬于哪個塊*/,blo/*塊的大小*/,block[1000]; void update(int l,int r){if(belong[l]==belong[r]){for(int i=l;i<=r;i++){//你的操作 }return ;}for(int i=l;i<=belong[l]*blo;i++){//你的操作 } for(int i=belong[l]+1;i<=belong[r]-1;i++){//你的操作 } for(int i=(belong[r]-1)*blo+1;i<=r;i++){//你的操作 } } int query(int l,int r){int ans=0;if(belong[l]==belong[r]){for(int i=l;i<=r;i++){//你的操作 }return ans;}for(int i=l;i<=belong[l]*blo;i++){//你的操作 } for(int i=belong[l]+1;i<=belong[r]-1;i++){//你的操作 } for(int i=(belong[r]-1)*blo+1;i<=r;i++){//你的操作 } return ans; }

數列分塊入門 1

#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a))const int N=5e4+5; int belong[N],a[N],block[1000],b; void add(int l,int r,int c){if(belong[l]==belong[r]){for(int i=l;i<=r;i++)a[i]+=c;return ;}for(int i=l;i<=belong[l]*b;i++)a[i]+=c;for(int i=belong[l]+1;i<=belong[r]-1;i++)block[i]+=c;for(int i=(belong[r]-1)*b+1;i<=r;i++)a[i]+=c;} int main(){ios::sync_with_stdio(false);cin.tie(0);int n,o,l,r,c;cin>>n;b=sqrt(n);for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)belong[i]=(i-1)/b+1;for(int i=1;i<=n;i++){cin>>o>>l>>r>>c;if(o==0)add(l,r,c);else cout<<a[r]+block[belong[r]]<<endl;}return 0; } View Code

數列分塊入門 2

新技能：邊緣塊的重置

#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a))const int N=5e4+5; int a[N],belong[N],block[1000],blo; vector<int>vc[1000]; void reset(int x){vc[x].clear();for(int i=(x-1)*blo+1;i<=x*blo;i++)vc[x].pb(a[i]);sort(vc[x].begin(),vc[x].end()); } void add(int l,int r,int c){if(belong[l]==belong[r]){for(int i=l;i<=r;i++)a[i]+=c;reset(belong[l]);return ;}for(int i=l;i<=belong[l]*blo;i++)a[i]+=c;reset(belong[l]);for(int i=belong[l]+1;i<=belong[r]-1;i++)block[i]+=c;for(int i=(belong[r]-1)*blo+1;i<=r;i++)a[i]+=c;reset(belong[r]); } int query(int l,int r,int c){int ans=0;if(belong[l]==belong[r]){for(int i=l;i<=r;i++)if(a[i]+block[belong[i]]<c)ans++;return ans;}for(int i=l;i<=belong[l]*blo;i++)if(a[i]+block[belong[i]]<c)ans++;for(int i=belong[l]+1;i<=belong[r]-1;i++){int x=c-block[i];ans+=lower_bound(vc[i].begin(),vc[i].end(),x)-vc[i].begin();}for(int i=(belong[r]-1)*blo+1;i<=r;i++)if(a[i]+block[belong[i]]<c)ans++;return ans; } int main(){ios::sync_with_stdio(false);cin.tie(0);int n,o,l,r,c;cin>>n;blo=sqrt(n);for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){belong[i]=(i-1)/blo+1;vc[belong[i]].pb(a[i]);}for(int i=1;i<=belong[n];i++)sort(vc[i].begin(),vc[i].end());for(int i=1;i<=n;i++){cin>>o>>l>>r>>c;if(o==0)add(l,r,c);else cout<<query(l,r,c*c)<<endl;}return 0; } View Code

數列分塊入門 3

#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a))const int N=1e5+5; int a[N],belong[N],block[1000],blo; vector<int>vc[1000]; void reset(int x){vc[x].clear();for(int i=(x-1)*blo+1;i<=x*blo;i++)vc[x].pb(a[i]);sort(vc[x].begin(),vc[x].end()); } void add(int l,int r,int c){if(belong[l]==belong[r]){for(int i=l;i<=r;i++)a[i]+=c;reset(belong[l]);return ;}for(int i=l;i<=belong[l]*blo;i++)a[i]+=c;reset(belong[l]);for(int i=belong[l]+1;i<=belong[r]-1;i++)block[i]+=c;for(int i=(belong[r]-1)*blo+1;i<=r;i++)a[i]+=c;reset(belong[r]); } int query(int l,int r,int c){int ans=-1;if(belong[l]==belong[r]){for(int i=l;i<=r;i++)if(a[i]+block[belong[i]]<c)ans=max(ans,a[i]+block[belong[i]]);return ans;}for(int i=l;i<=belong[l]*blo;i++)if(a[i]+block[belong[i]]<c)ans=max(ans,a[i]+block[belong[i]]);for(int i=belong[l]+1;i<=belong[r]-1;i++){int x=c-block[i];int t=lower_bound(vc[i].begin(),vc[i].end(),x)-vc[i].begin();if(t!=0)ans=max(ans,vc[i][t-1]+block[i]);}for(int i=(belong[r]-1)*blo+1;i<=r;i++)if(a[i]+block[belong[i]]<c)ans=max(ans,a[i]+block[belong[i]]);return ans; } int main(){ios::sync_with_stdio(false);cin.tie(0);int n,o,l,r,c;cin>>n;blo=sqrt(n);for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){belong[i]=(i-1)/blo+1;vc[belong[i]].pb(a[i]);}for(int i=1;i<=belong[n];i++)sort(vc[i].begin(),vc[i].end());for(int i=1;i<=n;i++){cin>>o>>l>>r>>c;if(o==0)add(l,r,c);else cout<<query(l,r,c)<<endl;}return 0; } View Code

數列分塊入門 4

#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a))const int N=1e5+5; int a[N],belong[N],blo; ll sum[1000],block[1000]; void add(int l,int r,int c){if(belong[l]==belong[r]){for(int i=l;i<=r;i++)a[i]+=c,sum[belong[i]]+=c;return ;}for(int i=l;i<=belong[l]*blo;i++)a[i]+=c,sum[belong[i]]+=c;for(int i=belong[l]+1;i<=belong[r]-1;i++)block[i]+=c;for(int i=(belong[r]-1)*blo+1;i<=r;i++)a[i]+=c,sum[belong[i]]+=c; } ll query(int l,int r,int c){ll ans=0;if(belong[l]==belong[r]){for(int i=l;i<=r;i++)ans=(ans+a[i]+block[belong[i]]);return ans;}for(int i=l;i<=belong[l]*blo;i++)ans=(ans+a[i]+block[belong[i]]);for(int i=belong[l]+1;i<=belong[r]-1;i++)ans=(ans+sum[i]+blo*block[i]);for(int i=(belong[r]-1)*blo+1;i<=r;i++)ans=(ans+a[i]+block[belong[i]]);return ans; } int main(){ios::sync_with_stdio(false);cin.tie(0);int n,o,l,r,c;cin>>n;blo=sqrt(n);for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){belong[i]=(i-1)/blo+1;sum[belong[i]]+=a[i];}for(int i=1;i<=n;i++){cin>>o>>l>>r>>c;if(o==0)add(l,r,c);else cout<<query(l,r,c)%(c+1)<<endl;}return 0; } View Code

數列分塊入門 5

套路套路

#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a))const int N=1e5+5; int a[N],belong[N],blo,flag[1000]; ll sum[1000]; void solve_sqrt(int x){if(flag[x])return ;flag[x]=1;sum[x]=0;for(int i=(x-1)*blo+1;i<=x*blo;i++){a[i]=sqrt(a[i]);sum[x]+=a[i];if(a[i]>1)flag[x]=0;} } void update(int l,int r){if(belong[l]==belong[r]){for(int i=l;i<=r;i++){sum[belong[i]]-=a[i];a[i]=sqrt(a[i]);sum[belong[i]]+=a[i];}return ;}for(int i=l;i<=belong[l]*blo;i++){sum[belong[i]]-=a[i];a[i]=sqrt(a[i]);sum[belong[i]]+=a[i];}for(int i=belong[l]+1;i<=belong[r]-1;i++)solve_sqrt(i);for(int i=(belong[r]-1)*blo+1;i<=r;i++){sum[belong[i]]-=a[i];a[i]=sqrt(a[i]);sum[belong[i]]+=a[i];} } ll query(int l,int r){ll ans=0;if(belong[l]==belong[r]){for(int i=l;i<=r;i++)ans+=a[i];return ans;}for(int i=l;i<=belong[l]*blo;i++)ans+=a[i];for(int i=belong[l]+1;i<=belong[r]-1;i++)ans+=sum[i];for(int i=(belong[r]-1)*blo+1;i<=r;i++)ans+=a[i];return ans; } int main(){ios::sync_with_stdio(false);cin.tie(0);int n,o,l,r,c;cin>>n;blo=sqrt(n);for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++){belong[i]=(i-1)/blo+1;sum[belong[i]]+=a[i];}for(int i=1;i<=n;i++){cin>>o>>l>>r>>c;if(o==0)update(l,r);else cout<<query(l,r)<<endl;}return 0; } View Code

數列分塊入門 6

新技能：單塊過大，重建塊

#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mp make_pair #define pii pair<int,int> #define mem(a,b) memset(a,b,sizeof(a))const int N=2e5+5; int a[N],belong[N],blo,m; vector<int>vc[1000]; pii query(int a){int top=1;while(a>vc[top].size())a-=vc[top++].size();return mp(top,a-1); } void rebuild(){int top=0;for(int i=1;i<=m;i++){for(int j=0;j<vc[i].size();j++)a[++top]=vc[i][j];vc[i].clear();}for(int i=1;i<=top;i++)belong[i]=(i-1)/blo+1,vc[belong[i]].pb(a[i]);m=belong[top]; } void insert(int a,int b){pii t=query(a);vc[t.first].insert(vc[t.first].begin()+t.second,b);if(vc[t.first].size()>15*blo)rebuild(); } int main(){ios::sync_with_stdio(false);cin.tie(0);int n,o,l,r,c;cin>>n;blo=sqrt(n);for(int i=1;i<=n;i++){cin>>a[i];belong[i]=(i-1)/blo+1;vc[belong[i]].pb(a[i]); }m=belong[n];for(int i=1;i<=n;i++){cin>>o>>l>>r>>c;if(o==0)insert(l,r);else{pii t=query(r);cout<<vc[t.first][t.second]<<endl;} }return 0; } View Code

數列分塊入門 7

新技能：乘法和加法的標記

#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a))const int N=1e5+5; const int MOD=1e4+7; ll a[N],belong[N],tim[1000],plu[1000]; int n,blo; void reset(int x){for(int i=(x-1)*blo+1;i<=min(x*blo,n);i++)a[i]=(a[i]*tim[belong[i]]+plu[belong[i]])%MOD;tim[x]=1;plu[x]=0; } void add(int l,int r,int c){if(belong[l]==belong[r]){reset(belong[l]);for(int i=l;i<=r;i++){a[i]+=c;a[i]%=MOD;}return ;}reset(belong[l]);for(int i=l;i<=belong[l]*blo;i++){a[i]+=c;a[i]%=MOD;}for(int i=belong[l]+1;i<=belong[r]-1;i++){plu[i]+=c;plu[i]%=MOD;}reset(belong[r]);for(int i=(belong[r]-1)*blo+1;i<=r;i++){a[i]+=c;a[i]%=MOD;} } void mul(int l,int r,int c){if(belong[l]==belong[r]){reset(belong[l]);for(int i=l;i<=r;i++){a[i]*=c;a[i]%=MOD;}return ;}reset(belong[l]);for(int i=l;i<=belong[l]*blo;i++){a[i]*=c;a[i]%=MOD;}for(int i=belong[l]+1;i<=belong[r]-1;i++){plu[i]*=c;plu[i]%=MOD;tim[i]*=c;tim[i]%=MOD; }reset(belong[r]);for(int i=(belong[r]-1)*blo+1;i<=r;i++){a[i]*=c;a[i]%=MOD;} } int main(){ios::sync_with_stdio(false);cin.tie(0);int o,l,r,c;cin>>n;blo=sqrt(n);for(int i=1;i<=n;i++){cin>>a[i];belong[i]=(i-1)/blo+1;} for(int i=1;i<=belong[n];i++)tim[i]=1; for(int i=1;i<=n;i++){cin>>o>>l>>r>>c;if(o==0){add(l,r,c);}else if(o==1){mul(l,r,c);}else{cout<<(a[r]*tim[belong[r]]+plu[belong[r]])%MOD<<endl;}}return 0; } View Code

數列分塊入門 8

#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a))const int N=1e5+5; int a[N],belong[N],blo,block[1000]; void reset(int x){for(int i=(x-1)*blo+1;i<=x*blo;i++){a[i]=block[belong[i]];} block[x]=-1; } int query(int l,int r,int c){int ans=0;if(belong[l]==belong[r]){if(block[belong[l]]!=-1)reset(belong[l]);for(int i=l;i<=r;i++){if(a[i]!=c)a[i]=c;else ans++;}return ans;}if(block[belong[l]]!=-1)reset(belong[l]);for(int i=l;i<=belong[l]*blo;i++){if(a[i]!=c)a[i]=c;else ans++; }for(int i=belong[l]+1;i<=belong[r]-1;i++){if(block[i]!=-1){if(block[i]!=c)block[i]=c;else ans+=blo; } else{for(int j=(i-1)*blo+1;j<=i*blo;j++){if(a[j]!=c)a[j]=c;else ans++;}block[i]=c;}}if(block[belong[r]]!=-1)reset(belong[r]);for(int i=(belong[r]-1)*blo+1;i<=r;i++){if(a[i]!=c)a[i]=c;else ans++;}return ans; } int main(){ios::sync_with_stdio(false);cin.tie(0);mem(block,-1);int n,o,l,r,c;cin>>n;blo=sqrt(n);for(int i=1;i<=n;i++){cin>>a[i];belong[i]=(i-1)/blo+1;} for(int i=1;i<=n;i++){cin>>l>>r>>c;cout<<query(l,r,c)<<endl;}return 0; } View Code

數列分塊入門 9

區間眾數

#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) const int N=1e5+5; int a[N],belong[N],blo,cnt[N],val[N]; vector<int>pos[N]; vector<int>v; int f[1000][1000]; int n,l,r; void init(int x){mem(cnt,0);int mx=0,c=0;for(int i=(x-1)*blo+1;i<=n;i++){cnt[a[i]]++;if(cnt[a[i]]>c){c=cnt[a[i]];mx=a[i];}else if(cnt[a[i]]==c&&a[i]<mx){mx=a[i];} f[x][belong[i]]=mx;} } int cont(int l,int r,int x){return upper_bound(pos[x].begin(),pos[x].end(),r)-lower_bound(pos[x].begin(),pos[x].end(),l); } int query(int l,int r){int ans=0,c=0;if(l==r){for(int i=l;i<=r;i++){int t=cont(l,r,a[i]);if(t>c){c=t;ans=a[i];} else if(t==c&&a[i]<ans){ans=a[i];}}return ans;}ans=f[belong[l]+1][belong[r]-1];c=cont(l,r,ans);for(int i=l;i<=belong[l]*blo;i++){int t=cont(l,r,a[i]);if(t>c){c=t;ans=a[i];} else if(t==c&&a[i]<ans){ans=a[i];}}for(int i=(belong[r]-1)*blo+1;i<=r;i++){int t=cont(l,r,a[i]);if(t>c){c=t;ans=a[i];} else if(t==c&&a[i]<ans){ans=a[i];}}return ans; } int main(){ios::sync_with_stdio(false);cin.tie(0);cin>>n;blo=sqrt(n);for(int i=1;i<=n;i++){cin>>a[i];v.pb(a[i]);belong[i]=(i-1)/blo+1;}sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());for(int i=1;i<=n;i++){int t=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;val[t]=a[i];a[i]=t;pos[a[i]].pb(i);}for(int i=1;i<=belong[n];i++){init(i);}for(int i=1;i<=n;i++){cin>>l>>r;cout<<val[query(l,r)]<<endl;}return 0; } View Code

?

轉載于:https://www.cnblogs.com/widsom/p/8413266.html

總結

以上是生活随笔為你收集整理的算法笔记--数列分块的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。