分块

分块是一种思想，不是一种数据结构。分块的基本思想是，通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。

例题：【模板】线段树 1

我们将序列分为 $\left\lceil\dfrac{n}{b}\right\rceil$ 块，第 $i$ 块维护 $\left[(i - 1) \times \left\lfloor\dfrac{n}{b}\right\rfloor + 1, i \times \left\lfloor\dfrac{n}{b}\right\rfloor\right]$ ，第 $\left\lfloor\dfrac{n}{b}\right\rfloor + 1$ 块（如果有的话）维护 $\left[\left\lfloor\dfrac{n}{b}\right\rfloor^2 + 1, n\right]$ 。

对于每一块，维护一个 $sum$ 数组，表示第 $i$ 块内不算上整块修改的 $a_i$ 的和。再维护一个 $tag$ 数组，表示第 $i$ 块整块累计增加的值。

对于修改操作：

如果 $l$ 与 $r$ 在同一个块里，直接暴力修改每一个 $a_i$ ，并将 $sum$ 累加。

否则，将 $l$ 到 $r$ 的所有整块（被 $[l, r]$ 完全包含的块）的 $tag \to tag + x$ ，并对散块（不被 $[l, r]$ 完全包含的块）暴力修改，将 $sum$ 累加。

对于查询操作：

如果 $l$ 与 $r$ 在同一个块里，直接求和即可，注意要加上 $tag \times (r - l + 1)$ （因为每个点都被增加过 $tag$ ）。

否则，对于 $l$ 到 $r$ 的所有整块（被 $[l, r]$ 完全包含的块），使 $ans \to ans + sum + tag \times siz$ ，并对散块（不被 $[l, r]$ 完全包含的块）暴力直接求和（也要加上 $tag \times (r - l + 1)$ ），将结果加起来。

单次修改或查询时间复杂度为 $O(\frac{n}{b} + b)$ ，显然 $b$ 取 $\sqrt n$ 最优，时间复杂度为 $O(\sqrt n)$ 。

代码：

#include <cstdio>
#include <cmath>

int len, k, n, q, t, l, r, x, siz[1001], b[100001], s[1001], e[1001];
long long v[100001], sum[1001], tag[1001];
int main(){
	scanf("%d%d", &n, &q);
	int len = sqrt(n);
	int k = len;
	for (int i = 1;i <= len;i ++){
		s[i] = (i - 1) * len + 1;
		e[i] = i * len;
	}
	if (len * len < n) s[++ k] = e[len] + 1, e[k] = n;
	for (int i = 1;i <= k;i ++){
		siz[i] = e[i] - s[i] + 1;
		for (int j = s[i];j <= e[i];j ++) b[j] = i;
	}
	for (int i = 1;i <= n;i ++) scanf("%lld", &v[i]);
	for (int i = 1;i <= k;i ++){
		for (int j = s[i];j <= e[i];j ++) sum[i] += v[j];
	}
	while (q --){
		scanf("%d", &t);
		if (t == 1){
			scanf("%d%d%d", &l, &r, &x);
			int bl = b[l], br = b[r];
			if (bl == br){
				for (int i = l;i <= r;i ++) v[i] += x, sum[bl] += x;
			}
			else {
				if (l != s[bl]){
					for (int i = l;i <= e[bl];i ++) v[i] += x, sum[bl] += x;
					bl ++;
				}
				if (r != e[br]){
					for (int i = s[br];i <= r;i ++) v[i] += x, sum[br] += x;
					br --;
				}
				for (int i = bl;i <= br;i ++) tag[i] += x;
			}
		}
		else {
			scanf("%d%d", &l, &r);
			int bl = b[l], br = b[r];
			long long ans = 0;
			if (bl == br){
				for (int i = l;i <= r;i ++) ans += v[i] + tag[bl];
			}
			else {
				if (l != s[bl]){
					for (int i = l;i <= e[bl];i ++) ans += v[i] + tag[bl];
					bl ++;
				}
				if (r != e[br]){
					for (int i = s[br];i <= r;i ++) ans += v[i] + tag[br];
					br --;
				}
				for (int i = bl;i <= br;i ++) ans += sum[i] + tag[i] * siz[i];
			}
			printf("%lld\n", ans);
		}
	}
}

例题：[Violet] 蒲公英

这是一道经典的区间众数问题。

由于众数与值域无关，先离散化。

我们像上一道题一样将序列分为 $\left\lfloor \dfrac{n}{b} \right\rfloor$ 块，长度为 $b$ ，对于每一个询问，把 $[l, r]$ 分为 $3$ 段：

$[l, L)$ ，其中 $L$ 为 $l$ 后面第一个整块的左端点；
$[L, R]$ ，其中 $R$ 为 $r$ 前面第一个整块的右端点；
$(R, r]$ 。

不难发现，答案只有两种可能：

$[L, R]$ 的众数；
$[l, L)$ 以及 $(R, r]$ 中出现的数。

我们可以预处理出每一个形如区间 $[L, R]$ 的众数（ $L$ ， $R$ 都是一个整块的端点），这样的区间一共有 $\left(\dfrac{n}{b}\right)^2$ 个，预处理时间复杂度为 $O(n\frac{n}{b})$ 。

查询时可以直接查询 $[L, R]$ 的众数，而 $[l, L)$ 以及 $(R, r]$ 中出现的数的出现次数要另外计算。我们可以用 vector 来顺序记录下每一个值的所有出现位置，在查询时二分查找即可。

总时间复杂度为 $O(n\frac{n}{b} + mb \log n)$ ， $b$ 取 $\sqrt{\frac n{\log n}}$ 时时间复杂度为 $O((n + m)\sqrt{n \log n})$ 。

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;

int n, m, a[40001], b[40001], _l, t[40001], ks, zs, cs;
int len, L[1001], R[1001], B[40001], g[1001][1001];
int lst, l, r, bl, br, tmp, cnt, ans;
vector<int> p[40001];
int counts(int l, int r, int x){
	return upper_bound(p[x].begin(), p[x].end(), r) - lower_bound(p[x].begin(), p[x].end(), l);
}
int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1;i <= n;i ++) scanf("%d", &a[i]), b[i] = a[i];
	sort(b + 1, b + n + 1);
	_l = unique(b + 1, b + n + 1) - b - 1;
	for (int i = 1;i <= n;i ++) a[i] = lower_bound(b + 1, b + _l + 1, a[i]) - b;
	for (int i = 1;i <= n;i ++) p[a[i]].push_back(i);
	len = 40;
	for (int i = 1;i <= n / len;i ++) ks ++, L[ks] = (i - 1) * len + 1, R[ks] = i * len;
	if (R[ks] < n) ks ++, L[ks] = R[ks - 1] + 1, R[ks] = n;
	for (int i = 1;i <= ks;i ++){
		for (int j = L[i];j <= R[i];j ++) B[j] = i;
	}
	for (int i = 1;i <= ks;i ++){
		memset(t, 0, sizeof(t)), cs = zs = 0;
		for (int j = i;j <= ks;j ++){
			for (int k = L[j];k <= R[j];k ++){
				t[a[k]] ++;
				if (cs < t[a[k]] || (cs == t[a[k]] && zs > a[k])) zs = a[k], cs = t[a[k]];
			}
			g[i][j] = zs;
		}
	}
	while (m --){
		scanf("%d%d", &l, &r);
		l = (l + lst - 1) % n + 1;
		r = (r + lst - 1) % n + 1;
		if (l > r) swap(l, r);
		bl = B[l], br = B[r];
		cnt = ans = 0;
		if (bl == br){
			for (int i = l;i <= r;i ++){
				tmp = counts(l, r, a[i]);
				if (cnt < tmp || (cnt == tmp && ans > a[i])) cnt = tmp, ans = a[i];
			}
		}
		else {
			for (int i = l;i <= R[bl];i ++){
				tmp = counts(l, r, a[i]);
				if (cnt < tmp || (cnt == tmp && ans > a[i])) cnt = tmp, ans = a[i];
			}
			for (int i = L[br];i <= r;i ++){
				tmp = counts(l, r, a[i]);
				if (cnt < tmp || (cnt == tmp && ans > a[i])) cnt = tmp, ans = a[i];
			}
			bl ++, br --;
			if (bl <= br && g[bl][br]){
				tmp = counts(l, r, g[bl][br]);
				if (cnt < tmp || (cnt == tmp && ans > g[bl][br])) cnt = tmp, ans = g[bl][br];
			}
		}
		printf("%d\n", lst = b[ans]);
	}
}

例题：磁力块

我们可以写出一个 BFS 框架，队列里维护已经被吸引的磁石。

现在我们要解决的问题就是哪些磁石可以被吸引。

我们可以将磁石先按照质量排序，分成 $\sqrt n$ 段后对每一段按照距离原点的距离排序。

显然有一个正整数 $k$ 满足以下两个条件：

对于 $1 \le i \le k - 1$ 的 $i$ ，每一块里的所有磁石的质量都小于等于当前使用的磁石的磁力。
对于 $k + 1 \le i \le n$ 的 $i$ ，每一块里的所有磁石的质量都大于当前使用的磁石的磁力。

对于满足第一种情况的块，我们直接从那一块的左端点往右扫描并入队，然后将左端点移到第一个距离大于吸引半径的磁石处，就可以保证每一个磁石在这个环节只被扫描一次。

对于第 $k$ 段，直接暴力扫描即可。

BFS 的时间复杂度为 $O(n)$ ，暴力扫描的时间复杂度为 $O(\sqrt n)$ ，总时间复杂度为 $O(n \sqrt n)$ 。

#include <algorithm>
#include <cstdio>
#include <cmath>
double dis(double ax, double ay, double bx, double by){
	return sqrt((ax - bx) * (ax - bx) + (ay - by) * (ay - by));
}

using namespace std;

struct node{
	int w, p, r;
	double d;
}st, a[300001], q[300001], f;
bool cmp1(node a, node b){return a.w < b.w;}
bool cmp2(node a, node b){return a.d < b.d;}
int n, X, Y, x, y, ql = 1, qr = 0, ans;
int len, cnt, L[1001], R[1001], maxw[1001];
bool vis[300001];
int main(){
	st.w = st.d = 0;
	scanf("%d%d%d%d%d", &X, &Y, &st.p, &st.r, &n);
	for (int i = 1;i <= n;i ++){
		scanf("%d%d%d%d%d", &x, &y, &a[i].w, &a[i].p, &a[i].r);
		a[i].d = dis(X, Y, x, y);
	}
	sort(a + 1, a + n + 1, cmp1);
	len = sqrt(n);
	for (int i = 1;i <= n / len;i ++) cnt ++, L[cnt] = (i - 1) * len + 1, R[cnt] = i * len;
	if (R[cnt] < n) cnt ++, L[cnt] = R[cnt - 1] + 1, R[cnt] = n;
	for (int i = 1;i <= cnt;i ++) maxw[i] = a[R[i]].w, sort(a + L[i], a + R[i] + 1, cmp2);
	q[++ qr] = st;
	while (ql <= qr){
		f = q[ql ++];
		for (int i = 1;i <= cnt;i ++){
			if (maxw[i] > f.p){
				for (int j = L[i];j <= R[i];j ++){
					if (!vis[j] && a[j].w <= f.p && a[j].d <= f.r) vis[j] = 1, q[++ qr] = a[j];
				}
				break;
			}
			for (;L[i] <= R[i] && a[L[i]].d <= f.r;L[i] ++){
				if (!vis[L[i]]) q[++ qr] = a[L[i]];
			}
		}
	}
	printf("%d", qr - 1);
}

菜王的 blog

分块思想学习笔记

分块

例题：【模板】线段树 1

例题：[Violet] 蒲公英

例题：磁力块

下一篇：点分治学习笔记