听说学了这个算法 CSP 至少多考 100 分，来看一看。
我们先来看分块要维护哪些信息，然后借助例题来理解这个算法。
分块维护的信息（build）：
- 数列块长
blo：数列每块的长度，一般为 \lfloor \sqrt n\rfloor，建议在正式考试中这样写。如果在平常的练习中被卡常了可以尝试更换块长，如 \lfloor \sqrt n\rfloor+1、\lfloor \sqrt n\rfloor-1、\lceil \sqrt n\rceil 等。在代码中我们将其写作 blo=sqrt(n);。
- 数列块数
cnt：数列分的块的数量，为 \lceil\dfrac{n}{blo}\rceil。在代码中我们将其写作 cnt=(n+blo-1)/blo;。
- 每块起始点
L[i]：数列从左到右分的第 i 个块的起始点，为 (i-1)\times blo+1。在代码中我们将其写作 L[i]=(i-1)*blo+1;。
- 每块终止点
R[i]：数列从左到右分的第 i 个块的终止点，为 i\times blo。注意由于数列的终点为 n，所以 R_{cnt}=n。在代码中我们将其写作 R[i]=i*blo;，R[cnt]=n;。
```cpp
for(int i=1;i<=cnt;i++){
L[i]=(i-1)*blo+1;
R[i]=i*blo;
}
R[cnt]=n;
```
5. 数列每个位置的所属块 `bel[i]`：对于数列的每个位置，它属于这个数列的哪个块，为 $\dfrac{i-1}{blo}+1$。在代码中我们将其写作 `bel[i]=(i-1)/blo+1;`。
$1,2,3,4,5$ 五部分的代码合起来如下：
```cpp
void build(int n){
blo=sqrt(n);
cnt=(n+blo-1)/blo;
for(int i=1;i<=cnt;i++){
L[i]=(i-1)*blo+1;
R[i]=i*blo;
}
R[cnt]=n;
for(int i=1;i<=n;i++) bel[i]=(i-1)/blo+1;
}
```
另有一种写法为：
```cpp
void build(){
blo=sqrt(n);
cnt=(n+blo-1)/blo;
for(int i=1;i<=cnt;i++){
L[i]=(i-1)*blo+1;
R[i]=i*blo;
}
R[cnt]=n;
for(int i=1;i<=n;i++) bel[i]=(i-1)/blo+1;
}
```
另有一种写法为不单列为函数，直接写在主函数里，本人不推荐这种写法。
# 分块的区间操作（change）：
注：单点操作相当于 $x=y$ 的区间操作，在此我们对其不做讨论。
1. 区间加：将 $[x,y]$ 内的数加上 $k$。若此时 $x,y$ 同属一个块内，则直接暴力从 $x$ 加到 $y$，否则先暴力从 $x$ 加到 $R_{bel_x}$，再从 $L_{bel_y}$ 加到 $y$，以此来处理掉边界的不规整的范围，让需要处理的范围中只剩下若干个整块，显然此时我们不能一个一个数去加，这时我们回想起线段树中有一个很重要的优化叫做 lazytag 优化，我们在分块中同样使用这个优化，设 `lz[i]` 表示第 $i$ 个块被整个加的值，注意是整个加，这样在后续询问 $a_i$ 时 $a_i$ 就变成了 $a_i+lz_{bel_i}$，在修改 $a_i$ 只剩下若干个整块时也只需要将每个块的 $lz_i=lz_i+k$ 就行了。分块的 lazytag 可以永不下放，也可以在每次查询时只下放两侧的两块散的。
$1$ 部分的代码如下：
```cpp
void add(int x,int y,int k){
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++) a[i]+=k;
return;
}
for(int i=x;i<=R[bel[x]];i++) a[i]+=k;
for(int i=L[bel[y]];i<=y;i++) a[i]+=k;
for(int i=bel[x]+1;i<=bel[y]-1;i++) lz[i]+=k;
return;
}
```
2. 区间减：将 $[x,y]$ 内的数减去 $k$。同区间加。
3. 区间乘：将 $[x,y]$ 内的数乘上 $k$。同区间加。注意 $lz$ 数组的初始值要设为 $1$。
4. 区间除：将 $[x,y]$ 内的数除以 $k$。同区间加。一般数据是 double 类型的，因为 $a_i\div b\div c=a_i\div(b\times c)$，所以可以转化为区间乘。注意 $lz$ 数组的初始值要设为 $1$，同区间乘。
5. 区间异或：将 $[x,y]$ 内的数异或 $k$。同区间加。因为 $a_i\oplus b\oplus c=a_i\oplus (b\oplus c),x\oplus 0=x$，每次只需要把 $lz_i=lz_i\oplus k$ 即可。
6. 区间取反：将 $[x,y]$ 内的数取反。同区间加。一般是正数变成负数，负数变成正数，也有 $1$ 变成 $0$，$0$ 变成 $1$ 的，每次只需要把 $lz_i=-lz_i$ 或 $lz_i=!lz_i$ 即可，注意 $lz$ 数组的初始值要设为 $1$。
7. 区间覆盖：将 $[x,y]$ 内的数覆盖为 $k$。每次只需要把 $lz_i=k$ 即可。区间覆盖只在特定情况下能写，因为先覆盖 $a$ 再覆盖 $b$ 和先覆盖 $b$ 再覆盖 $a$ 的结果是不同的，也就是覆盖不满足交换律，但是单点覆盖很常见，而且特定情况的区间覆盖例题中有我就放了。
$7$ 部分的代码如下（很抱歉原来的代码是错的，这里我放上了 LOJ#6284 的区间覆盖代码，upd 是下放懒标记）：
```cpp
void cov(int x,int y,int k){
if(bel[x]==bel[y]){
upd(bel[x]);
for(int i=x;i<=y;i++) a[i]=k;
return;
}
upd(bel[x]);
for(int i=x;i<=R[bel[x]];i++) a[i]=k;
upd(bel[y]);
for(int i=L[bel[y]];i<=y;i++) a[i]=k;
for(int i=bel[x]+1;i<bel[y];i++){
if(lz[i]==-1) for(int j=L[i];j<=R[i];j++) a[j]=k;
lz[i]=k;
}
}
```
常见的这七种，后面会结合例题讲的。
# 分块的区间查询（query）：
注：单点查询相当于 $x=y$ 的区间查询，在此我们对其不做讨论。
1. 求区间和：求 $\sum_{i=x}^{y} a_i$。由前文可知此时查询时的 $a_i=a_i+lz_{bel_i}$，那么只需要在操作时维护 $b_i=\sum_{j=L_i}^{R_i} (a_j+lz_i)$，等价于 $b_i=(\sum_{j=L_i}^{R_i} a_j)+lz_i\times (R_i-L_i+1)$。最后若此时 $x,y$ 同属一个块内，则直接暴力从 $x$ 找到 $y$ 暴力加，否则先暴力从 $x$ 找到 $R_{bel_x}$ 暴力加，再从 $L_{bel_y}$ 找到 $y$ 暴力加，以此来处理掉边界的不规整的范围，让需要处理的范围中只剩下若干个整块，最后再加上每个整块的 $b_i$ 就是答案。
$1$ 部分的代码如下：
```cpp
int qsum(int x,int y,int k){
int ans=0;
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++) ans+=a[i]+lz[bel[x]];
return ans;
}
for(int i=x;i<=R[bel[x]];i++) ans+=a[i]+lz[bel[x]];
for(int i=L[bel[y]];i<=y;i++) ans+=a[i]+lz[bel[y]];
for(int i=bel[x]+1;i<=bel[y]-1;i++) ans+=b[i];
return ans;
}
```
2. 求区间 max：求 $\max_{i=x}^{y} a_i$。因为 $a\leq b$ 则 $a+x\leq b+x$，所以在操作时维护 $b_i=\max_{j=L_i}^{R_i} a_j$。最后若此时 $x,y$ 同属一个块内，则直接暴力从 $x$ 找到 $y$ 暴力取 max，否则先暴力从 $x$ 找到 $R_{bel_x}$ 暴力取 max，再从 $L_{bel_y}$ 找到 $y$ 暴力取 max，以此来处理掉边界的不规整的范围，让需要处理的范围中只剩下若干个整块，最后再与每个整块的 $b_i+lz_i$ 取 max 就是答案。
另有一种写法为维护 $b_i=(\max_{j=L_i}^{R_i} a_j)+lz_i$，最后再与每个整块的 $b_i$ 取 max 就是答案。
$2$ 部分的代码如下：
```cpp
int qmax(int x,int y,int k){
int ans=-1e18;
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++) ans=max(ans,a[i]+lz[bel[x]]);
return ans;
}
for(int i=x;i<=R[bel[x]];i++) ans=max(ans,a[i]+lz[bel[x]]);
for(int i=L[bel[y]];i<=y;i++) ans=max(ans,a[i]+lz[bel[y]]);
for(int i=bel[x]+1;i<=bel[y]-1;i++) ans=max(ans,b[i]+lz[i]);
return ans;
}
```
3. 求区间 min：求 $\min_{i=x}^{y} a_i$。同求区间 max。
4. 求区间 $<k$ 的数：求 $\sum_{i=x}^{y} [a_i<k]$。需要复制一个数组，然后在新数组把每个块进行一个从小到大的排序，然后若此时 $x,y$ 同属一个块内，则直接暴力从 $x$ 找到 $y$ 暴力在原数组查找合法值，否则先暴力从 $x$ 找到 $R_{bel_x}$ 暴力在原数组查找合法值，再从 $L_{bel_y}$ 找到 $y$ 暴力在原数组查找合法值，以此来处理掉边界的不规整的范围，让需要处理的范围中只剩下若干个整块，由于此时每个整块内元素有序，对于每个整块用二分在新数组来求得该块的合法 $<k$ 的数，可以用手写二分或 lower_bound 实现，我使用的是 lower_bound，在代码中我们将其写作 `ans+=(lower_bound(b+L[i],b+R[i]+1,k-lz[i])-b)-L[i];`，需要注意的是，这里也需要用到 lazytag。求 $\sum_{i=x}^{y} [a_i\leq k]$ 也是如此，把 lower_bound 换成 upper_bound 即可。
$4$ 部分的代码如下：
```cpp
void build(int n){
blo=sqrt(n);
cnt=(n+blo-1)/blo;
for(int i=1;i<=cnt;i++){
L[i]=(i-1)*blo+1;
R[i]=i*blo;
}
R[cnt]=n;
for(int i=1;i<=n;i++) bel[i]=(i-1)/blo+1;
for(int i=1;i<=n;i++) b[i]=a[i];
for(int i=1;i<=cnt;i++) sort(b+L[i],b+R[i]+1);
}
void add(int x,int y,int k){
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++) a[i]+=k;
for(int i=L[bel[x]];i<=R[bel[x]];i++) b[i]=a[i];
sort(b+L[bel[x]],b+R[bel[x]]+1);
return;
}
for(int i=x;i<=R[bel[x]];i++) a[i]+=k;
for(int i=L[bel[x]];i<=R[bel[x]];i++) b[i]=a[i];
sort(b+L[bel[x]],b+R[bel[x]]+1);
for(int i=L[bel[y]];i<=y;i++) a[i]+=k;
for(int i=L[bel[y]];i<=R[bel[y]];i++) b[i]=a[i];
sort(b+L[bel[y]],b+R[bel[y]]+1);
for(int i=bel[x]+1;i<=bel[y]-1;i++) lz[i]+=k;
}
int qsum(int x,int y,int k){
int ans=0;
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++) ans+=a[i]+lz[bel[x]]<k;
return ans;
}
for(int i=x;i<=R[bel[x]];i++) ans+=a[i]+lz[bel[x]]<k;
for(int i=L[bel[y]];i<=y;i++) ans+=a[i]+lz[bel[y]]<k;
for(int i=bel[x]+1;i<=bel[y]-1;i++) ans+=(lower_bound(b+L[i],b+R[i]+1,k-lz[i])-b)-L[i];
return ans;
}
```
5. 求区间 $>k$ 的数：求 $\sum_{i=x}^{y} [a_i> k]$。同求区间 $<k$ 的数。
6. 求区间 $=k$ 的数：求 $\sum_{i=x}^{y} [a_i=k]$。同求区间 $<k$ 的数。
7. 求区间 $\neq k$ 的数：求 $\sum_{i=x}^{y} [a_i\neq k]$。同求区间 $<k$ 的数。
常见的这七种，后面会结合例题讲的。
# 分块的时间复杂度：
由于我们把数列分成了 $\lfloor \sqrt n\rfloor$ 个块，极端情况下我们每次会把每个块都遍历一遍（也可以理解成遍历一个块内的所有元素），所以时间复杂度为 $O(n+q\sqrt n)$。如果是查询的 $4,5,6,7$ 操作，还需要一个排序，时间复杂度变为 $O(n+q\sqrt n\log n)$。略劣于线段树和主席树的 $O(n+q\log n)$。
# 分块九题：
1. 第一题：[LOJ#6277. 数列分块入门 1](https://loj.ac/p/6277)。操作 $1+$ 查询 $1$（单点）。
https://loj.ac/s/2178256
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=50001;
int n,cnt,q,op,x,y,k,a[N],L[N],R[N],bel[N],lz[N],blo;
void build(int n){
blo=sqrt(n);
cnt=(n+blo-1)/blo;
for(int i=1;i<=cnt;i++){
L[i]=(i-1)*blo+1;
R[i]=i*blo;
}
R[cnt]=n;
for(int i=1;i<=n;i++) bel[i]=(i-1)/blo+1;
}
void add(int x,int y,int k){
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++) a[i]+=k;
return;
}
for(int i=x;i<=R[bel[x]];i++) a[i]+=k;
for(int i=L[bel[y]];i<=y;i++) a[i]+=k;
for(int i=bel[x]+1;i<=bel[y]-1;i++) lz[i]+=k;
return;
}
int qsum(int x){
return a[x]+lz[bel[x]];
}
signed main(){
cin>>n;
q=n;
for(int i=1;i<=n;i++) cin>>a[i];
build(n);
while(q--){
cin>>op>>x>>y>>k;
if(!op) add(x,y,k);
else cout<<qsum(y)<<endl;
}
}
```
2. 第二题：[LOJ#6278. 数列分块入门 2](https://loj.ac/p/6278)。操作 $1+$ 查询 $4$。
https://loj.ac/s/2178348
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+1;
int n,cnt,q,x,y,k,a[N],b[N],L[N],R[N],bel[N],lz[N],blo,op;
void build(int n){
blo=sqrt(n);
cnt=(n+blo-1)/blo;
for(int i=1;i<=cnt;i++){
L[i]=(i-1)*blo+1;
R[i]=i*blo;
}
R[cnt]=n;
for(int i=1;i<=n;i++) bel[i]=(i-1)/blo+1;
for(int i=1;i<=n;i++) b[i]=a[i];
for(int i=1;i<=cnt;i++) sort(b+L[i],b+R[i]+1);
}
void add(int x,int y,int k){
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++) a[i]+=k;
for(int i=L[bel[x]];i<=R[bel[x]];i++) b[i]=a[i];
sort(b+L[bel[x]],b+R[bel[x]]+1);
return;
}
for(int i=x;i<=R[bel[x]];i++) a[i]+=k;
for(int i=L[bel[x]];i<=R[bel[x]];i++) b[i]=a[i];
sort(b+L[bel[x]],b+R[bel[x]]+1);
for(int i=L[bel[y]];i<=y;i++) a[i]+=k;
for(int i=L[bel[y]];i<=R[bel[y]];i++) b[i]=a[i];
sort(b+L[bel[y]],b+R[bel[y]]+1);
for(int i=bel[x]+1;i<=bel[y]-1;i++) lz[i]+=k;
}
int qsum(int x,int y,int k){
int ans=0;
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++) ans+=a[i]+lz[bel[x]]<k;
return ans;
}
for(int i=x;i<=R[bel[x]];i++) ans+=a[i]+lz[bel[x]]<k;
for(int i=L[bel[y]];i<=y;i++) ans+=a[i]+lz[bel[y]]<k;
for(int i=bel[x]+1;i<=bel[y]-1;i++) ans+=(lower_bound(b+L[i],b+R[i]+1,k-lz[i])-b)-L[i];
return ans;
}
signed main(){
cin>>n;
q=n;
for(int i=1;i<=n;i++) cin>>a[i];
build(n);
while(q--){
cin>>op>>x>>y>>k;
if(!op) add(x,y,k);
else cout<<qsum(x,y,k*k)<<endl;
}
}
```
3. 第三题：[LOJ#6279. 数列分块入门 3](https://loj.ac/p/6279)。操作 $1+$ 查询 $6$（微修）。
https://loj.ac/s/2178473
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+1;
int n,cnt,q,x,y,k,a[N],b[N],L[N],R[N],bel[N],lz[N],blo,op;
void build(int n){
blo=sqrt(n);
cnt=(n+blo-1)/blo;
for(int i=1;i<=cnt;i++){
L[i]=(i-1)*blo+1;
R[i]=i*blo;
}
R[cnt]=n;
for(int i=1;i<=n;i++) bel[i]=(i-1)/blo+1;
for(int i=1;i<=n;i++) b[i]=a[i];
for(int i=1;i<=cnt;i++) sort(b+L[i],b+R[i]+1);
}
void add(int x,int y,int k){
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++) a[i]+=k;
for(int i=L[bel[x]];i<=R[bel[x]];i++) b[i]=a[i];
sort(b+L[bel[x]],b+R[bel[x]]+1);
return;
}
for(int i=x;i<=R[bel[x]];i++) a[i]+=k;
for(int i=L[bel[x]];i<=R[bel[x]];i++) b[i]=a[i];
sort(b+L[bel[x]],b+R[bel[x]]+1);
for(int i=L[bel[y]];i<=y;i++) a[i]+=k;
for(int i=L[bel[y]];i<=R[bel[y]];i++) b[i]=a[i];
sort(b+L[bel[y]],b+R[bel[y]]+1);
for(int i=bel[x]+1;i<=bel[y]-1;i++) lz[i]+=k;
}
int qsum(int x,int y,int k){
int ans=-1e18;
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++) if(a[i]+lz[bel[x]]<k) ans=max(ans,a[i]+lz[bel[x]]);
if(ans!=-1e18) return ans;
else return -1;
}
for(int i=x;i<=R[bel[x]];i++) if(a[i]+lz[bel[x]]<k) ans=max(ans,a[i]+lz[bel[x]]);
for(int i=L[bel[y]];i<=y;i++) if(a[i]+lz[bel[y]]<k) ans=max(ans,a[i]+lz[bel[y]]);
for(int i=bel[x]+1;i<=bel[y]-1;i++){
if(lower_bound(b+L[i],b+R[i]+1,k-lz[i])-b-L[i]==0) continue;
ans=max(ans,b[lower_bound(b+L[i],b+R[i]+1,k-lz[i])-b-1]+lz[i]);
}
if(ans!=-1e18) return ans;
else return -1;
}
signed main(){
cin>>n;
q=n;
for(int i=1;i<=n;i++) cin>>a[i];
build(n);
while(q--){
cin>>op>>x>>y>>k;
if(!op) add(x,y,k);
else cout<<qsum(x,y,k)<<endl;
}
}
```
4. 第四题：[LOJ#6280. 数列分块入门 4](https://loj.ac/p/6280)。操作 $1+$ 查询 $1$。
https://loj.ac/s/2178527
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+1;
int n,cnt,q,op,x,y,k,a[N],b[N],L[N],R[N],bel[N],lz[N],blo;
void build(int n){
blo=sqrt(n);
cnt=(n+blo-1)/blo;
for(int i=1;i<=cnt;i++){
L[i]=(i-1)*blo+1;
R[i]=i*blo;
}
R[cnt]=n;
for(int i=1;i<=n;i++) bel[i]=(i-1)/blo+1;
for(int i=1;i<=n;i++) b[bel[i]]+=a[i];
}
void add(int x,int y,int k){
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++) a[i]+=k,b[bel[x]]+=k;
return;
}
for(int i=x;i<=R[bel[x]];i++) a[i]+=k,b[bel[x]]+=k;
for(int i=L[bel[y]];i<=y;i++) a[i]+=k,b[bel[y]]+=k;
for(int i=bel[x]+1;i<=bel[y]-1;i++) lz[i]+=k;
return;
}
int qsum(int x,int y,int c){
int ans=0;
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++) ans=(ans+a[i]+lz[bel[x]])%c;
return ans;
}
for(int i=x;i<=R[bel[x]];i++) ans=(ans+a[i]+lz[bel[x]])%c;
for(int i=L[bel[y]];i<=y;i++) ans=(ans+a[i]+lz[bel[y]])%c;
for(int i=bel[x]+1;i<=bel[y]-1;i++) ans=(ans+b[i]+lz[i]*(R[i]-L[i]+1))%c;
return ans;
}
signed main(){
cin>>n;
q=n;
for(int i=1;i<=n;i++) cin>>a[i];
build(n);
while(q--){
cin>>op>>x>>y>>k;
if(!op) add(x,y,k);
else cout<<qsum(x,y,k+1)<<endl;
}
}
```
5. 第五题：[LOJ#6281. 数列分块入门 5](https://loj.ac/p/6281)。区间开方 $+
$ 查询 $1$。
关于区间开放有一个经典的 trick：如果只有区间开方这一个操作，那么这个数列的每一个数开几次就会变成 $1$，而且次数非常少。由于 $\sqrt 1=1$，所以变成 $1$ 就不会被影响了。
我们给每个块开一个 set，用来维护该块中非 $1$ 的数的位置，每次若此时 $x,y$ 同属一个块内，则直接暴力从 $x$ 开到 $y$，否则先暴力从 $x$ 开到 $R_{bel_x}$，再从 $L_{bel_y}$ 开到 $y$，以此来处理掉边界的不规整的范围，让需要处理的范围中只剩下若干个整块，对于每个整块枚举对应块 set 内的位置，对该位置进行开方，若开方后该位置的数已经为 $1$，则删掉这个数的位置。
[UB](https://www.luogu.com.cn/paste/dca4b5oj)
https://loj.ac/s/2178527
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+1;
int n,cnt,q,op,x,y,k,a[N],b[N],L[N],R[N],bel[N],lz[N],blo;
set<int>st[N];
void build(int n){
blo=sqrt(n);
cnt=(n+blo-1)/blo;
for(int i=1;i<=cnt;i++){
L[i]=(i-1)*blo+1;
R[i]=i*blo;
}
R[cnt]=n;
for(int i=1;i<=n;i++) bel[i]=(i-1)/blo+1;
for(int i=1;i<=n;i++) if(a[i]!=1) st[bel[i]].insert(i);
}
void sqr(int x,int y){
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++) a[i]=sqrt(a[i]);
return;
}
for(int i=x;i<=R[bel[x]];i++) a[i]=sqrt(a[i]);
for(int i=L[bel[y]];i<=y;i++) a[i]=sqrt(a[i]);
for(int i=bel[x]+1;i<=bel[y]-1;i++){
auto it=st[i].begin();
while(it!=st[i].end()){
a[*it]=sqrt(a[*it]);
if(a[*it]==1) st[i].erase(it++);
else ++it;
}
}
return;
}
int qsum(int x,int y){
int ans=0;
if(bel[x]==bel[y]){
for(int i=x;i<=y;i++) ans+=a[i];
return ans;
}
for(int i=x;i<=R[bel[x]];i++) ans+=a[i];
for(int i=L[bel[y]];i<=y;i++) ans+=a[i];
for(int i=bel[x]+1;i<=bel[y]-1;i++){
for(auto j=st[i].begin();j!=st[i].end();j++) ans+=a[*j];
ans+=R[i]-L[i]+1-st[i].size();
}
return ans;
}
signed main(){
cin>>n;
q=n;
for(int i=1;i<=n;i++) cin>>a[i];
build(n);
while(q--){
cin>>op>>x>>y>>k;
if(!op) sqr(x,y);
else cout<<qsum(x,y)<<endl;
}
}
```
6. 第六题：[LOJ#6282. 数列分块入门 6](https://loj.ac/p/6282)。单点插入 $+
$ 查询 $1$（单点）。
https://loj.ac/s/2179022
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1;
int n,m,q,a[N],op,x,y,k;
vector<int>b;
void ins(int x,int k){
b.insert(b.begin()+x,k);
}
int qsum(int k){
return b[k];
}
int main(){
cin>>n;
q=n;
b.push_back(0);
for(int i=1;i<=n;i++) cin>>a[i],b.push_back(a[i]);
while(q--){
cin>>op>>x>>y>>k;
if(!op) ins(x,y);
else cout<<qsum(y)<<endl;
}
}
```
什么你问我分块在哪里，被省略了，因为这个单点询问根本用不上分块。
那我出个加强版吧，口胡一下：
6.5. 第六点五题：[LOJ#6282.5. 数列分块入门 6.5](https://www.bilibili.com/video/BV1GJ411x7h7)。单点插入 $+$ 查询 $1$。
注意这个是区间查询。
由于有了插入操作，我们不能再使用数组了，我们考虑使用 vector 来维护这个东西。
我们先在 vector 中 build 出数组有的一切东西（$b_i,L_i,R_i,bel_i$），然后每次插入将其 insert 到对应的位置（注意 vector 的 insert 是将其 insert 到某个位置前），然后更新每个块的 $b_i,L_i,R_i$ 以及每个位置的 $bel_i$，这些东西都可以在根号时间复杂度内完成。
代码略，毕竟只是口胡。
7. 第七题：[LOJ#6283. 数列分块入门 7](https://loj.ac/p/6283)。操作 $1,3+
$ 查询 $1$（单点）。
区间乘和区间加组合在一起的时候记住先乘后加，唯一不同的一点就是更新乘的 lazytag 时就是把加和乘的 lazytag 都乘上 k。
这里我写了个下放懒标记的版本。
https://loj.ac/s/2179168
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+1,p=10007;
int n,cnt,q,op,x,y,k,a[N],L[N],R[N],bel[N],lz1[N],lz2[N],blo;
void build(int n){
blo=sqrt(n);
cnt=(n+blo-1)/blo;
for(int i=1;i<=cnt;i++){
L[i]=(i-1)*blo+1;
R[i]=i*blo;
}
R[cnt]=n;
for(int i=1;i<=n;i++) bel[i]=(i-1)/blo+1;
for(int i=1;i<=n;i++) lz2[i]=1;
}
void upd(int x){
for(int i=L[x];i<=R[x];i++) a[i]=((a[i]*lz2[x]%p)+lz1[x])%p;
lz1[x]=0;
lz2[x]=1;
}
void add(int x,int y,int k){
if(bel[x]==bel[y]){
upd(bel[x]);
for(int i=x;i<=y;i++) a[i]=(a[i]+k)%p;
return;
}
upd(bel[x]);
for(int i=x;i<=R[bel[x]];i++) a[i]=(a[i]+k)%p;
upd(bel[y]);
for(int i=L[bel[y]];i<=y;i++) a[i]=(a[i]+k)%p;
for(int i=bel[x]+1;i<=bel[y]-1;i++) lz1[i]=(lz1[i]+k)%p;
return;
}
void mul(int x,int y,int k){
if(bel[x]==bel[y]){
upd(bel[x]);
for(int i=x;i<=y;i++) a[i]=(a[i]*k)%p;
return;
}
upd(bel[x]);
for(int i=x;i<=R[bel[x]];i++) a[i]=(a[i]*k)%p;
upd(bel[y]);
for(int i=L[bel[y]];i<=y;i++) a[i]=(a[i]*k)%p;
for(int i=bel[x]+1;i<=bel[y]-1;i++) lz2[i]=(lz2[i]*k)%p,lz1[i]=(lz1[i]*k)%p;
return;
}
int qsum(int x){
return ((a[x]*lz2[bel[x]]%p)+lz1[bel[x]])%p;
}
signed main(){
cin>>n;
q=n;
for(int i=1;i<=n;i++) cin>>a[i];
build(n);
while(q--){
cin>>op>>x>>y>>k;
if(!op) add(x,y,k);
else if(op==1) mul(x,y,k);
else cout<<qsum(y)<<endl;
}
}
```
8. 第八题：[LOJ#6284. 数列分块入门 8](https://loj.ac/p/6284)。操作 $7+
$ 查询 $6$。
https://loj.ac/s/2179325
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+1;
int n,cnt,q,x,y,k,a[N],bel[N],L[N],R[N],lz[N],blo;
void build(int n){
blo=sqrt(n);
cnt=(n+blo-1)/blo;
for(int i=1;i<=cnt;i++){
L[i]=(i-1)*blo+1;
R[i]=i*blo;
}
R[cnt]=n;
for(int i=1;i<=n;i++) bel[i]=(i-1)/blo+1;
memset(lz,-1,sizeof lz);
}
void upd(int x){
if(lz[x]==-1) return;
for(int i=L[x];i<=R[x];i++) a[i]=lz[x];
lz[x]=-1;
}
void cov(int x,int y,int k){
if(bel[x]==bel[y]){
upd(bel[x]);
for(int i=x;i<=y;i++) a[i]=k;
return;
}
upd(bel[x]);
for(int i=x;i<=R[bel[x]];i++) a[i]=k;
upd(bel[y]);
for(int i=L[bel[y]];i<=y;i++) a[i]=k;
for(int i=bel[x]+1;i<bel[y];i++){
if(lz[i]==-1) for(int j=L[i];j<=R[i];j++) a[j]=k;
lz[i]=k;
}
}
int qsum(int x,int y,int k){
int ans=0;
if(bel[x]==bel[y]){
upd(bel[x]);
for(int i=x;i<=y;i++) ans+=a[i]==k;
return ans;
}
upd(bel[x]);
for(int i=x;i<=R[bel[x]];i++) ans+=a[i]==k;
upd(bel[y]);
for(int i=L[bel[y]];i<=y;i++) ans+=a[i]==k;
for(int i=bel[x]+1;i<bel[y];i++){
if(lz[i]==-1) for(int j=L[i];j<=R[i];j++) ans+=a[j]==k;
ans+=blo*(lz[i]==k);
}
return ans;
}
signed main(){
cin>>n;
q=n;
for(int i=1;i<=n;i++) cin>>a[i];
build(n);
while(q--){
cin>>x>>y>>k;
cout<<qsum(x,y,k)<<endl;
cov(x,y,k);
}
}
```
9. 第九题：[LOJ#6285. 数列分块入门 9](https://loj.ac/p/6285)。区间最小众数问题。
感觉这题就是出题人没活整了要凑个九题搬过来的，放在 Ynoi 里不过分了。不过 LOJ 的数据范围很大，数据很强，这点很好，洛谷的数据范围纯消愁。
首先一个数可能是区间众数，必须要满足其中一项：
1. 是散块中的一个数。
2. 是整块的众数。
先把每块的 $2$ 预处理出来，这个不难吧。
然后我们建一个 `vector<int>C[N];`，记录每个数每个出现位置，最后 `upper_bound(C[k].begin(),C[k].end(),y)-lower_bound(C[k].begin(),C[k].end(),x);` 就是 $k$ 在 $[l,r]$ 出现的次数。
容易发现数组开不下，于是我们需要离散化。
[洛谷原题](https://www.luogu.com.cn/problem/P4168)
[如果你洛谷过了但是 LOJ TLE 92 / 96](https://www.luogu.com.cn/discuss/962281)
https://loj.ac/s/2179659
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int n,cnt,q,x,y,k,a[N],f[N],dp[1001][1001],c[N],bel[N],L[N],R[N],lz[N],blo;
vector<int>C[N];
unordered_map<int,int>d;
int count(int l,int r,int k){
return upper_bound(C[k].begin(),C[k].end(),y)-lower_bound(C[k].begin(),C[k].end(),x);
}
void build(int n){
blo=sqrt(n);
cnt=(n+blo-1)/blo;
for(int i=1;i<=cnt;i++){
L[i]=(i-1)*blo+1;
R[i]=i*blo;
}
R[cnt]=n;
for(int i=1;i<=n;i++) bel[i]=(i-1)/blo+1;
}
int qmax(int x,int y){
int ans=0,b=1e18,p;
if(bel[x]==bel[y]){
memset(c,0,sizeof c);
for(int i=x;i<=y;i++){
c[a[i]]++;
if(ans<c[a[i]]) ans=c[a[i]],b=a[i];
else if(ans==c[a[i]]) b=min(b,a[i]);
}
return b;
}
for(int i=x;i<=R[bel[x]];i++){
p=count(x,y,a[i]);
if(p>ans) ans=p,b=a[i];
else if(p==ans) b=min(b,a[i]);
}
for(int i=L[bel[y]];i<=y;i++){
p=count(x,y,a[i]);
if(p>ans) ans=p,b=a[i];
else if(p==ans) b=min(b,a[i]);
}
p=count(x,y,dp[bel[x]+1][bel[y]-1]);
if(p>ans) ans=p,b=dp[bel[x]+1][bel[y]-1];
else if(p==ans) b=min(b,dp[bel[x]+1][bel[y]-1]);
return b;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
q=n;
for(int i=1;i<=n;i++) cin>>a[i],f[i]=a[i];
build(n);
sort(f+1,f+1+n);
for(int i=1;i<=n;i++) d[f[i]]=i;
for(int i=1;i<=n;i++) a[i]=d[a[i]];
for(int i=1;i<=n;i++) C[a[i]].push_back(i);
for(int i=1;i<=cnt;i++){
memset(c,0,sizeof c);
int b=1e18,ans=0;
for(int j=i;j<=cnt;j++){
for(int k=L[j];k<=R[j];k++){
c[a[k]]++;
if(c[a[k]]>ans) ans=c[a[k]],b=a[k];
else if(c[a[k]]==ans) b=min(b,a[k]);
}
dp[i][j]=b;
}
}
while(q--){
cin>>x>>y;
cout<<f[qmax(x,y)]<<'\n';
}
}
```
# 分块九题的真实难度：
1. 黄，更简单的可以用树状数组替代。
2. 蓝。
3. 蓝。
4. 绿，更简单的可以用线段树替代。
5. 蓝。
6. 黄，更简单的可以用乱搞替代（6.5. 蓝）。
7. 绿，更简单的可以用线段树替代。
8. 蓝，可以用珂朵莉树平替。
9. 紫，[洛谷原题](https://www.luogu.com.cn/problem/P4168)。