1. 介绍
? 分块的基本思想就是通过适当的划分, 预处理一部分信息并保存下来, 用空间换取时间. 总之就是一种 "优雅" 的暴力, 遵循 "大段维护, 局部朴素" 的思想.
2. 总结
划分区块
t 为区块个数, len 为区块长度, 一般为 n/t, 有时候根据复杂度调整.
- int t=sqrt(n);
- for(int i=1;i<=t;++i){
- L[i]=(i-1)*sqrt(n)+1;
- R[i]=i*sqrt(n);
- }
- if(R[t]<n) t++,L[t]=R[t-1]+1,R[t]=n;
pos[]标记
有时侯和预处理写在一起
- for(int i=1;i<=t;++i){
- for(int j=L[i];j<=R[i];++j){
- pos[j]=i;
- }
- }
查询
- int query(int l,int r){
- int p=pos[l],q=pos[r];
- if(p==q){
- //l,r 在一个块内, 一般局部朴素
- }
- else{
- //l,r 不在一个块内, 那就对 p+1~q-1 块维护, l~R[p],L[q]~r 段朴素处理
- }
- }
修改
有的题有修改操作, 就和处理查询一样.
3. 习题
一个简单的整数问题 2 https://www.acwing.com/problem/content/244/
这道题可以作为一道模板题. 理解分块的过程.
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int MA=1e5+5;
- int n,m,x,y,t;
- ll add[MA],sum[MA];
- int a[MA],pos[MA],L[MA],R[MA];
- ll d;
- void Change(int l,int r,ll val){
- int p=pos[l],q=pos[r];
- if(p==q){ //l,r 在一个块里面, 朴素修改
- for(int i=l;i<=r;++i) a[i]+=val;
- sum[p]+=val*(r-l+1);
- }
- else{
- for(int i=p+1;i<=q-1;++i) add[i]+=val; // 给 p+1 到 q-1 块打标记
- for(int i=l;i<=R[p];++i) a[i]+=val; // 处理最左端不满一块的区域
- sum[p]+=val*(R[p]-l+1);
- for(int i=L[q];i<=r;++i) a[i]+=val; // 处理最右端不满一块的区域
- sum[q]+=val*(r-L[q]+1);
- }
- }
- ll query(int l,int r){
- int p=pos[l],q=pos[r];
- ll ans=0;
- if(p==q){
- for(int i=l;i<=r;++i) ans+=a[i];
- ans+=add[p]*(r-l+1);
- }
- else{
- for(int i=p+1;i<=q-1;++i) ans+=sum[i]+add[i]*(R[i]-L[i]+1);
- for(int i=l;i<=R[p];++i) ans+=a[i];
- ans+=add[p]*(R[p]-l+1);
- for(int i=L[q];i<=r;++i) ans+=a[i];
- ans+=add[q]*(r-L[q]+1);
- }
- return ans;
- }
- int main()
- {
- // 输入
- memset(add,0,sizeof(add));
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;++i) scanf("%d",&a[i]);
- // 分块, 确定各个分块左右端点
- t=sqrt(n);
- for(int i=1;i<=t;++i){
- L[i]=(i-1)*sqrt(n)+1;
- R[i]=i*sqrt(n);
- }
- if(R[t]<n) t++,L[t]=R[t-1]+1,R[t]=n;
- for(int i=1;i<=t;++i){ // 预处理 sum[], pos[]
- for(int j=L[i];j<=R[i];++j){
- sum[i]+=a[j];
- pos[j]=i;
- }
- }
- // 指令处理
- while(m--){
- char op[5];
- scanf("%s",&op);
- if(op[0]=='C'){
- scanf("%d %d %lld",&x,&y,&d);
- Change(x,y,d);
- }
- else if(op[0]=='Q'){
- scanf("%d%d",&x,&y);
- printf("%lld\n",query(x,y));
- }
- }
- return 0;
- }
蒲公英 https://www.acwing.com/problem/content/251/
在线求区间众数
用 vector 保存每个数出现的位置, 在预处理时, 对处理区间每个数, 在对应存位置向量中二分查找区间边界 l 和 r 的下标位置, 作差就是这个值在区间中的出现次数. 然后用这个次数更新答案.
预处理任意 2 个块的答案, 为什么要预处理任意 2 区块之间的答案呢?, 这是由于区间众数不具有 "区间可加性", 为了减少复杂度, 所以要先预处理
- "大段维护, 小段朴素"
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int MA=4e4+5;
- int a[MA],b[MA],c[MA],pos[MA],L[MA],R[MA],f[805][805]; //c: 用来计数, pos: 标记所属块, L/R: 块边界, f: 任意区间答案
- vector<int> e[MA];
- int find(int x,int l,int r){ // 确定数字 x 在 l,r 区间中的个数
- return upper_bound(e[x].begin(),e[x].end(),r) - lower_bound(e[x].begin(),e[x].end(),l);
- }
- void work(int x,int l,int r,int &cnt,int &ans){
- int w=find(x,l,r); //w 记录 x 在 l,r 中的个数
- if(w>cnt||(w==cnt&&x<ans)){ // 更新答案
- cnt=w;
- ans=x;
- }
- }
- int query(int l,int r){
- int p=pos[l],q=pos[r];
- int ans=0,cnt=0;
- if(p==q){ //// 小段: 朴素查询 l,r 之间的每个值
- for(int i=l;i<=r;++i) work(a[i],l,r,cnt,ans);
- return b[ans];
- }
- int x=0,y=0;
- if(p+1<=q-1){
- x=p+1;
- y=q-1;
- }
- for(int i=l;i<=R[p];++i) work(a[i],l,r,cnt,ans);
- for(int i=L[q];i<=r;++i) work(a[i],l,r,cnt,ans);
- if(f[x][y]) work(f[x][y],l,r,cnt,ans);
- return b[ans];
- }
- int main()
- {
- int n,m;
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;++i) scanf("%d",&a[i]);
- memcpy(b,a,sizeof(b));
- sort(b+1,b+n+1);
- int tot=unique(b+1,b+n+1)-(b+1);
- for(int i=1;i<=n;++i){
- a[i]=lower_bound(b+1,b+tot+1,a[i]) - b;
- e[a[i]].push_back(i);
- }
- int t=sqrt(log(n)/log(2)*n);
- int len=t?n/t:n;
- for(int i=1;i<=t;++i){
- L[i]=(i-1)*len+1;
- R[i]=i*len;
- }
- if(R[t]<n) t++,L[t]=R[t-1]+1,R[t]=n;
- for(int i=1;i<=t;++i)
- for(int j=L[i];j<=R[i];++j)
- pos[j]=i;
- for(int i=1;i<=t;++i){
- memset(c,0,sizeof(c));
- int ans=0,cnt=0;
- for(int j=L[i];j<=n;++j){
- if(++c[a[j]]>cnt||(c[a[j]]==cnt&&a[j]<ans)){
- cnt=c[a[j]];
- ans=a[j];
- }
- f[i][pos[j]]=ans;
- }
- }
- int x=0;
- while(m--){
- int l,r;
- scanf("%d%d",&l,&r);
- l=(l+x-1)%n+1;
- r=(r+x-1)%n+1;
- if(l>r) swap(l,r);
- x=query(l,r);
- printf("%d\n",x);
- }
- return 0;
- }
磁力距
一开始没有头绪, 就想暴力算法,\(O(n^{2})\) 复杂度, 既然分块是优雅的暴力, 那应该可以利用分块降低复杂度.
将所有点按到 \((x0,y0)?\) 的距离的平方大小排序, 这一就将所有点由二维压缩到一维坐标上. 然后就可以将它们分块了.
分成 \(\sqrt n\) 块 , 每一块内部再按照质量大小排序, 这一步写在预处理里面.
我们用一个队列存到手的磁石 (感觉这类题, 一个点可以得到其他一些点的题用队列很方便模拟). 遍历所有分块, 如果这个分块最大的距离 dis[i] 大于当前处理的点 now 的磁力半径.(因为按距离从小到大排序) 那么之后的分块就都不用考虑, 只需要把当前分块处理一下, 就跳出. 否则, 将整个分块都处理一下.
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int MA=2e6+5;
- struct node
- {
- ll m,d,r,p;
- }a[MA];
- int pos[MA],L[MA],R[MA],vis[MA],l,r,n;
- ll dis[MA],x,y;
- queue<int> q;
- int x0,y_0;
- bool cmp_m(const node &a,const node &b) {return a.m<b.m;}
- bool cmp_d(const node &a,const node &b) {return a.d<b.d;}
- int main()
- {
- scanf("%d%d%lld%lld%d",&x0,&y_0,&a[0].p,&a[0].r,&n);
- a[0].r*=a[0].r;
- for(int i=1;i<=n;++i){
- scanf("%lld%lld%lld%lld%lld",&x,&y,&a[i].m,&a[i].p,&a[i].r);
- a[i].r*=a[i].r;
- a[i].d=(x0-x)*(x0-x)+(y_0-y)*(y_0-y);
- }
- sort(a+1,a+n+1,cmp_d);
- int t=sqrt(n);
- for(int i=1;i<=t;++i){
- L[i]=(i-1)*sqrt(n)+1;
- R[i]=i*sqrt(n);
- dis[i]=a[R[i]].d;
- sort(a+L[i],a+R[i]+1,cmp_m);
- }
- if(R[t]<n){
- t++,L[t]=R[t-1]+1,R[t]=n;
- dis[t]=a[R[t]].d;
- sort(a+L[t],a+R[t]+1,cmp_m);
- }
- q.push(0);
- vis[0]=1;
- int ans=0;
- while(q.size()){
- int now=q.front();
- q.pop();
- for(int i=1;i<=t;++i){
- if(dis[i]>a[now].r){
- for(int j=L[i];j<=R[i];++j){
- if(!vis[j] && a[j].m<=a[now].p && a[j].d<=a[now].r){
- q.push(j);
- //cout<<j<<endl;
- vis[j]=1;
- ans++;
- }
- }
- break;
- }
- while(L[i]<=R[i]&&a[L[i]].m<=a[now].p){
- if(!vis[L[i]]){
- q.push(L[i]);
- //cout<<L[i]<<endl;
- ans++;
- }
- ++L[i];
- }
- }
- }
- printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3398502.html