分块

现在我们回到初学者阶段，来学习乱搞型数据结构：分块。

分块简述

分块就是把一个序列均匀地分成若干块，每块维护某些信息。针对每次查询的区间，我们直接暴力搞掉两边的零碎块，然后规模实在大的中间部分就用块来搞。所以说，分块其实就像是个优化的暴力，但复杂度是根号的。

分块的基础操作

计算块长

为了保证复杂度，我们规定块长就是总长开根号。

block = sqrt(n);

计算某个位置所对应的块的编号

算是规律吧。

blong[i] = (i - 1) / block + 1;

计算某个块的左右端点

左端点：该块左面的所有块总长 +1

右端点：该块及之前块的总长

st[i] = (i - 1) * block + 1;
ed[i] = min(st[i] + block - 1, n);//处理最后小块，也可直接特判

计算块的个数

注意序列长为完全平方数的情况，但一般让个数++就问题不大了。

limi = n / block + 1;

对最后零散块的特判

通常我们可以对最后的那个小块以及小块往后的块进行特殊处理，以防出一些奇怪的小错。

blong[n + 1] = blong[n] + 1, st[blong[n + 1]] = n + 1;

例题

线段树 1

这是一道熟悉的线段树题，我们也可以用~~树状数组或~~分块做。

维护每个点的权值val，每个块的权值和sum。

区间加

如果查询区间非常小，即x与y在一个块里，直接暴力修改点的val和块的sum；

否则先处理两边小块。这两步代码类似：

val[i] += k;
sum[blong[i]] += k;

然后搞中间大块：

for (register int i = blong[x] + 1; i <= blong[y] - 1; ++i) {
	laz[i] += k;
	sum[i] += block * k;
}

区间查询

同上。

零碎：

ans += val[i] + laz[blong[i]];

整块：

ans += sum[i];

值得注意的是，我们要尽量保证每个点的真实性（和正确性），以求更简便地编程，我们在修改零碎时不变laz，直接变val和sum。毕竟是暴力算法嘛。

#6278. 数列分块入门 2：区间小于x的元素个数

考虑到如果序列是有序的，我们将可以 (nlogn) 时间内查询。所以我们分块后把每个块新建个数组排个序，然后再按分块思路一点点搞：

区间加

零碎暴力改，然后重新排序。

inline void resort(int cur) {
	for (register int i = st[cur]; i <= ed[cur]; ++i) h[i] = a[i];
	sort(h + st[cur], h + ed[cur] + 1);
}
...
			if (blong[l] == blong[r]) {
				for (register int i = l; i <= r; ++i) {
					a[i] += c;
				}
				resort(blong[l]);
				continue;
			}
			for (register int i = l; i <= ed[blong[l]]; ++i) {
				a[i] += c;
			}
			resort(blong[l]);
			for (register int i = r; i >= st[blong[r]]; --i) {
				a[i] += c;
			}
			resort(blong[r]);
			for (register int i = blong[l] + 1; i <= blong[r] - 1; ++i) {
				laz[i] += c;
			}

区间查询

零碎暴力查，整块二分查。

inline int query(int cur, int x) {//二分
	int l = st[cur], r = ed[cur], mid, res = l - 1;
	while (l <= r) {
		mid = (l + r) >> 1;
		if (h[mid] + laz[cur] < x) {
			res = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	return res - st[cur] + 1;
}
...
			int c2 = 1ll * c * c;
			int res = 0;
			if (blong[l] == blong[r]) {
				for (register int i = l; i <= r; ++i) {
					if (a[i] + laz[blong[l]] < c2) res++;
				}
				printf("%lld
", res);
				continue;
			}
			for (register int i = l; i <= ed[blong[l]]; ++i) {
				if (a[i] + laz[blong[l]] < c2) res++;
			}
			for (register int i = r; i >= st[blong[r]]; --i) {
				if (a[i] + laz[blong[r]] < c2)	res++;
			}
			for (register int i = blong[l] + 1; i <= blong[r] - 1; ++i) {
				res += query(i, c2);
			}
			printf("%lld
", res);

#6285. 数列分块入门 9:区间最小众数

还是很重要的一个思想：先处理好大块的答案，然后考虑到零散块对答案的影响只可能发生在零散块里面的那些数中，因此对于零散块单独计算即可。

包括区间加权众数（4241: 历史研究）的处理方法也是一样。

主要数组：

f[i][j]:从第i块到第j块的最小众数
v[x]:数x的所有出现位置（从小到大排序）
Cnt[x]:数x的出现次数（用来暂存的容器，随时清空）

每次询问区间的答案只可能出现在全部整块众数，和边角块的数。因此我们预处理好f[i][j]，每次暴力数就好了。

需要注意一下预处理的方法。

类似的题目：P4135 作诗

时间复杂度：(nsqrt nlogn)；空间复杂度： (n)

(Code:)

inline void init(int t) {
    if (st[t] > ed[t])
        return;  
    memset(Cnt, 0, sizeof(Cnt));
    int ans = inf, mxcnt = 0;
    for (register int i = st[t]; i <= n; ++i) {
        Cnt[a[i]]++;
        if (Cnt[a[i]] > mxcnt || (Cnt[a[i]] == mxcnt && val[a[i]] < val[ans])) {
            mxcnt = Cnt[a[i]];
            ans = a[i];
        }
        f[t][blong[i]] = ans;
    }
}
inline int countt(int l, int r, int x) {
    int res = upper_bound(v[x].begin(), v[x].end(), r) - lower_bound(v[x].begin(), v[x].end(), l);
    return res;
}
inline int query(int l, int r) {
    int mxcnt = 0, res = inf, cnt;
    if (blong[l] == blong[r]) {
        for (register int i = l; i <= r; ++i) {
            cnt = countt(l, r, a[i]);
            if (cnt > mxcnt || (cnt == mxcnt && val[a[i]] < val[res])) {
                mxcnt = cnt;
                res = a[i];
            }
        }
        return res;
    }
    res = f[blong[l] + 1][blong[r] - 1];
    mxcnt = countt(l, r, res);
    for (register int i = l; i <= ed[blong[l]]; ++i) {
        cnt = countt(l, r, a[i]);
        if (cnt > mxcnt || (cnt == mxcnt && val[a[i]] < val[res])) {
            mxcnt = cnt;
            res = a[i];
        }
    }
    for (register int i = r; i >= st[blong[r]]; --i) {
        cnt = countt(l, r, a[i]);
        if (cnt > mxcnt || (cnt == mxcnt && val[a[i]] < val[res])) {
            mxcnt = cnt;
            res = a[i];
        }
    }
    return res;
}
int main() {
	...(get in and lsh)
	for (register int i = 1; i <= n / block + 1; ++i) init(i);
	int l, r;
	for (register int i = 1; i <= n; ++i) {
		read(l);
		read(r);
		printf("%d
", val[query(l, r)]);
	}
	return 0;
}

优化

如果时间卡得很紧，但是空间允许开得很大，那么我们有这样的一种优化方法：

关键变量:

Cnt[bk][x]：从块 bk 开始，一直到结束，数 x 的出现总次数（类似后缀和）
f[bk][bk]：同上
bin[x]：数 x 的出现次数（不同时间意义不太一样，是一个用来暂存的容器）

每次我们直接统计得到 x 的出现次数，而不去 (lower~bound)，这样可以在时间上少一个 log。但是又要求我们不能对暂存容器 (bin) 进行 (n) 次 (memset)，所以要把用到的数存到一个栈里面，最后只清空栈里面的数（常见套路）。实际上，计算与清空是同步进行的。

可以看到：

19.15s -> 1.68s

10.79MB -> 66.93MB

能够从这里看出两种方法的优缺点。

int Cnt[NN][N], f[NN][NN];
inline void work(int bk) {
	int cnt = -1, num;
	for (register int i = st[bk]; i <= n; ++i) {
		Cnt[bk][h[i]]++;
		if (Cnt[bk][h[i]] > cnt || (Cnt[bk][h[i]] == cnt && h[i] < num))
			cnt = Cnt[bk][h[i]], num = h[i];
		if (blong[i] != blong[i + 1])	f[bk][blong[i]] = num;
	}
}

inline void init() {
	block = sqrt(n);
	for (register int i = 1; i <= n; ++i)	blong[i] = (i - 1) / block + 1;
	for (register int i = 1; i <= n / block + 1; ++i) {
		st[i] = (i - 1) * block + 1;
		ed[i] = min(n, st[i] + block - 1);
	}
	blong[n + 1] = blong[n] + 1; st[blong[n + 1]] = n + 1;
	for (register int i = 1; i <= blong[n]; ++i)
		work(i);
}

int stk[N], stop, bin[N];
inline void query(int l, int r) {
	stop = 0;
	if (blong[l] == blong[r]) {
		for (register int i = l; i <= r; ++i)	bin[h[i]]++, stk[++stop] = h[i];
		int cnt = -1, num;
		while (stop) {
			int tmp = stk[stop--];
			if (!bin[tmp])	continue;
			if (bin[tmp] > cnt || (bin[tmp] == cnt && tmp < num))
				cnt = bin[tmp], num = tmp;
			bin[tmp] = 0;
		}
		ans = num;
		return ;
	}
	
	int lft = blong[l] + 1, rig = blong[r] - 1;
	int cnt = -1, num;
	if (lft <= rig)	num = f[lft][rig], cnt = Cnt[lft][num] - Cnt[rig + 1][num];
	for (register int i = l; i <= ed[blong[l]]; ++i)	bin[h[i]]++, stk[++stop] = h[i];
	for (register int i = r; i >= st[blong[r]]; --i)	bin[h[i]]++, stk[++stop] = h[i];
	while (stop) {
		int tmp = stk[stop--];
		if (!bin[tmp])	continue;
		int ntmp = bin[tmp] + Cnt[lft][tmp] - Cnt[rig + 1][tmp];
		if (ntmp > cnt || (ntmp == cnt && tmp < num))
			cnt = ntmp, num = tmp;
		bin[tmp] = 0;
	}
	ans = num;
}

值域分块

针对值域进行分块。

有些题操作就是在值域上的，比如莫队的单点加，求前 (k) 小，可以用来平衡复杂度。

还有些题操作是在区间上的，但是和值域有关系，这时候可以把序列按照值域分块，然后以所在块为第一关键字，位置为第二关键字排序，这样一个区间就被划分为了若干块的连续区间，然后可以对每个块进行暴力预处理之类的操作。Set Merging

分块的拓展

莫队算法
块状链表（其实就是分块）

练习题

以下给出几道练习题：

#6279. 数列分块入门 3 区间加，查询前驱

#6280. 数列分块入门 4 区间加，区间求和

#6281. 数列分块入门 5 区间开放，区间求和

#6282. 数列分块入门 6 单点插入，单点查询

#6283. 数列分块入门 7 区间乘，区间加，单点查询

#6284. 数列分块入门 8 区间查询值为某值的元素个数，区间推平

#6285. 数列分块入门 9 区间查询最小众数 (类似的题：P4168 [Violet]蒲公英）

P3203 [HNOI2010]弹飞绵羊

P4135 作诗

注意：

分块如果调挂了的话，可以对拍造组小数据，玩一下数据。因为分块相对于树形数据结构（如平衡树）来说很好调。
分块入过的坑：

对小范围的特判的continue
计算ed[i]的取min

	for (register int i = 1; i <= n / block + 1; ++i) {
		st[i] = (i - 1) * block + 1;
		ed[i] = min(st[i] + block - 1, n);//attention!
	}

这部分的 (i) 有两种可能，一种是序列里的编号，一种是块的编号，写代码时要把 (i) 分清。
分块维护链表时，一定要分清节点编号和节点的值！！这部分非常容易出错！！

附

分块基本结构（实际上重难点在预处理和维护上）

inline void init() {
	block = sqrt(n);
	for (register int i = 1; i <= n; ++i)	blong[i] = (i - 1) / block + 1;
	for (register int i = 1; i <= n / block + 1; ++i) {
		st[i] = (i - 1) * block + 1;
		ed[i] = min(n, st[i] + block - 1);
	}
	blong[n + 1] = blong[n] + 1; st[blong[n + 1]] = n + 1;
	...//real init
}