洛谷博客欢迎来踩。
摘要
分块,是一种优雅的暴力,它通过对数列分段,完成对数列一些区间操作和区间查询的操作,是一种根号算法。
这篇学习笔记&题解是本萌新在学习分块过程中的一些感悟,希望能够帮助分块零基础的同学学会基础分块。
0 说明
本文中,以下变量有特定的含义:
:块的大小
:被分块的数列的大小(长度)
:第号块的左边界
:第号块的右边界
:块的数量
:第号元素所属的块
在写作时,由于本萌新的失误,只好提前在这里令与等价。
1 建块
1.1 建块需要完成的任务
在读入数据后,建块需要完成以下几个任务:
- 确定块的大小
- 确定块的数量
- 标记每个块的左右边界
- 标记每个元素所属的块
- 对每个块的数据进行初始化
1.2 确定块的大小
一般来说,我们习惯于令$$
但是由于毒瘤良心命题人泛滥,极其有可能被针对,在这种情况下,我们可以对块的大小适当作出一些调整,例如,,等。
一般这个工作只有一句话:
block=sqrt(n);
1.3 确定块的数量
在确定了块的大小后,块的数目就很容易确定了。
但是不一定是一个完全平方数,我们需要把最后几个无法凑足个元素的再单独分一个块。
代码如下:
tot=n/block; if(n%block) tot++;
1.4 标记每个块的左右边界
非常显然,
从而可以得出结论:$$$$
特别地,
代码:
for(int i=1;i<=tot;i++){ L[i]=(i-1)*block+1; R[i]=i*block; } R[tot]=n;
1.5 标记每个元素所属的块
根据1.4,我们很容易推出公式如下:
代码如下:
for(int i=1;i<=n;i++) belong[i]=(i-1)/block;
重要:在使用分块过程中,一定要小心和的书写错误不能出现重大审题性错误@朱卫红
1.6 对每个块的元素进行初始化
这项工作因题目不同而不同,如【教主的魔法】一题,就要对每个块的元素进行排序。
因为排序会对原始数列作出改变,所以在本题中,应当先把数列复制一遍再进行分块
2 分块题常见的操作
修改:
- 对数列内的每个数加上
- 对数列内的每个数减去
- etc.
查询:
- 求数列内的所有数的和
- 求数列内的数有多少大于/小于/大于等于/小于等于
- etc.
3 修改操作
考虑两种修改操作本质相同,第二种修改操作相当于第一种修改操作中。
3.1 暴力修改
考虑枚举区间之间所有数,直接对其实施修改,在修改的过程中维护每一个块的和/大小关系等。
但这不是我们考虑的东西
3.2 考虑线段树思想
线段树一个重要思想:
考虑应用在分块中。在修改操作中,如果是整块,就不维护每个的具体信息,而是在这个块的标记上加上。对于没有整块修改的部分(即块和的修改部分),暴力修改。
这样的话,第个数据的真正数据值
如果询问涉及到排序,块和需要全部重新备份和排序,对于块的块,数的相对大小不会改变,所以可以不重新排序。
特别地,需要特判的情况。
代码:
void change(){ if(belong[x]==belong[y]){ for(int i=x;i<=y;i++){ a[i]+=k; sum[belong[x]]+=k; } return; } for(int i=x;i<=R[belong[x]];i++){ a[i]+=k;sum[belong[x]]+=k; } for(int i=L[belong[y]];i<=y;i++){ a[i]+=k;sum[belong[y]]+=k; } for(int i=belong[x]+1;i<=belong[y]-1;i++){ lazy[i]+=k; sum[i]+=blo*k; } }
对以下这句代码作出特别解释:
sum[i]+=blo*k;
不用特判最后一块的原因是:如果操作区间覆盖到的最后一块,也一定是作为处理掉了,剩下来的块长一定是。
4 查询操作
4.1 查询元素和
对于块和,暴力枚举加和,注意加上其元素后还要加上
对于的块,直接即可。
同样的,需要特判
代码:
int query_sum(){ int ans=0; if(belong[x]==belong[y]){ for(int i=x;i<=y;i++){ ans+=a[i]+lazy[belong[x]]; } return ans; } for(int i=x;i<=R[belong[x]];i++){ ans+=a[i]+lazy[belong[x]]; } for(int i=L[belong[x]];i<=y;i++){ ans+=a[i]+lazy[belong[y]]; } for(int i=belong[x]+1;i<=belong[y]-1;i++){ ans+=sum[i]; } return ans; }
4.2 查询关系
与4.1类似,在块和,暴力枚举求答案;
对于[belong_x+1,belong_y-1]的块,因为其是有序的,进行二分找到端点位置,然后加加减减求出块中有多少符合要求的元素即可。
本处代码见5.
5 教主的魔法
在学习完分块后,我们可以发现,教主的魔法就是一道裸的分块题。
因此,完整代码如下:
#include<bits/stdc++.h> using namespace std; int a[1000007],d[1000007],L[1007],R[1007],belong[10000007],lazy[1007],ans; int n,q,block,tot,x,y,k; char cz; template <typename Tp> void read(Tp &x){ x=0;char ch=1;int fh; while(ch!='-'&&(ch>'9'||ch<'0')){ ch=getchar(); } if(ch=='-'){ fh=-1;ch=getchar(); }else fh=1; while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+ch-'0';ch=getchar(); } x*=fh; } void fr(char &x) { x=0;while(x!='M'&&x!='A') x=getchar(); } void build() { block=sqrt(n);tot=n/block; if(n%block) tot++; for(register int i=1;i<=n;i++){ belong[i]=(i-1)/block+1;d[i]=a[i]; } for(register int i=1;i<=tot;i++){ L[i]=(i-1)*block+1,R[i]=i*block; } R[tot]=n; for(register int i=1;i<=tot;i++){ sort(d+L[i],d+R[i]+1); } } void change() { if(belong[x]==belong[y]){ for(register int i=x;i<=y;i++){ a[i]+=k; } for(register int i=L[belong[x]];i<=R[belong[x]];i++){ d[i]=a[i]; } sort(d+L[belong[x]],d+R[belong[x]]+1); } else{ for(register int i=x;i<=R[belong[x]];i++){ a[i]+=k; } for(register int i=L[belong[x]];i<=R[belong[x]];i++){ d[i]=a[i]; } sort(d+L[belong[x]],d+R[belong[x]]+1); for(register int i=L[belong[y]];i<=y;i++){ a[i]+=k; } for(register int i=L[belong[y]];i<=R[belong[y]];i++){ d[i]=a[i]; } sort(d+L[belong[y]],d+R[belong[y]]+1); for(register int i=belong[x]+1;i<=belong[y]-1;i++){ lazy[i]+=k; } } } void query() { ans=0; if(belong[x]==belong[y]){ for(register int i=x;i<=y;i++){ if(lazy[belong[x]]+a[i]>=k) ans++; } printf("%d\n",ans); return; } else{ for(register int i=x;i<=R[belong[x]];i++){ if(lazy[belong[x]]+a[i]>=k) ans++; } for(register int i=L[belong[y]];i<=y;i++){ if(lazy[belong[y]]+a[i]>=k) ans++; } for(register int i=belong[x]+1;i<=belong[y]-1;i++){ int ll=L[i],rr=R[i],result=0,mid; while(ll<=rr) { mid=(ll+rr)>>1; if(d[mid]+lazy[i]>=k) rr=mid-1,result=R[i]-mid+1; else ll=mid+1; } ans+=result; } printf("%d\n",ans); } } int mian() { read(n);read(q); for(register int i=1;i<=n;i++) read(a[i]); build(); while(q--){ fr(cz); read(x);read(y);read(k); if(cz=='M'){ change(); } if(cz=='A'){ query(); } } return 0; }
6 附
因为本人是个萌新,文字未免有些疏漏,欢迎大佬指导。