入门分块 1-9 笔记 - MituFun's Blog

2522 字

13 分钟

入门分块 1-9 笔记

2022-04-09

竞赛

算法

此为本人于 2022-04-09 初次发表在洛谷的内容，迁移至此。阅读原文（好像现在洛谷博客限制站外访问了）

分块 1#

题目链接

操作涉及区间加法，单点查值。

这个还算比较板子的。

零散块暴力，整块加上一个 $\text{tag}$ ，但是貌似这道题里面块的值并不重要。

最后答案就是 $a_x+b[bel_x].tag$

代码实现

分块 2#

题目链接

操作涉及区间加法，询问区间内小于某个值 $x$ 的元素个数。

很板子，但是调了 2 天才调出来，是整块处理的时候出错了。

题目要求我们计算小于 $c^2$ 的数的数量，如果我们直接进行暴力从块的开始到末尾扫一遍的话，这样会很容易被卡成 $\mathcal{O}(n^2)$ 的，所以我们考虑二分。

很显然，给出的序列未必是单调的。因此，我们每个块内都要单独储存这个块内数值的信息，然后进行排序。初始化的时候也要进行排序。

对于整块而言，修改后没有必要进行排序，因为是整个块内的值都增加 $c$ ，所以块内的值互相的大小关系没有变化，所以不需要更新。

对于零散块而言，暴力即可。对于整块而言，可以直接二分。

之所以我调了两天，就是因为处理整块的时候，第 $i$ 个块被我认为成了是第 $i$ 个元素，然后在进行查询块内的值的时候加上了一个 $bel_i$ ，导致错误。

简化思路就是：块内排序，查询时二分，零散块暴力。

代码实现

类似的题可以去写 P2801 教主的魔法，LOJ 这道题数据过弱，甚至纯暴力都能过。

分块 3#

题目链接

操作涉及区间加法，询问区间内小于某个值 $x$ 的前驱（比其小的最大元素）。

我们看到比某一个数更小的最大数，很容易想到二分。整块排序，然后再用 lower_bound 找到块内第一个比 $x$ 大的值，然后将下标 $-1$ 就是这个块内 $x$ 的前驱。注意这里如果 lower_bound 找到的下标为 $0$ ，则表示这个块里面没有比 $x$ 更小的数了，continue 掉这个块即可。

然后对于零散块，暴力找到比 $x$ 小的最大值，最后判一下答案合不合法即可。

简化思路就是：块内排序，查询时二分找下标，零散块暴力。

代码实现

分块 4#

题目链接

操作涉及区间加法，区间求和。

我觉得这是除了分块 1 以外最简单的一道了，但是还是调了一段时间（主要是忘记初始化块了）。

然后对于这道题而言，每个块存储一个 $\text{val}$ 表示这个块内之和，然后加上一个懒惰标记 $\text{tag}$ 。注意，这里的 $\text{tag}$ 是表示块内单个值的懒惰标记，而不是整个块。

那么对于零散块而言，可以直接暴力求和，第 $i$ 个数的值就是 $a_i+b[\text{bel}_i].\text{tag}$ 。然后整块的话，就是块的值再加上懒惰标记乘上块长。

然后，其实这道题的代码也可以通过分块 1。因为对于单独一个数 $x$ ，可以看成是区间 $[x,x]$ 内的和。

代码实现

分块 5#

题目链接

操作涉及区间开方，区间求和。

这道题有点思维难度。首先，你会发现一个很严重的问题： $\sqrt{a}+\sqrt{b}\ne \sqrt{a+b}$ ，不能直接用懒惰标记了。

我们很容易发现，对于一个数不断开方，会十分迅速地退化为 $0$ 或 $1$ 。而且 $0$ 和 $1$ 开方都是等于他本身，再对他们进行操作就是浪费时间。

因此，我们块内需要额外储存一个当前块内最大值。只有在当前块内最大值大于 $1$ 的时候再执行操作，否则不用管即可。注意每次操作完成后都要更新最大值。

然后洛谷 P4145 上帝造题的七分钟 2 / 花神游历各国和这道题一样，可以作为练习。

代码实现

分块 6#

题目链接

操作涉及单点插入，单点询问，数据随机生成。

这道题我本来想用 vector 暴力做法当做对拍使得，想交一下测一下正确性，结果不小心过了。代码实现

分块以后写，还不会（

补题啦补题啦！——2026.10.8 我去这多少年了

这题貌似网上大部分的做法都是要考虑周期性重构。但实际上，由于数据生成是随机的，故插入的数据会均匀分布在每一块当中。并不会出现某一个块巨大导致被卡掉。反而如果这道题采用了重构，其花费的时间反而会更多。

这题的 query 和 insert 确实有些不同。

insert#

考虑到每次是单次插入，朴素地想法是目标坐标不断减去当前块长，当剩余坐标小于0时，则表明就应当插入于此块之中。

当然，与此同时，需要更新当前块的左右端点和长度，以及后续块因为前面插入了一个数导致左右端点的向右偏移。

很明显，此为 $O(\sqrt n)$ 的做法。但是常数较大。

为了优化，我们可以发现，有一部分时间运用于了查找当前应当插入于哪一块中。不妨可以尝试设计 bel[i] 数组储存 $i$ 位置被哪一个块包含。

对于可行性，可以发现，对于后续的块，每次只需要更新块端点的 bel 即可。

query#

由于我们在 insert 中维护了 bel 故我们甚至可以 $O(1)$ 查询。

具体看代码：

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
using namespace std;

#define int long long

const int maxn = 1e5 + 10;
int n;
int a[maxn];

int siz, bel[maxn * 2];
struct block {
	int l, r;
	vector<int> vals;
} b[maxn];

void build() {
	siz = sqrt(n);
	for (int i = 1; i <= siz; i++) {
		b[i].l = b[i - 1].r + 1;
		b[i].r = b[i].l + siz - 1;
	}
	b[siz].r = n;
	for (int i = 1; i <= siz; i++) {
		b[i].vals.push_back(-1);
		for (int j = b[i].l; j <= b[i].r; j++) {
			b[i].vals.push_back(a[j]);
			bel[j] = i;
		}
	}
}

void insert(int x, int v) {
	int bx = bel[x];
	int pos = x - b[bx].l + 1;
	b[bx].vals.insert(b[bx].vals.begin() + pos, v);
	b[bx].r++;
	bel[b[bx].r] = bx;
	for (int j = bx + 1; j <= siz; j++) {
		b[j].l++, b[j].r++;
		bel[b[j].l] = j, bel[b[j].r] = j;
	}
}

int query(int x) {
	return b[bel[x]].vals[x - b[bel[x]].l + 1];
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	build();
	for (int i = 1; i <= n; i++) {
		int op, l, r, c;
		cin >> op >> l >> r >> c;
		if (op == 0) {
			insert(l, r);
		} else {
			cout << query(r) << endl;
		}
	}
	return 0;
}

分块 7#

题目链接

操作涉及区间乘法，区间加法，单点询问。

首先，我们发现查询操作很简单，不需要进行过多的考虑，但是修改操作略显繁琐。

我们修改需要维护两种操作：区间乘和区间加。我们可以在块内创建两个标记，一个是区间乘标记 $\text{mul}$ ，另一个区间加标记 $\text{add}$ 。初始的时候 $\text{mul=1,add=0}$ 。

对于区间乘，发现对于块内的一个值 $x$ ，实际的值应该是：

$(x\times \text{mul})+\text{add}$

但如果乘上了一个数 $c$ ，则原式变为了：

\begin{aligned} &c(x\times \text{mul})+c\times\text{add}\\ =&(x\times (c\times\text{mul}))+c\times\text{add} \end{aligned}

即将乘法标记乘上 $c$ ，同时也将累加标记加上 $c$ 。

对于区间加，如果加上了一个数 $c$ ，则原式变为了：

(x\times \text{mul})+\text{add}+c

即不对乘法标记进行修改，只将加法标记加上一个 $c$ 。

对于零散块，会发现，如果没有将标记下传而直接修改实际值是错误的。例如，对于一个值 $x$ ，如果不下传标记而直接区间乘 $c$ 就会变为：

\begin{aligned} &(x\times c)\times \text{mul}+\text{add}\\ \ne&((x\times \text{mul})+\text{add})\times c \end{aligned}

而区间加 $c$ 就会变为：

\begin{aligned} &(x+c)\times\text{mul}+\text{add}\\ \ne&((x\times \text{mul})+\text{add})+c \end{aligned}

因此，对于零散块而言，需要将标记下传到块内的每一个值。

最后说一下，记得及时取模。

代码实现

分块 8#

题目链接

操作涉及区间询问等于一个数 $c$ 的元素，并将这个区间的所有元素改为 $c$ 。

先是看到有区间推平，想到了珂朵莉树，然后不小心过了。代码实现

然后这题的珂朵莉树貌似是卡不掉的，因为推平操作和查询操作绑定在了一起，推平操作一定占到了总操作数的 $50\%$ ，所以应该算是正解。

~~分块等会写~~

update 2022.5.1：放假了，终于把分块做法补上了。

观察题目，发现对于 $50\%$ 的询问，都会将一个区间变为一个相同的数，而且，数据范围很大，所以势必会让一段区间内每个数字都相等。如果仍然暴力计算数字相等区间内的答案，那么将会花费很多时间。

这里我们可以往块内增加一个属性 $\text{flag}$ 和 $\text{tag}$ ，其中 $\text{flag}$ 是个 $\text{bool}$ 变量，储存着当前块管辖的区间内是否每个值都相等， $\text{tag}$ 是个 $\text{int}$ 变量，储存着如果 $\text{flag}$ 为 $\text{true}$ ，那么区间内每个值都是多少。

可以想到，对于整块而言，如果标记为 $\text{true}$ ，那么直接将答案加上块内元素数量，否则暴力；对于零散块而言，直接暴力，注意，要将块内的 $\text{tag}$ 下传到实际的值，如果直接使用原数组内的 $a_i$ 是错误的，因为在修改的时候是直接修改覆盖到的块的 $\text{tag}$ 和 $\text{flag}$ ，并不会对块内实际值做出改变。