专栏文章

分享一套小清新分块题：带步长的分块操作

__Fireflies_
算法·理论参与者 2已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@mlmkp637
此快照首次捕获于
2026/02/15 01:11
4 天前
此快照最后确认于
2026/02/19 01:11
10 小时前
查看原文
防伪标识
本文作者为 Luogu 用户 uid=918478，仅在 Luogu 上发表，如果您在非原文处看见此文章且没有标明来源，说明您阅读的文章是侵权文章，请联系对应平台举报下架侵权者文章。

T1：P3870

题目链接

题目大意:

有一个 01 串，两种操作，第一种区间取反，第二种查询区间内 1 的个数。
n,m≤105n,m \le 10^5，维护 01 串分块套 bitset 即可做到 O(nnw)O(\frac{n\sqrt n}{w})。
具体为在每个整块内维护整体取反的懒标记和 01 的个数，修改时如果为整块则懒标记加一，否则下传懒标记并暴力修改。查询时对于整块，若标记为偶数，则答案累加块内 1 的个数，否则累加 0 的个数，对于散块，下传懒标记暴力计算即可。
代码比较简单不放了。
本题的线段树做法也比较显然，在这里不过多赘述。

T2：P12846

题目链接

题目大意；

有一个 01 串，四种操作，第一种区间隔空取反，步长二；第二种区间隔空取反，步长三；第三种区间取反；第四种查询区间内 1 的个数。
n≤5×105n \le 5 \times 10^5 且 m≤105m \le 10^5 使用分块套 bitset 可以做到 O(mnw)O(\frac{m\sqrt n}{w})。
具体来说，因为只有三种修改，步长分别为一二三，最小公倍数为六，所以分别维护块内所有模六余零，模六余一，模六余二，模六余三，模六余四，模六余五的位置上的 01 个数，维护六个懒标记：
  1. 从块内第一个元素开始，步长二。
  2. 从块内第二个元素开始，步长二。
  3. 从块内第一个元素开始，步长三。
  4. 从块内第二个元素开始，步长三。
  5. 从块内第三个元素开始，步长三。
  6. 整个块翻转。
那么块内模六余一的位置就受懒标记一三六的影响；模六余二的位置就受懒标记二四六的影响；模六余三的位置就受懒标记一五六的影响；模六余四的位置就受懒标记二三六的影响；模六余五的位置就受懒标记一四六的影响；模六余零的位置就受懒标记二五六的影响。
修改时整块添加对应懒标记，散块下传懒标记暴力改。
查询时对于整块，计算在模六意义下各个位置受相应懒标记影响的和，是偶数累加当前位置上 1 的个数，否则累加 0 的个数。散块下传标记暴力计数。
代码
本题不卡常，写的是比较粗糙的实现。
CPP
#include <bits/stdc++.h>
using namespace std;
//#define int ll
//#define ll long long
inline int read()
{
	int 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*10+ch-48;ch=getchar();}
	return x*f;
}
void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
int B=750;
int n,m;
int mqk=0,mqs=B;
struct fk{
	int l,r;
	int tag[5][5];
	int alltag;
	bitset<805>a;
	int da[15][5];
	void csh(){
		l=(mqk-1)*B+1;
		r=mqk*B;
		alltag=0;
		tag[1][2]=tag[2][2]=tag[1][3]=tag[2][3]=tag[3][3]=0;
	}
	void query(){
		da[1][0]=da[1][1]=0;
		da[2][0]=da[2][1]=0;
		da[3][0]=da[3][1]=0;
		da[4][0]=da[4][1]=0;
		da[5][0]=da[5][1]=0;
		da[6][0]=da[6][1]=0;
		for(int i=1;i<=B;i++){
			if(l+i-1>n) break;
			if(i%6==1) da[1][0]+=a[i];
			if(i%6==2) da[2][0]+=a[i];
			if(i%6==3) da[3][0]+=a[i];
			if(i%6==4) da[4][0]+=a[i];
			if(i%6==5) da[5][0]+=a[i];
			if(i%6==0) da[6][0]+=a[i];
			if(i%6==1) da[1][1]+=(a[i]^1);
			if(i%6==2) da[2][1]+=(a[i]^1);
			if(i%6==3) da[3][1]+=(a[i]^1);
			if(i%6==4) da[4][1]+=(a[i]^1);
			if(i%6==5) da[5][1]+=(a[i]^1);
			if(i%6==0) da[6][1]+=(a[i]^1);
		}
	}
	void qy(){
		alltag%=2;
		tag[1][2]%=2;
		tag[2][2]%=2;
		tag[1][3]%=2;
		tag[2][3]%=2;
		tag[3][3]%=2;
	}
	void ql(){
		alltag=tag[1][2]=tag[2][2]=tag[1][3]=tag[2][3]=tag[3][3]=0;
	}
}k[805];
#define pr pair<int,int>
#define mp make_pair
#define ft first
#define sd second
pr wz[500005];
signed main(){
	n=read();
	m=read();
	for(int i=1;i<=n;i++){
		mqs++;
		if(mqs==B+1){
			mqk++;
			k[mqk].csh();
			mqs=1;
		}
		int u=read();
		if(u==1) k[mqk].a.set(mqs);
		else k[mqk].a.reset(mqs);
		wz[i]=mp(mqk,mqs);
	}
	for(int i=1;i<=mqk;i++) k[i].query();
	while(m--){
		int op=read(),ml=read(),mr=read();
		if(op==1){
			pr u=wz[ml];
			for(int i=1;i<=mqk;i++){
				if(mr<k[i].l||ml>k[i].r) continue;
				else if(ml<=k[i].l&&mr>=k[i].r){
					if((k[i].l-ml+1)%2==1) k[i].tag[1][2]++;
					else k[i].tag[2][2]++;
				}
				else{
					k[i].qy(); 
					for(int j=1;j<=B;j++){
						if(k[i].alltag==1) k[i].a.flip(j);
						if(k[i].tag[1][2]==1&&(j%6==1||j%6==3||j%6==5)) k[i].a.flip(j);
						if(k[i].tag[2][2]==1&&(j%6==2||j%6==4||j%6==0)) k[i].a.flip(j);
						if(k[i].tag[1][3]==1&&(j%6==1||j%6==4)) k[i].a.flip(j);
						if(k[i].tag[2][3]==1&&(j%6==2||j%6==5)) k[i].a.flip(j);
						if(k[i].tag[3][3]==1&&(j%6==3||j%6==0)) k[i].a.flip(j);		
					}
					k[i].ql();
					k[i].query();
					if(u==wz[ml]){
						int ss=u.sd;
						for(int j=ss;j<=B;j+=2){
							if(ml<=j+k[i].l-1&&mr>=j+k[i].l-1){
								k[i].a.flip(j);
							    u.sd+=2;
							}	
						}
						if(u.sd==B||u.sd==B+2){
							u.ft++;
							u.sd=2;
						}
						else{
							u.ft++;
							u.sd=1;
						}
					}
					else{
						int ss=u.sd;
						for(int j=ss;j<=B;j+=2){
							if(ml<=j+k[i].l-1&&mr>=j+k[i].l-1){
								k[i].a.flip(j);
							    u.sd+=2;
							}	
						}
					}
					k[i].query();
				}
			}
		}
		if(op==2){
			pr u=wz[ml];
			for(int i=1;i<=mqk;i++){
				if(mr<k[i].l||ml>k[i].r) continue;
				else if(ml<=k[i].l&&mr>=k[i].r){
					if(u.sd==1){
						k[i].tag[1][3]++;
						u.ft++;
						u.sd=1;
					}
					else if(u.sd==2){
						k[i].tag[2][3]++;
						u.ft++;
						u.sd=2;
					}
					else{
						k[i].tag[3][3]++;
						u.ft++;
						u.sd=3; 
					}	
				}
				else{
					k[i].qy(); 
					for(int j=1;j<=B;j++){
						if(k[i].alltag==1) k[i].a.flip(j);
						if(k[i].tag[1][2]==1&&(j%6==1||j%6==3||j%6==5)) k[i].a.flip(j);
						if(k[i].tag[2][2]==1&&(j%6==2||j%6==4||j%6==0)) k[i].a.flip(j);
						if(k[i].tag[1][3]==1&&(j%6==1||j%6==4)) k[i].a.flip(j);
						if(k[i].tag[2][3]==1&&(j%6==2||j%6==5)) k[i].a.flip(j);
						if(k[i].tag[3][3]==1&&(j%6==3||j%6==0)) k[i].a.flip(j);		
					}
					k[i].ql();
					k[i].query();
					if(u==wz[ml]){
						int ss=u.sd;
						for(int j=ss;j<=B;j+=3){
							if(ml<=j+k[i].l-1&&mr>=j+k[i].l-1){
								k[i].a.flip(j);
							    u.sd+=3;
							}	
						}
						if(u.sd==B||u.sd==B+3){
							u.ft++;
							u.sd=3;
						}
						else if(u.sd==B-1||u.sd==B+2){
							u.ft++;
							u.sd=2;
						}
						else{
						    u.ft++;
						    u.sd=1;
						}
					}
					else{
						int ss=u.sd;
						for(int j=ss;j<=B;j+=3){
							if(ml<=j+k[i].l-1&&mr>=j+k[i].l-1){
								k[i].a.flip(j);
							    u.sd+=3;
							}	
						}
					}
					k[i].query();
				} 
			}
		}
		if(op==3){
			for(int i=1;i<=mqk;i++){
				if(ml>k[i].r||mr<k[i].l) continue;
				else if(ml<=k[i].l&&mr>=k[i].r){
					k[i].alltag++;
				}
				else{
					k[i].qy(); 
					for(int j=1;j<=B;j++){
						if(k[i].alltag==1) k[i].a.flip(j);
						if(k[i].tag[1][2]==1&&(j%6==1||j%6==3||j%6==5)) k[i].a.flip(j);
						if(k[i].tag[2][2]==1&&(j%6==2||j%6==4||j%6==0)) k[i].a.flip(j);
						if(k[i].tag[1][3]==1&&(j%6==1||j%6==4)) k[i].a.flip(j);
						if(k[i].tag[2][3]==1&&(j%6==2||j%6==5)) k[i].a.flip(j);
						if(k[i].tag[3][3]==1&&(j%6==3||j%6==0)) k[i].a.flip(j);		
					}
					k[i].ql();
					k[i].query();
					for(int j=1;j<=B;j++){
						if(ml<=j+k[i].l-1&&mr>=j+k[i].l-1){
						    k[i].a.flip(j);
						}	
					}
					k[i].query();
				}
			}
		} 
		if(op==4){
			int ans=0;
			for(int i=1;i<=mqk;i++){
				if(ml>k[i].r||mr<k[i].l) continue;
				else if(ml<=k[i].l&&mr>=k[i].r){
					int um1=k[i].alltag+k[i].tag[1][2]+k[i].tag[1][3];
					int um2=k[i].alltag+k[i].tag[2][2]+k[i].tag[2][3];
					int um3=k[i].alltag+k[i].tag[1][2]+k[i].tag[3][3];
					int um4=k[i].alltag+k[i].tag[1][3]+k[i].tag[2][2];
					int um5=k[i].alltag+k[i].tag[1][2]+k[i].tag[2][3];
					int um6=k[i].alltag+k[i].tag[2][2]+k[i].tag[3][3];
					um1%=2;
					um2%=2;
					um3%=2;
					um4%=2;
					um5%=2;
					um6%=2;
					ans+=k[i].da[1][um1];
					ans+=k[i].da[2][um2];
					ans+=k[i].da[3][um3];
					ans+=k[i].da[4][um4];
					ans+=k[i].da[5][um5];
					ans+=k[i].da[6][um6];
				}
				else{
					k[i].qy(); 
					for(int j=1;j<=B;j++){
						if(k[i].alltag==1) k[i].a.flip(j);
						if(k[i].tag[1][2]==1&&(j%6==1||j%6==3||j%6==5)) k[i].a.flip(j);
						if(k[i].tag[2][2]==1&&(j%6==2||j%6==4||j%6==0)) k[i].a.flip(j);
						if(k[i].tag[1][3]==1&&(j%6==1||j%6==4)) k[i].a.flip(j);
						if(k[i].tag[2][3]==1&&(j%6==2||j%6==5)) k[i].a.flip(j);
						if(k[i].tag[3][3]==1&&(j%6==3||j%6==0)) k[i].a.flip(j);		
					}
					k[i].ql();
					k[i].query();
					for(int j=1;j<=B;j++){
						if(ml<=j+k[i].l-1&&mr>=j+k[i].l-1){
						    ans+=k[i].a[j];
						}	
					}
				}
			}
			cout<<ans<<endl; 
		}
	} 
	return 0; 
}
本题也可以线段树维护，留给读者思考。

T3：P5309

题目链接

题目大意：

操作一区间隔空加，步长 xx，操作二查询区间和。
n,m≤2×105n,m \le 2 \times 10^5，500ms，分块加根号分治做到 mnm \sqrt n。
步长不确定，显然不能在用像 T2 一样在模最小公倍数意义下维护的方式了，也无法在用线段树维护了，发现步长 xx 较大时可以暴力加，这是简单的，那么难点就在步长较小的时候了。
每次修改的右端点确定，而且 y≤xy \le x 是一个很好的性质，对于 xx 和 yy 都相同的修改显然可以直接累加贡献。
因为 xx 已经确定较小，考虑固定 xx 维护每个 yy 的贡献，我们发现每次修改操作就相当于给序列以 xx 的块长进行了分块，每个整块内都包含了 yy，所以考虑对 yy 做前缀和后缀和做到快速查询，散块暴力就行。
对于询问，先遍历块计算一遍散块修改和初始元素以及 xx 较大时暴力修改造成的贡献，这里 O(n)O(\sqrt n)，再遍历 xx，利用记录的前缀和后缀和 O(1)O(1) 计算整块修改的贡献，因为 xx 被控制在 n\sqrt n 以下，所以总复杂度 O(mn)O(m \sqrt n)。
代码
由于是由乃题，所以略微需要卡常，需要采用比较精细的实现，特别注意一下取模。
CPP
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
inline  long long read()
{
	long long x=0,f=1;char ch=getchar_unlocked();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar_unlocked();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar_unlocked();}
	return x*f;
}
int B=500;
int G=120;
int n,m;
int wz[200005];
int mqk=0, mqs=B;
struct fk{
    int l,r;
    long long sum;
    long long a[505];
    void csh(){
        l=(mqk-1)*B+1;
        r=mqk*B;
        sum=0;
    }
}k[505];
long long sumr[1005][1005];
long long suml[1005][1005];
signed main() {
    n=read();
	m=read();
	for(int i=1;i<=n;i++){
		mqs++;
		if(mqs==B+1){
			mqk++;
			mqs=1;
			k[mqk].csh();
		}
		k[mqk].a[mqs]=read(); 
		k[mqk].sum+=k[mqk].a[mqs];
		k[mqk].sum%=MOD;
		wz[i]=mqk;
	}
    for(int u=1;u<=m;u++){
        int op=read();
        if(op==1){
            long long x=read(),y=read(),z=read(); 
            if(x>=G){
                for(int j=y;j<=n;j+=x){
					k[wz[j]].sum+=z;
					if(j%B==0) k[wz[j]].a[B]+=z;
					else k[wz[j]].a[j%B]+=z;
					if(j%B==0) k[wz[j]].a[B]%=MOD;
					else k[wz[j]].a[j%B]%=MOD;
				}
            }
			else{
                for(int i=y;i<=x;i++){sumr[x][i]+=z;sumr[x][i]%=MOD;} 
                for(int i=y;i>=1;i--){suml[x][i]+=z;suml[x][i]%=MOD;} 
            }
        } else {
            int l=read(),r=read();
            long long ans=0;
            int sl=wz[l],sr=wz[r];
            if(sl==sr){
                for(int i=1;i<=B;i++){
                    if(l<=k[sl].l+i-1&&r>=k[sl].l+i-1){
                        ans+=k[sl].a[i];
                        ans%=MOD;
                    }
                }
            }
			else{
                for(int i=1;i<=B;i++){
                    if(k[sl].l+i-1>=l){
                        ans+=k[sl].a[i];
                        ans%=MOD;
                    }
                    
                }
                for(int i=sl+1;i<=sr-1;i++){
                    ans+=k[i].sum;
                }
                ans%=MOD;
                for(int i=1;i<=B;i++){
                    if(k[sr].l+i-1<=r){
                        ans+=k[sr].a[i];
                        ans%=MOD;
                    }
                }
            }
            for(int i=1;i<G;i++){
            	if(!sumr[i][i]) continue;
                int kl=(l-1)/i+1,kr=(r-1)/i+1;
                int jsl=(l-1)%i+1,jsr=(r-1)%i+1; 
                if(kl==kr){
                    ans+=(sumr[i][jsr]-sumr[i][jsl-1]+MOD);
                    ans%=MOD;
                }
				else{
                    long long sl=(sumr[i][i]-sumr[i][jsl-1]+MOD);
                    long long sr=sumr[i][jsr];
                    ans+=(kr-kl-1)*sumr[i][i];
                    ans%=MOD;
                    ans+=(sl+sr);
                    ans%=MOD;
                }
            }
            cout<<ans%MOD<<"\n";
        }
    }
    return 0;
}

一点总结：

带步长的分块操作，当步长固定且较小时，可以求出他们的最小公倍数，在模最小公倍数的意义下为维护操作。步长不固定时，可以尝试对其进行根号分值，在非暴力的一侧套一些数据结构做到每个块 O(1)O(1) 或 O(log⁡n)O(\log n)，做到每次操作复杂度 O(n)O(\sqrt n) 或 O(nlog⁡n)O(\sqrt n \log n)。
感谢您的阅读，可以留下一个免费的赞吗？

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...