分块:通过适当的划分,把数据分成一个一个的"块".
处理时,如果整个"块"都在操作范围内,直接对"块"进行操作,而如果只有"块"的一部分需要操作,则直接暴力处理.称之为"大段维护,局部朴素(暴力)"
如何分块影响到整道题目的时间效率.分块分得好,程序跑的飞快.分得不好,与暴力算法相差无几.如何分块能够使时间效率最低 是可以根据程序来计算的,蒟蒻数学太渣,不会算.所以大多数情况下通常是划分成(sqrt(n))块,时间效率往往是(nsqrt(n)),故还有人说它是神奇的(nsqrt(n))算法.
很多题目中,我们只是借助分块的思想,对数据划分成"块"后,便于处理.所以分块就像离散化一样,往往是一个预处理过程.比如莫队就是基于分块的预处理.
长度为n的序列,m次操作.操作有询问和修改两种.
询问:模x 等于y的下标上的权值 的总和.
修改:将下标x的权值修改为y.
本题可以美妙的暴力求解,但正解是分块.我们就来谈谈分块.
我们要求的答案实际上就是:
for(int i=y;i<=n;i+=x)
ans+=val[i];
但这样显然会超时,因为当模数x=1时,此算法就是(n^2)算法(实际上暴力就是卡在这一个点上),当模数x越小时,就越接近(n^2).(n一定时,模数x越大,循环次数就越少)
考虑如何优化?既然"当模数x越小时,就越接近(n^2)",为什么不预处理出模数很小的时候的答案呢,这个"小"是如何界定的呢?不如就以(sqrt(n))为分界值吧(好随意).
当模数在(1)~(sqrt(n))范围内时,直接用一个f的二维数组记录答案.(f[x][y])表示模x时等于y的下标上的权值的总和.就像这样:
for(int i=1;i<=n;i++)
for(int j=1;j<=sqrt(n);j++)
f[j][i%j]+=val[i];
于是我们通过美妙的(nsqrt(n))预处理出了当模数x小于等于(nsqrt(n))时的答案,则当模数x大于(nsqrt(n))时,就直接像最上面那样暴力求解即可.
再来考虑修改操作,修改时我们只要维护当模数x小于等于(nsqrt(n))时的答案即可.
for(int i=1;i<=unit;i++){
f[i][x%i]+=y-val[x];
}
val[x]=y;
鉴于上面分析得这么详细,把下面代码的核心全都挖出来讲了,所以就不注释代码了.
int n,m,unit;
int val[150005],f[2005][2005];
int main(){
n=read();m=read();
unit=sqrt(n);
for(int i=1;i<=n;i++){
val[i]=read();
for(int j=1;j<=unit;j++){
f[j][i%j]+=val[i];
}
}
while(m--){
char op;cin>>op;
int x=read(),y=read();
if(op=='C'){
for(int i=1;i<=unit;i++){
f[i][x%i]+=y-val[x];
}
val[x]=y;
}
else{
if(x<=unit){
printf("%d
",f[x][y]);
continue;
}
else{
int ans=0;
for(int i=y;i<=n;i+=x){
ans+=val[i];
}
printf("%d
",ans);
}
}
}
return 0;
}
长度为n的序列,Q次操作.
修改:把序列([l,r])之间的每个数加上(val);
询问:查询序列([l,r])之间大于等于(val)的数的个数.
此题极像线段树的板子题,但仔细想想,线段树统计区间范围内大于等于(val)的数的个数很吃力,那就还是考虑分块.
int n,Q,unit;
int a[1000005],c[1000005];
struct kuai{
int l,r,add;
}b[10005];
//结构体记录每一个"块"的左右端点位置和增加标记add
//这个add就相当于的线段树区间修改中的延迟标记
void change(int l,int r,int val){
for(int i=1;i<=unit;i++){
if(l<=b[i].l&&r>=b[i].r)
b[i].add+=val;
//当这一"块"全都位于修改范围内时,add标记
else if(l<=b[i].l&&r<=b[i].r){
for(int j=b[i].l;j<=b[i].r;j++){
c[j]=a[j]+b[i].add;
if(j>=b[i].l&&j<=r)
c[j]+=val;
}
sort(c+b[i].l,c+b[i].r+1);
}
else if(l>=b[i].l&&r>=b[i].r){
for(int j=b[i].l;j<=b[i].r;j++){
c[j]=a[j]+b[i].add;
if(j>=l&&j<=b[i].r)
c[j]+=val;
}
sort(c+b[i].l,c+b[i].r+1);
}
//当这一"块"只有部分在修改范围内时,直接暴力地处理
//每处理完一个"块",仍要保证"块"内的单调性
}
}
int erfen(int num,int val){
if(c[b[num].l]+b[num].add>=val)
return b[num].r-b[num].l+1;
//这一"块"最小的值都大于等于val
//则整个"块"都会对答案产生贡献
else if(c[b[num].r]+b[num].add<val)
return 0;
//这一"块"最大的值都小于val,则全都不会产生贡献.
else{
int l=b[num].l,r=b[num].r,mid,ans;
while(l<=r){
mid=(l+r)>>1;
if(c[mid]+b[num].add>=val){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
return b[num].r-ans+1;
}
//其余情况都要二分查找
}
void query(int l,int r,int val){
int ans=0;
for(int i=1;i<=unit;i++){
if(l<=b[i].l&&r>=b[i].r)
ans+=erfen(i,val);
//当这一"块"全都位于查询范围内时,对整个"块"二分查找
else if(l<=b[i].l&&r<=b[i].r){
for(int j=b[i].l;j<=r;j++)
if((c[j]+b[i].add)>=val)
ans++;
}
else if(l>=b[i].l&&r>=b[i].r){
for(int j=l;j<=b[i].r;j++)
if((c[j]+b[i].add)>=val)
ans++;
}
//当这一"块"只有部分在查询范围内时,直接暴力地处理
}
printf("%d
",ans);
}
int main(){
n=read();Q=read();
unit=sqrt(n);
for(int i=1;i<=n;i++){
a[i]=read();
c[i]=a[i];
}
for(int i=1;i<=unit;i++){
b[i].l=(i-1)*unit+1;
b[i].r=i*unit;
}
if(b[unit].r!=n){
unit++;
b[unit].l=b[unit-1].r+1;
b[unit].r=n;
}
//这个for和if是在预处理每一"块"的左右端点的位置
for(int i=1;i<=unit;i++)
sort(c+b[i].l,c+b[i].r+1);
//为了快速查询,维护每一块内的数值单调递增
while(Q--){
char op;cin>>op;
int l=read(),r=read(),val=read();
if(op=='M'){change(l,r,val);}
else{query(l,r,val);}
}
return 0;
}