自动搬运

查看原文

来自洛谷，原作者为

	览遍千秋 将伤与泪汇成力化作拳

搬运于2025-08-24 21:41:46，当前版本为作者最后更新于2019-01-12 18:00:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

upd 2023-02-01 修改题解内容，使得其符合现行题解规范，并自己审核通过（）

upd 2025-02-05 重写完整代码，去掉 register 等无效内容，规范复用逻辑与 STL 函数，并自己审核通过。

---

摘要

分块，是一种优雅的暴力，它通过对数列分段，完成对数列一些区间操作和区间查询的操作，是一种根号算法。

这篇学习笔记&题解是本萌新在学习分块过程中的一些感悟，希望能够帮助分块零基础的同学学会基础分块。

---

0 说明

本文中，以下变量有特定的含义：

• $\operatorname{block}$：块的大小
• $n$：被分块的数列的大小（长度）
• $L_{x}$：第 $x$ 号块的左边界
• $R_{x}$：第 $x$ 号块的右边界
• $\operatorname{tot}$：块的数量
• $\operatorname{belong}_{x}$：第 $x$ 号元素所属的块

在写作时，由于本萌新的失误，只好提前在这里令 $[l,r]$ 与 $[x,y]$ 等价。

---

1 建块

1.1 建块需要完成的任务

在读入数据后，建块需要完成以下几个任务：

• 确定块的大小
• 确定块的数量
• 标记每个块的左右边界
• 标记每个元素所属的块
• 对每个块的数据进行初始化

1.2 确定块的大小

一般来说，我们习惯于令 $\operatorname{block}=\sqrt{n}$。

但是由于毒瘤良心命题人泛滥，$\operatorname{block}=\sqrt{n}$ 极其有可能被针对，在这种情况下，我们可以对块的大小适当作出一些调整，例如 $\sqrt{n}+1$，$\sqrt{n}-1$，$\sqrt{\frac{n}{\lg(n)}}$ 等。

一般这个工作只有一句话：

block = (int)sqrt((double)n);

1.3 确定块的数量

在确定了块的大小后，块的数目就很容易确定了。

但是 $n$ 不一定是一个完全平方数，我们需要把最后几个无法凑足 $\operatorname{block}$ 个元素的再单独分一个块。

代码如下：

tot = n / block;
if(n % block) tot++;

1.4 标记每个块的左右边界

非常显然，$L_1=1,R_1=\operatorname{block},L_2=\operatorname{block}+1,R_2=2×\operatorname{block},\cdots$

从而可以得出结论：

$$L_{x}=(x-1)\cdot\operatorname{block}+1,R_{x}=x\cdot \operatorname{block} $$

特别地，$R_{\operatorname{tot}}=n$

代码：

for(int i = 1; i <= tot; i++){
	L[i] = (i - 1) * block + 1;
    R[i] = i * block;
}
R[tot] = n;

1.5 标记每个元素所属的块

根据 1.4，我们很容易推出公式如下：

$$\operatorname{belong}_{x}=\frac{x-1}{\operatorname{block}}+1 $$

代码如下：

for(int i = 1; i <= n; i++)
	belong[i] = (i - 1) / block + 1;

重要：在使用分块过程中，一定要注意区分 $\operatorname{tot}$ 和 $n$。 $\operatorname{tot}$ 是块的总数，$n$ 是原来元素的总数。

1.6 对每个块的元素进行初始化

这项工作因题目不同而不同，如【教主的魔法】一题，就要对每个块的元素进行排序。

因为排序会对原始数列作出改变，所以在本题中，应当先把数列复制一遍再进行分块

---

2 分块题常见的操作

修改：

• 对数列 $[l,r]$ 内的每个数加上 $k$
• 对数列 $[l,r]$ 内的每个数减去 $k$
• etc.

查询：

• 求数列 $[l,r]$ 内的所有数的和
• 求数列 $[l,r]$ 内的数有多少大于/小于/大于等于/小于等于 $k$
• etc.

---

3 修改操作

考虑两种修改操作本质相同，第二种修改操作相当于第一种修改操作中 $k=-k'$。

3.1 暴力修改

考虑枚举区间 $[l,r]$ 之间所有数，直接对其实施修改，在修改的过程中维护每一个块的和/大小关系等。

但这不是我们考虑的东西

3.2 考虑线段树思想

线段树一个重要思想：lazytag

考虑应用在分块中。在修改操作中，如果是整块，就不维护每个的具体信息，而是在这个块的 $\operatorname{lazy}$ 标记上加上 $k$。对于没有整块修改的部分（即块 $\operatorname{belong}_x$ 和 $\operatorname{belong}_y$ 的修改部分），暴力修改。

这样的话，第 $i$ 个数据 $a_i$ 的真正数据值为 $a_i+\operatorname{lazy}_{\operatorname{belong}_{i}}$。

如果询问涉及到排序，块 $\operatorname{belong}_x$ 和 $\operatorname{belong}_y$ 需要全部重新备份和排序，对于块 $[\operatorname{belong}_x+1,\operatorname{belong}_y-1]$ 的块，数的相对大小不会改变，所以可以不重新排序。

特别地，需要特判 $\operatorname{belong}_x=\operatorname{belong}_y$ 的情况。

代码：

void change(){
	if(belong[x] == belong[y]){
		for(int i = x; i <= y; i++){
			a[i] += k;
			sum[belong[x]] += k;
		}
		return;
	}
	for(int i = x; i <= R[belong[x]]; i++){
		a[i] += k;sum[belong[x]] += k;
	}
	for(int i = L[belong[y]]; i <= y; i++){
		a[i] += k; sum[belong[y]] += k;
	}
	for(int i = belong[x] + 1; i <= belong[y] - 1; i++){
		lazy[i] += k;
		sum[i] += blo * k;
	}
}

对以下这句代码作出特别解释：

sum[i] += blo * k;

不用特判最后一块的原因是：如果操作区间覆盖到的最后一块，也一定是作为 $\operatorname{belong}_y$ 处理掉了，剩下来的块长一定是 $\operatorname{block}$。

---

4 查询操作

4.1 查询元素和

对于块 $\operatorname{belong}_x$ 和 $\operatorname{belong}_y$，暴力枚举加和，注意加上其元素后还要加上 $\operatorname{lazy}_{\operatorname{belong}_{i}}$

对于 $[\operatorname{belong}_x+1,\operatorname{belong}_y-1]$ 的块，直接 ans=ans+sum[i] 即可。

同样的，需要特判 $\operatorname{belong}_x=\operatorname{belong}_y$

代码：

int query_sum(){
	int ans = 0;
	if(belong[x] == belong[y]){
		for(int i = x; i <= y; i++){
			ans += a[i] + lazy[belong[x]];
		}
		return ans;
	}
	for(int i = x; i <= R[belong[x]]; i++){
		ans += a[i] + lazy[belong[x]];
	}
	for(int i = L[belong[x]]; i <= y; i++){
		ans += a[i] + lazy[belong[y]];
	}
	for(int i = belong[x] + 1; i <= belong[y] - 1; i++){
		ans += sum[i];
	}
	return ans;
}

4.2 查询关系

与4.1类似，在块 $\operatorname{belong}_x$ 和 $\operatorname{belong}_y$，暴力枚举求答案；

对于 $[\operatorname{belong}_x+1,\operatorname{belong}_y-1]$ 的块，因为其是有序的，进行二分找到端点位置，然后加加减减求出块中有多少符合要求的元素即可。

本处代码见5.

---

5 教主的魔法

在学习完分块后，我们可以发现，教主的魔法就是一道裸的分块题。

因此，完整代码如下：

#include<bits/stdc++.h>
using namespace std;

const int INT_SIZE = sizeof(int);
const int MAXN = 1000000 + 7;
const int MAXBLOCK = 1000 + 7;

int a[MAXN], d[MAXN], belong[MAXN];
int L[MAXBLOCK], R[MAXBLOCK], lazy[MAXBLOCK];
int n, q, block, tot, x, y, k;


void build() {
    block = (int)sqrt(n);
    tot = (n + block - 1) / block;
    for(int i = 1; i <= n; i++) {
        belong[i] = (i - 1) / block + 1;
    }
    for(int i = 1; i <= tot; i++) {
        L[i] = (i - 1) * block + 1;
        R[i] = min(i * block, n);
        sort(d + L[i], d + R[i] + 1);
    }
}

void modify_part(int bid, int st, int ed) {
    for(int i = st; i <= ed; i++) {
        a[i] += k;
    }
    int len = R[bid] - L[bid] + 1;
    memcpy(d + L[bid], a + L[bid], len * INT_SIZE);
    sort(d + L[bid], d + R[bid] + 1);
}

void modify() {
    if(belong[x] == belong[y]) {
        modify_part(belong[x], x, y);
        return;
    }

    modify_part(belong[x], x, R[belong[x]]);
    modify_part(belong[y], L[belong[y]], y);
    
    for(int i = belong[x] + 1; i < belong[y]; i++) {
        lazy[i] += k;
    }
}

int query_part(int bid, int st, int ed) {
    int ret = 0;
    for(int i = st; i <= ed; i++) {
        if(a[i] + lazy[bid] >= k) {
            ++ret;
        }
    }
    return ret;
}

int query() {
    if(belong[x] == belong[y]) {
        return query_part(belong[x], x, y);
    }

    int ansL = query_part(belong[x], x, R[belong[x]]);
    int ansR = query_part(belong[y], L[belong[y]], y);
    int ansM = 0;

    for(int i = belong[x] + 1; i < belong[y]; i++) {
        int pos = lower_bound(d + L[i], d + R[i] + 1, k - lazy[i]) - d;
        ansM += R[i] - pos + 1;
    }

    return ansL + ansR + ansM;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        d[i] = a[i];
    }
    build();
    while(q--){
        char op;
        cin >> op >> x >> y >> k;
        switch(op) {
            case 'M': {
                modify();
                break;
            }
            case 'A': {
                cout << query() << '\n';
                break;
            }
        }
    }
    return 0;
}

2024-02-05 更新前代码

6 附

因为本人是个萌新，文字未免有些疏漏，欢迎大佬指导。