分享一套小清新分块题：带步长的分块操作
_Fireflies_
·
·
算法·理论
::::info[防伪标识]
本文作者为 Luogu 用户 uid=918478，仅在 Luogu 上发表，如果您在非原文处看见此文章且没有标明来源，说明您阅读的文章是侵权文章，请联系对应平台举报下架侵权者文章。
::::
T1：P3870
题目链接
题目大意:
有一个 01 串，两种操作，第一种区间取反，第二种查询区间内 1 的个数。
具体为在每个整块内维护整体取反的懒标记和 01 的个数，修改时如果为整块则懒标记加一，否则下传懒标记并暴力修改。查询时对于整块，若标记为偶数，则答案累加块内 1 的个数，否则累加 0 的个数，对于散块，下传懒标记暴力计算即可。
代码比较简单不放了。
本题的线段树做法也比较显然，在这里不过多赘述。
## T2：P12846
[题目链接](https://www.luogu.com.cn/problem/P12846)
### 题目大意；
有一个 01 串，四种操作，第一种区间隔空取反，步长二；第二种区间隔空取反，步长三；第三种区间取反；第四种查询区间内 1 的个数。
$n \le 5 \times 10^5$ 且 $m \le 10^5$ 使用分块套 bitset 可以做到 $O(\frac{m\sqrt n}{w})$。
具体来说，因为只有三种修改，步长分别为一二三，最小公倍数为六，所以分别维护块内所有模六余零，模六余一，模六余二，模六余三，模六余四，模六余五的位置上的 01 个数，维护六个懒标记：
1. 从块内第一个元素开始，步长二。
2. 从块内第二个元素开始，步长二。
3. 从块内第一个元素开始，步长三。
4. 从块内第二个元素开始，步长三。
5. 从块内第三个元素开始，步长三。
6. 整个块翻转。
那么块内模六余一的位置就受懒标记一三六的影响；模六余二的位置就受懒标记二四六的影响；模六余三的位置就受懒标记一五六的影响；模六余四的位置就受懒标记二三六的影响；模六余五的位置就受懒标记一四六的影响；模六余零的位置就受懒标记二五六的影响。
修改时整块添加对应懒标记，散块下传懒标记暴力改。
查询时对于整块，计算在模六意义下各个位置受相应懒标记影响的和，是偶数累加当前位置上 1 的个数，否则累加 0 的个数。散块下传标记暴力计数。
:::info[代码]
本题不卡常，写的是比较粗糙的实现。
```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
[题目链接](https://www.luogu.com.cn/problem/P5309)
### 题目大意：
操作一区间隔空加，步长 $x$，操作二查询区间和。
$n,m \le 2 \times 10^5$，500ms，分块加根号分治做到 $m \sqrt n$。
步长不确定，显然不能在用像 T2 一样在模最小公倍数意义下维护的方式了，也无法在用线段树维护了，发现步长 $x$ 较大时可以暴力加，这是简单的，那么难点就在步长较小的时候了。
每次修改的右端点确定，而且 $y \le x$ 是一个很好的性质，对于 $x$ 和 $y$ 都相同的修改显然可以直接累加贡献。
因为 $x$ 已经确定较小，考虑固定 $x$ 维护每个 $y$ 的贡献，我们发现每次修改操作就相当于给序列以 $x$ 的块长进行了分块，每个整块内都包含了 $y$，所以考虑对 $y$ 做前缀和后缀和做到快速查询，散块暴力就行。
对于询问，先遍历块计算一遍散块修改和初始元素以及 $x$ 较大时暴力修改造成的贡献，这里 $O(\sqrt n)$，再遍历 $x$，利用记录的前缀和后缀和 $O(1)$ 计算整块修改的贡献，因为 $x$ 被控制在 $\sqrt n$ 以下，所以总复杂度 $O(m \sqrt n)$。
::::info[代码]
由于是由乃题，所以略微需要卡常，需要采用比较精细的实现，特别注意一下取模。
```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(\log n)$，做到每次操作复杂度 $O(\sqrt n)$ 或 $O(\sqrt n \log n)$。
感谢您的阅读，可以留下一个免费的赞吗？