分块——暴力美学

发表于 分类于 阅读次数：

暴力出奇迹，骗分过样例

区间加区间和

分块操作可以把一个对区间的操作变成对于如下三个区间的操作：

  • 左碎块
  • 右碎块
  • 中间整块

一般来说， 我们会把原区间分割成 \(\sqrt n\) 个块，每个块长达 \(\sqrt n\) 。举个例子，对于一个长度为16的区间，我们把他分成1 \(\sim\) 4， 5 \(\sim\) 8，9 \(\sim\) 12，13 \(\sim\) 16四块。那么，如果我们要对区间2 \(\sim\) 14进行操作，可以把它分为整块5 \(\sim\) 12，左碎块2 \(\sim\) 4和右碎块13 \(\sim\) 14.对于左右碎块，我们对每个元素暴力处理，而对于整块，我们对每一个块做一个lazytag。不难发现，整块中最多有 \(\sqrt n\) 个块， 两个碎块中最多有 \(2 \sqrt n\) 个元素，所以整体复杂度不会超过 \(O( \sqrt n)\) 。

实现方法

举个例子：区间修改，区间查询。 我们对于每一个块，维护一个块和，一个块被加和（lazytag）。

原序列：1 2 3 | 4 5 6 | 7 8 9 | 10

块和：6 | 15 | 24 | 10

块被加和：0 | 0 | 0 | 0

此时我们把区间 [2,10] 加上2，则整块为 [4,9] 即第2、3块，碎块为 [2,3] 和 [10,10] 。那么我们进行如下操作：

把碎块中的每个元素加上2（在原序列中修改，同时更改块和），把2，3两个块的块被加和加上2（原序列和块和都不变）。

原序列：1 2+2 3+2 | 4 5 6 | 7 8 9 | 10+2

块和：6+2+2 | 15 | 24 | 10+2

块被加和：0 | 0+2 | 0+2 | 0

可以看到，+2操作只进行了少于 \(4 \sqrt n\) 次。

这样之后如何查询呢？

  • 单点查询 \(O(1)\)

对于每一个元素，它的实际权值是原序列权值加上所在块的块被加和（为什么？）

原序列记录了它作为碎块时被修改的权值，块被加和记录了它作为整块的一部分时被修改的权值，所以实际权值就是两者之和。

  • 单块查询 \(O(1)\)

对于一个块，它所有元素的权值和为：块和 + 块被加和 * 块的长度（为什么？）

块被加和块被加和记录了它作为整块时被修改的权值，而且每个元素都加上了块被加和，所以整体加上了块被加和 * 块的长度；而块和则记录了当块中的一部分作为碎块时加的权值，所以实际权值就是两者之和。

  • 区间查询

也分成左碎块，右碎块和整块。对于两个碎块中的每个元素，做一次单点查询，对于整块中的每一块，做一次单块查询，把所有结果相加，时间复杂度 \(O(\sqrt n)\) 。

这样区间修改，区间查询就讲完了。 上模板：（肯定没有树状数组快啊）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
inline void init(int n) { while (len * len <= n) len++; len--; }
inline int get_id(int i) {return (i % len == 0) ? (i / len) : (i / len + 1); }

inline void update_one(int i, long long x) { a[i] += x; part[get_id(i)] += x; }
inline void update_part(int i, long long x) { lazy[i] += x; }
inline void update(int l, int r, long long x) {
    while (l % len != 1) update_one(l++, x);
    while (r % len != 0) update_one(r--, x);
    for (int i = get_id(l); i <= get_id(r); i++) update_part(i, x);
}

inline long long ask_one(int i) { return a[i] + lazy[get_id(i)]; }
inline long long ask_part(int i) { return part[i] + lazy[i] * len; }
inline long long ask(int l, int r) {
    long long res = 0;
    while (l % len != 1) res += ask_one(l++);
    while (r % len != 0) res += ask_one(r--);
    for (int i = get_id(l); i <= get_id(r); i++) res += ask_part(i);
    return res;
}

区间推平

凡是涉及到区间推平的操作，可以放心大胆地对整块进行tag标记，并且在处理散块时大胆地把标记下放。如果在整块查询中遇到了被下放过tag的整块，就对整块进行暴力处理。不要担心时间复杂度，因为每次修改只会下放2个标记，但是会打下 \(\sqrt n\) 个标记。

例题：数列分块入门 8

参考代码：

vector二分

考虑以下问题：区间加，区间前驱。

我们可以将每一个块里的数分别存到一个 std::vector<int> 里，然后进行排序，查询时在每个块中二分出前驱，然后在 \(\sqrt n\) 个可能前驱中求出答案。修改时对于整块打标记，对于碎块，暴力修改后重构 vector 。注意在查询时输入的 \(x\) 要相应加减块标记。

例题：数列分块入门 2

值域分块

考虑以下问题：求区间逆序对，单点修改。

vector二分时间复杂度带 \(log\) ，但能解决区间修改。而如果是单点修改，我们可以考虑值域分块。

顾名思义，我们在值域上分块，记录在每个值域块中有多少个数。我们对每一个序列块进行值域分块，也就是求出每个块中有几个数在 \(1 \sim \sqrt n\) 之间，有几个数在 \(\sqrt n \sim 2\sqrt n\) 之间……然后将值域分块结果做前缀和，求出在前 \(i\) 个块中有几个数在 \(1 \sim \sqrt n\) 之间，有几个数在 \(\sqrt n \sim 2\sqrt n\) 之间……这样就可以在 \(\sqrt n\) 的时间内知道区间内有几个数比 \(x\) 小，比 \(x\) 大。那么区间逆序对可以先用归并求出，然后对于单点修改暴力更新块，包括 \(\sqrt n\) 个前缀值域分块结果和查询 \(i\) 以前产生了多少逆序对， \(i\) 现在产生了多少逆序对。

例题：动态逆序对