分块
此文章列出了几种分块的常见用法涉及的模板题目和代码，便于理解和复习分块算法。
数列分块入门 1
【区间加法+单点查询】 题面
题目描述
给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，单点查值。
输入格式
第一行输入一个数字 n。
第二行输入 n 个数字，第 i 个数字为 a_i，以空格隔开。
接下来输入 n 行询问，每行输入四个数字 \mathrm{opt}、l、r、c，以空格隔开。
若 \mathrm{opt} = 0，表示将位于 [l, r] 的之间的数字都加 c。
若 \mathrm{opt} = 1，表示询问 a_r 的值（l 和 c 忽略）。
输出格式
对于每次询问，输出一行一个数字表示答案。
样例
输入
4
1 2 2 3
0 1 3 1
1 0 1 0
0 1 2 2
1 0 2 0
输出
2
5
数据范围与提示
对于 100\% 的数据，1 \leq n \leq 50000, -2^{31} \leq \mathrm{others}、\mathrm{ans} \leq 2^{31}-1。
代码
#include<bits/stdc++.h>
#define ll long long
#define mem(x) memset(x,0,sizeof(x))
using namespace std;
const int N=5e4+5;
ll n,a[N],id[N],lazy[N];
void build(){ //构建分块数组，id[x]可以代表当前块的编号
int len=sqrt(n);
for(int i=1;i<=n;i++){
id[i]=(i-1)/len+1;
}
}
void add(int l,int r,ll x){
int sid=id[l],eid=id[r]; //sid是左边要查询的端点，eid是右边要查询的端点
if(sid==eid){
for(int i=l;i<=r;i++){ //如果不足一个块，直接暴力累加
a[i]+=x;
}
return;
}
for(int i=l;id[i]==sid;i++){ //如果左边不足一个块，直接暴力累加
a[i]+=x;
}
for(int i=sid+1;i<eid;i++){ //lazy标记，暂时存储当前块的累加总和
lazy[i]+=x;
}
for(int i=r;id[i]==eid;i--){//如果右边不足一个块，直接暴力累加
a[i]+=x;
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build();
for(int i=1;i<=n;i++){
ll x,l,r,c;
cin>>x>>l>>r>>c;
if(x==1){
cout<<a[r]+lazy[id[r]]<<"\n"; //单点查询的时候加上曾经lazy的数值
}
else{
add(l,r,c);
}
}
return 0;
}
数列分块入门 2
【区间加法+查询小于x的个数】 题面
题目描述
给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的元素个数。
输入格式
第一行输入一个数字 n。
第二行输入 n 个数字，第 i 个数字为 a_i，以空格隔开。
接下来输入 n 行询问，每行输入四个数字 \mathrm{opt}、l、r、c，以空格隔开。
若 \mathrm{opt} = 0，表示将位于 [l, r] 的之间的数字都加 c。
若 \mathrm{opt} = 1，表示询问 [l, r] 中，小于 c^2 的数字的个数。
输出格式
对于每次询问，输出一行一个数字表示答案。
样例
输入
4
1 2 2 3
0 1 3 1
1 1 3 2
1 1 4 1
1 2 3 2
输出
3
0
2
数据范围与提示
对于 100\% 的数据，1 \leq n \leq 50000, -2^{31} \leq \mathrm{others}、\mathrm{ans} \leq 2^{31}-1。
代码
#include<bits/stdc++.h>
#define ll long long
#define mem(x) memset(x,0,sizeof(x))
using namespace std;
const int N=6e4+5;
ll n,a[N],id[N],lazy[N],s[N],L[N],R[N],t[N];
void Sort(ll x){ //排序x区块的数值
for(int i=L[x];i<=R[x];i++){
t[i]=a[i];
}
sort(t+L[x],t+R[x]+1);
}
void build(){ //构建分块数组，id[x]可以代表当前块的编号
int len=sqrt(n); //块的数量
int tot=n/len; //一共有多少块
if(n%len){
tot++;
}
for(int i=1;i<=n;i++){
id[i]=(i-1)/len+1;
}
for(int i=1;i<=tot;i++){ //记录每一块的起点和终点
L[i]=(i-1)*len+1; //L[i]是当前区间的最左端
R[i]=i*len; //R[i]是当前区间的最右端
}
R[tot]=n;
for(int i=1;i<=tot;i++){
Sort(i); //每一块都排序后放入t数组
}
}
void add(int l,int r,ll x){
int len=sqrt(n);
int sid=id[l],eid=id[r]; //sid是左边要查询的端点，eid是右边要查询的端点
if(sid==eid){
for(int i=l;i<=r;i++){ //如果不足一个块，直接暴力累加
a[i]+=x;
}
Sort(sid);
return;
}
for(int i=l;id[i]==sid;i++){ //如果左边不足一个块，直接暴力累加
a[i]+=x;
s[sid]+=x;
}
for(int i=sid+1;i<eid;i++){ //lazy标记，暂时存储当前块的累加总和
lazy[i]+=x;
s[i]+=len*x;
}
for(int i=r;id[i]==eid;i--){//如果右边不足一个块，直接暴力累加
a[i]+=x;
s[eid]+=x;
}
Sort(sid);
Sort(eid);
}
ll query(int l,int r,ll x){
int sid=id[l],eid=id[r];
ll ans=0;
if(sid==eid){
for(int i=l;i<=r;i++){
if(a[i]+lazy[sid]<x){
ans++;
}
}
return ans;
}
for(int i=l;id[i]<=sid;i++){
if(a[i]+lazy[sid]<x){
ans++;
}
}
for(int i=sid+1;i<eid;i++){
ans=ans+(lower_bound(t+L[i],t+R[i]+1,x-lazy[i])-t)-L[i];
}
for(int i=r;id[i]==eid;i--){
if(a[i]+lazy[eid]<x){
ans++;
}
}
return ans;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build();
for(int i=1;i<=n;i++){
ll x,l,r,c;
cin>>x>>l>>r>>c;
if(x==1){
cout<<query(l,r,c*c)<<"\n"; //单点查询的时候加上曾经lazy的数值
}
else{
add(l,r,c);
}
}
return 0;
}
数列分块入门 3
【区间加法+求小于目标值的最大值】 题面
题目描述
给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的前驱（比其小的最大元素）。
输入格式
第一行输入一个数字 n。
第二行输入 n 个数字，第 i 个数字为 a_i，以空格隔开。
接下来输入 n 行询问，每行输入四个数字 \mathrm{opt}、l、r、c，以空格隔开。
若 \mathrm{opt} = 0，表示将位于 [l, r] 的之间的数字都加 c。
若 \mathrm{opt} = 1，表示询问 [l, r] 中 c 的前驱的值（不存在则输出 -1）。
输出格式
对于每次询问，输出一行一个数字表示答案。
样例
输入
4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4
输出
3
-1
数据范围与提示
对于 100\% 的数据，1 \leq n \leq 100000， -2^{31} \leq \mathrm{others}、\mathrm{ans} \leq 2^{31}-1。
代码
#include<bits/stdc++.h>
#define ll long long
#define mem(x) memset(x,0,sizeof(x))
using namespace std;
const int N=1e5+5;
ll n,a[N],id[N],lazy[N],s[N],L[N],R[N],t[N];
void Sort(ll x){ //排序x区块的数值
for(int i=L[x];i<=R[x];i++){
t[i]=a[i];
}
sort(t+L[x],t+R[x]+1);
}
void build(){ //构建分块数组，id[x]可以代表当前块的编号
int len=sqrt(n); //块的数量
int tot=n/len; //一共有多少块
if(n%len){
tot++;
}
for(int i=1;i<=n;i++){
id[i]=(i-1)/len+1;
}
for(int i=1;i<=tot;i++){ //记录每一块的起点和终点
L[i]=(i-1)*len+1; //L[i]是当前区间的最左端
R[i]=i*len; //R[i]是当前区间的最右端
}
R[tot]=n;
for(int i=1;i<=tot;i++){
Sort(i); //块内搜索
}
}
void add(int l,int r,ll x){
int len=sqrt(n);
int sid=id[l],eid=id[r]; //sid是左边要查询的端点，eid是右边要查询的端点
if(sid==eid){
for(int i=l;i<=r;i++){ //如果不足一个块，直接暴力累加
a[i]+=x;
}
Sort(sid);
return;
}
for(int i=l;id[i]==sid;i++){ //如果左边不足一个块，直接暴力累加
a[i]+=x;
s[sid]+=x;
}
for(int i=sid+1;i<eid;i++){ //lazy标记，暂时存储当前块的累加总和
lazy[i]+=x;
s[i]+=len*x;
}
for(int i=r;id[i]==eid;i--){//如果右边不足一个块，直接暴力累加
a[i]+=x;
s[eid]+=x;
}
Sort(sid);
Sort(eid);
}
ll query(int l,int r,ll x){
int sid=id[l],eid=id[r];
ll ans=-1;
if(sid==eid){
for(int i=l;i<=r;i++){
if(a[i]+lazy[sid]<x){
ans=max(ans,a[i]+lazy[sid]);
}
}
return ans;
}
for(int i=l;id[i]==sid;i++){
if(a[i]+lazy[sid]<x){
ans=max(ans,a[i]+lazy[sid]);
}
}
for(int i=sid+1;i<eid;i++){
int pos = (lower_bound(t + L[i], t + R[i] + 1, x - lazy[i]) - t);
if (--pos < L[i])
continue;
ans = max(ans, t[pos] + lazy[i]);
}
for(int i=r;id[i]==eid;i--){
if(a[i]+lazy[eid]<x){
ans=max(ans,a[i]+lazy[eid]);
}
}
return ans;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build();
for(int i=1;i<=n;i++){
ll x,l,r,c;
cin>>x>>l>>r>>c;
if(x==1){
cout<<query(l,r,c)<<"\n"; //单点查询的时候加上曾经lazy的数值
}
else{
add(l,r,c);
}
}
return 0;
}
数列分块入门 4
【区间加法+区间求和】 题面
题目描述
给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，区间求和。
输入格式
第一行输入一个数字 n。
第二行输入 n 个数字，第 i 个数字为 a_i，以空格隔开。
接下来输入 n 行询问，每行输入四个数字 \mathrm{opt}、l、r、c，以空格隔开。
若 \mathrm{opt} = 0，表示将位于 [l, r] 的之间的数字都加 c。
若 \mathrm{opt} = 1，表示询问位于 [l, r] 的所有数字的和 \bmod (c+1)。
输出格式
对于每次询问，输出一行一个数字表示答案。
样例
输入
4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4
输出
1
4
数据范围与提示
对于 100\% 的数据，1 \leq n \leq 50000, -2^{31} \leq \mathrm{others}、\mathrm{ans} \leq 2^{31}-1。
代码
#include <bits/stdc++.h>
#define ll long long
#define mem(x) memset(x, 0, sizeof(x))
using namespace std;
const int N = 5e4 + 5;
ll n, a[N], id[N], lazy[N], s[N];
void build() { // 构建分块数组，id[x]表示当前块的编号
int len = sqrt(n);
for (int i = 1; i <= n; i++) {
id[i] = (i - 1) / len + 1;
s[id[i]] += a[i]; // s记录当前块的总和
}
}
void add(int l, int r, ll x) {
int len = sqrt(n);
int sid = id[l], eid = id[r]; // sid是左端点所在块，eid是右端点所在块
if (sid == eid) {
for (int i = l; i <= r; i++) { // 同一块内直接暴力累加
a[i] += x;
s[sid] += x;
}
return;
}
for (int i = l; id[i] == sid; i++) { // 左边部分暴力累加
a[i] += x;
s[sid] += x;
}
for (int i = sid + 1; i < eid; i++) { // 中间部分标记lazy累加
lazy[i] += x;
s[i] += len * x;
}
for (int i = r; id[i] == eid; i--) { // 右边部分暴力累加
a[i] += x;
s[eid] += x;
}
}
ll query(int l, int r, ll p) {
int sid = id[l], eid = id[r];
ll ans = 0;
if (sid == eid) {
for (int i = l; i <= r; i++) {
ans = (ans + a[i] + lazy[sid]) % p;
}
return ans;
}
for (int i = l; id[i] == sid; i++) {
ans = (ans + a[i] + lazy[sid]) % p;
}
for (int i = sid + 1; i < eid; i++) {
ans = (ans + s[i]) % p;
}
for (int i = r; id[i] == eid; i--) {
ans = (ans + a[i] + lazy[eid]) % p;
}
return ans;
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
build();
for (int i = 1; i <= n; i++) {
ll x, l, r, c;
cin >> x >> l >> r >> c;
if (x == 1) {
cout << query(l, r, c + 1) << "\n"; // 单点查询包含lazy值
} else {
add(l, r, c);
}
}
return 0;
}
