入门（模板）"/>
分块入门（模板）
以前没玩过分块，只知道基本的概念，也没刷过题，先挂几个题。
ps：这比我当初学线段树、主席树时要简单。
样例一：区间修改+单点查询
const int maxn=5e5+7;
ll n,a[maxn],c,bl[maxn],b[maxn];
void add(ll l,ll r,ll x){for(int i=l;i<=min(bl[l]*c,r);i++) a[i]+=x;if(bl[l]!=bl[r]) for(int i=(bl[r]-1)*c+1;i<=r;i++) a[i]+=x;for(int i=bl[l]+1;i<bl[r];i++) b[i]+=x;
}
int main(){n=read(); c=sqrt(n);for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=n;i++) bl[i]=(i-1)/c+1;while(n--){ll op,l,r,x;op=read(); l=read(); r=read(); x=read();if(!op) add(l,r,x);else printf("%lld\n",a[r]+b[bl[r]]);}
}
样例二：区间修改+区间查询 小于 c元素的个数(vector 二分)
询问操作:
1、不完整的块枚举统计即可；
2、而要在每个整块内寻找小于一个值的元素数，于是我们不得不要求块内元素是有序的，这样就能使用二分法对块内查询，需要预处理时每块做一遍排序，复杂度O(nlogn)，每次查询在√n个块内二分，以及暴力2√n个元素，总复杂度O(nlogn + n√nlog√n)。
每次修改，边块的vector必须重构。必须在vector里面二分，不能改变原数组的位置。
#define bol(x) ((x-1)*c+1)
const int maxn=5e5+7;
int n,a[maxn],c,b[maxn],add[507];
vector<int>v[507];
//重构
void reset(int x){v[x].clear();for(int i=bol(x);i<=min(bol(x+1)-1,n);i++) v[x].push_back(a[i]);sort(v[x].begin(),v[x].end());
}
void modify(int l,int r,int x){int bl=b[l],br=b[r];if(bl==br){for(int i=l;i<=r;i++) a[i]+=x;reset(bl); return;}for(int i=l;i<bol(bl+1);i++) a[i]+=x;for(int i=bol(br);i<=r;i++) a[i]+=x;for(int i=bl+1;i<br;i++) add[i]+=x;reset(bl); reset(br);
}
int query(int l,int r,int x){int bl=b[l],br=b[r],ans=0;if(bl==br){for(int i=l;i<=r;i++) if(a[i]+add[bl]<x) ans++;return ans;}for(int i=l;i<bol(bl+1);i++) if(a[i]+add[bl]<x) ans++;for(int i=bol(br);i<=r;i++) if(a[i]+add[br]<x) ans++;for(int i=bl+1;i<br;i++){int tmp=x-add[i];ans+=lower_bound(v[i].begin(),v[i].end(),tmp)-v[i].begin();}return ans;
}
int main(){n=read(); c=n/sqrt(n);for(int i=1;i<=n;i++){a[i]=read();b[i]=(i-1)/c+1;v[b[i]].push_back(a[i]);}for(int i=1;i<=b[n];i++) sort(v[i].begin(),v[i].end());for(int i=1;i<=n;i++){int op,l,r,x;op=read(); l=read(); r=read(); x=read();if(!op) modify(l,r,x);else printf("%d\n",query(l,r,x*x));}
}
样例三：区间修改+区间查询 小于 c的最大数(set二分)
和上一题类似，将vector换成set，利用set自动排序，同时每次设的最小值为（1<<31），注意不是（1<<32）这会溢出。
#define bol(x) ((x-1)*c+1)
const int maxn=1e5+7;
const int inf=(1<<31);
int n,a[maxn],c,b[maxn],add[1007];
set<int>v[1007];
//重构
void reset(int x){v[x].clear();for(int i=bol(x);i<=min(bol(x+1)-1,n);i++) v[x].insert(a[i]);
}
void modify(int l,int r,int x){int bl=b[l],br=b[r];if(bl==br){for(int i=l;i<=r;i++) a[i]+=x;reset(bl); return;}for(int i=l;i<bol(bl+1);i++) a[i]+=x;for(int i=bol(br);i<=r;i++) a[i]+=x;for(int i=bl+1;i<br;i++) add[i]+=x;reset(bl); reset(br);
}
int query(int l,int r,int x){int bl=b[l],br=b[r],ans=inf;if(bl==br){for(int i=l;i<=r;i++){int tl=a[i]+add[bl];if(tl<x&&tl>ans) ans=tl;}return (ans==inf)?-1:ans;}for(int i=l;i<bol(bl+1);i++) if(a[i]+add[bl]<x&&a[i]+add[bl]>ans)ans=a[i]+add[bl];for(int i=bol(br);i<=r;i++) if(a[i]+add[br]<x&&a[i]+add[br]>ans)ans=a[i]+add[br];for(int i=bl+1;i<br;i++){int tmp=x-add[i];set<int>::iterator it=v[i].lower_bound(tmp);if(it==v[i].begin()) continue;it--;ans=max(ans,*it+add[i]);}return (ans==inf)?-1:ans;
}
int main(){n=read(); c=n/sqrt(n);for(int i=1;i<=n;i++){a[i]=read();b[i]=(i-1)/c+1;v[b[i]].insert(a[i]);}for(int i=1;i<=n;i++){int op,l,r,x;op=read(); l=read(); r=read(); x=read();if(!op) modify(l,r,x);else printf("%d\n",query(l,r,x));}
}
样例四：区间修改+区间查询和
基础运用
#define bol(x) ((x-1)*c+1)
const int maxn=1e5+7;
ll n,a[maxn],c,b[maxn],add[1007],v[1007];
void modify(ll l,ll r,ll x){ll bl=b[l],br=b[r];if(bl==br){for(ll i=l;i<=r;i++) a[i]+=x,v[bl]+=x;return;}for(ll i=l;i<bol(bl+1);i++) a[i]+=x,v[bl]+=x;for(ll i=bol(br);i<=r;i++) a[i]+=x,v[br]+=x;for(ll i=bl+1;i<br;i++) add[i]+=x,v[i]+=x*c;
}
ll query(ll l,ll r,ll x){ll bl=b[l],br=b[r],ans=0;if(bl==br){for(ll i=l;i<=r;i++) ans=(ans+a[i]+add[bl])%(x+1);return ans;}for(ll i=l;i<bol(bl+1);i++) ans=(ans+a[i]+add[bl])%(x+1);for(ll i=bol(br);i<=r;i++) ans=(ans+a[i]+add[br])%(x+1);for(ll i=bl+1;i<br;i++) ans=(ans+v[i])%(x+1);return ans;
}
int main(){n=read(); c=sqrt(n);for(ll i=1;i<=n;i++){a[i]=read();b[i]=(i-1)/c+1;v[b[i]]+=a[i];}for(ll i=1;i<=n;i++){ll op,l,r,x;op=read(); l=read(); r=read(); x=read();if(!op) modify(l,r,x);else printf("%d\n",query(l,r,x));}
}
样例五：区间开方+区间查询和
一个int范围内的数，最多开5次方(向小取整)。那么就是说：一个块在几次操作后很容易全部变成1，这个时候再操作开方，就不用修改了。
这里定义一个判断数组 f [507], 为1时，表示该块全为1，当然没有变为0的时候只能暴力修改了， 复杂度不会太高。
#define bol(x) ((x-1)*c+1)
const int maxn=1e5+7;
ll n,a[maxn],c,b[maxn],f[1007],v[1007];
void modify(ll l,ll r){ll bl=b[l],br=b[r];if(bl==br){for(int i=l;i<=r;i++){v[bl]-=a[i];a[i]=(int)sqrt(a[i]);v[bl]+=0ll+a[i];}return;}for(int i=l;i<bol(bl+1);i++){v[bl]-=a[i];a[i]=(int)sqrt(a[i]);v[bl]+=0ll+a[i];}for(int i=bol(br);i<=r;i++){v[br]-=a[i];a[i]=(int)sqrt(a[i]);v[br]+=0ll+a[i];}for(int i=bl+1;i<br;i++){if(f[i]) continue; //该块全为1f[i]=1; v[i]=0;for(int j=bol(i);j<bol(i+1);j++){a[j]=(int)sqrt(a[j]);v[i]+=0ll+a[j];if(a[j]>1) f[i]=0;} }
}
ll query(ll l,ll r){ll bl=b[l],br=b[r],ans=0;if(bl==br){for(int i=l;i<=r;i++) ans+=a[i];return ans;}for(int i=l;i<bol(bl+1);i++) ans+=a[i];for(int i=bol(br);i<=r;i++) ans+=a[i];for(int i=bl+1;i<br;i++) ans+=v[i];return ans;
}
int main(){n=read(); c=sqrt(n);for(int i=1;i<=n;i++){a[i]=read();b[i]=(i-1)/c+1;v[b[i]]+=a[i];}for(int i=1;i<=n;i++){ll op,l,r,x;op=read(); l=read(); r=read(); x=read();if(!op) modify(l,r);else printf("%lld\n",query(l,r));}
}
样例六：动态插入+分块重构
这里注意每个块的个数开始不一定相同了，要了解当前点在第几块还得从头一个块枚举过去。
当一个块相当于其它块过于大时（可以设一个临界值），分块重构，重构需要的复杂度为O(n)，重构的次数为√n，所以重构的复杂度没有问题，而且保证了每个块的大小相对均衡。
#define bol(x) ((x-1)*c+1)
const int maxn=1e6+7;
int n,a[maxn],c,m;
vector<int>v[maxn];
typedef pair<int,int>p;
void rebuild(){int top=0;for(int i=1;i<=m;i++){for(int val:v[i]) a[++top]=val;v[i].clear();}c=sqrt(top); m=ceil(1.0*top/c);for(int i=1;i<=top;i++) v[(i-1)/c+1].push_back(a[i]);
}
p query(int x){for(int i=1;i<=m;i++){if(x>v[i].size()) x-=v[i].size();else return make_pair(i,x-1);}
}
void Insert(int i,int x){p t=query(i);v[t.first].insert(v[t.first].begin()+t.second,x); //插入元素 if(v[t.first].size()>10*c) rebuild(); //块过大时，重新分块
}
int main(){n=read(); c=sqrt(n); m=ceil(1.0*n/c);for(int i=1;i<=n;i++){a[i]=read();v[(i-1)/c+1].push_back(a[i]);}for(int i=1;i<=n;i++){int op,l,r,x;op=read(); l=read(); r=read(); x=read();if(!op) Insert(l,r);else{p t=query(r);printf("%d\n",v[t.first][t.second]);}}
}样例七：区间乘+加
和线段树的双标记类似，有优先级
若当前的一个块乘以m1后加上a1，这时进行一个乘m2的操作，则原来的标记变成m1 * m2，a1 * m2
若当前的一个块乘以m1后加上a1，这时进行一个加a2的操作，则原来的标记变成m1，a1+a2
#define bol(x) ((x-1)*c+1)
const int maxn=1e5+7;
const int mod=10007;
int n,a[maxn],c,m,p[maxn],q[maxn],b[maxn];
void reset(int x){for(int i=bol(x);i<=min(bol(x+1)-1,n);i++)a[i]=(a[i]*p[x]+q[x])%mod;p[x]=1; q[x]=0;
}
void add(int op,int l,int r,int x){int bl=b[l],br=b[r];if(bl==br){reset(bl);for(int i=l;i<=r;i++){if(op) a[i]=(a[i]*x)%mod;else a[i]=(a[i]+x)%mod;}return;}reset(bl); reset(br);for(int i=l;i<bol(bl+1);i++){if(op) a[i]=(a[i]*x)%mod;else a[i]=(a[i]+x)%mod;}for(int i=bol(br);i<=r;i++){if(op) a[i]=(a[i]*x)%mod;else a[i]=(a[i]+x)%mod;}for(int i=bl+1;i<br;i++){if(op){p[i]=(p[i]*x)%mod;q[i]=(q[i]*x)%mod;}else q[i]=(q[i]+x)%mod;}
}
int main(){n=read(); c=sqrt(n);for(int i=1;i<=n;i++){a[i]=read();b[i]=(i-1)/c+1;p[b[i]]=1; //乘操作记录 }for(int i=1;i<=n;i++){int op,l,r,x;op=read(); l=read(); r=read(); x=read();if(op<2) add(op,l,r,x); else{int sum=(a[r]*p[b[r]]+q[b[r]])%mod;printf("%d\n",sum);}}
}
样例八：区间修改为同一值查询区间元素=c的
和线段树区间修改为同一值类似，都要下推，涉及区间求和的都有pushdown，和线段树一模一样啊，不过分块偏暴力点。
#define bol(x) ((x-1)*c+1)
const int maxn=1e5+7;
const int mod=10007;
int n,a[maxn],c,m,b[maxn],f[maxn];
void pushdown(int x){if(f[x]!=-1){for(int i=bol(x);i<=min(bol(x+1)-1,n);i++) a[i]=f[x];f[x]=-1;}
}
int query(int l,int r,int x){int bl=b[l],br=b[r],ans=0;if(bl==br){pushdown(bl);for(int i=l;i<=r;i++){if(a[i]==x) ans++;a[i]=x;}return ans;}pushdown(bl); pushdown(br);for(int i=l;i<bol(bl+1);i++){if(a[i]==x) ans++;a[i]=x;}for(int i=bol(br);i<=r;i++){if(a[i]==x) ans++;a[i]=x;}for(int i=bl+1;i<br;i++){if(f[i]==x) ans+=c;else if(f[i]==-1){for(int j=bol(i);j<bol(i+1);j++){if(a[j]==x) ans++;a[j]=x;}}f[i]=x;}return ans;
}
int main(){n=read(); c=sqrt(n);for(int i=1;i<=n;i++){a[i]=read();b[i]=(i-1)/c+1;f[b[i]]=-1;}for(int i=1;i<=n;i++){int l,r,x;l=read(); r=read(); x=read();printf("%d\n",query(l,r,x));}
}
样例九：维护区间众数
用预处理ans[ i ] [ j ] ，来表示第 i 个块到第 j 个块的众数，方法有点暴力，用的枚举。
这题中如果你用map 或unordered_map的话，你设计的块的大小是sqrt(n)的话会超时，你可以设计块长，这样会过，有点玄学，当然你用数组离散化的话，可以不用设计块长。
#include <bits/stdc++.h>
#pragma GCC optimize (2)
#pragma G++ optimize (2)
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define debug(x) cout<<#x<<" :"<<x<<endl
using namespace std;
typedef long long ll;
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}
void out(ll x) {int stackk[40];if(x<0){putchar('-');x=-x;}if(!x){putchar('0');return;}int top=0;while(x) stackk[++top]=x%10,x/=10;while(top) putchar(stackk[top--]+'0');
}
#define bol(x) ((x-1)*c+1)
const int maxn=1e5+7;
int n,a[maxn],c,m,b[maxn],ans[2007][2007],tot,cnt[maxn];
vector<int>v[maxn];
unordered_map<int,int>mp,f;
void init(int id){memset(cnt,0,sizeof(cnt));int mx=0,res=0;for(int i=bol(id);i<=n;i++){int to=b[i];cnt[a[i]]++;if(cnt[a[i]]>mx||(cnt[a[i]]==mx&&mp[a[i]]<mp[res])){res=a[i];mx=cnt[a[i]];}ans[id][to]=res;}
}
int getsum(int l,int r,int x){ return upper_bound(v[x].begin(),v[x].end(),r)-lower_bound(v[x].begin(),v[x].end(),l); }
int query(int l,int r){int bl=b[l],br=b[r];int res=ans[bl+1][br-1];int mx=getsum(l,r,res);for(int i=l;i<=min(bl*c,r);i++){int tmp=getsum(l,r,a[i]);if(tmp>mx||(tmp==mx&&mp[a[i]]<mp[res])){res=a[i];mx=tmp;}}if(bl!=br){for(int i=bol(br);i<=r;i++){int tmp=getsum(l,r,a[i]);if(tmp>mx||(tmp==mx&&mp[a[i]]<mp[res])){res=a[i];mx=tmp;}}}return mp[res];
}
int main(){n=read(); c=sqrt(n);c=80;for(int i=1;i<=n;i++){a[i]=read();b[i]=(i-1)/c+1;if(!f[a[i]]){f[a[i]]=++tot;mp[tot]=a[i];}a[i]=f[a[i]];v[a[i]].push_back(i);}for(int i=1;i<=b[n];i++) init(i);for(int i=1;i<=n;i++){int l,r;l=read(); r=read();if(l>r) swap(l,r);printf("%d\n",query(l,r));}
}
更多推荐
分块入门（模板）
发布评论