分块
Eva.Q Lv9
2023-08-26 21:40:05

布帛菽粟，柴米油盐。

分块

分块就是把一个整体划分为若干个小块，对于每个小块维护信息。每次操作或询问时，如果某个小块被完全覆盖，那么就可以直接修改或利用这个小块的信息，如果某个小块被部分覆盖，那么久暴力修改或利用被覆盖部分的每个元素。

对于一个长度为 的数组，如果分成 块，那么每块的长度就是 。块数不能太少也不能太多，一般来说会分成 块。这样在最坏情况下，我们要处理接近 个整块，还要对长度为 的零散块单独处理，总时间复杂度为 。这是一种根号算法。

虽然在复杂度上劣于线段树和树状数组，但它好写。

1
2
3
4
5
6
int n = rd(), len = sqrt(n); // n 元素个数  len 块长
for (int i = 0; i < n; ++i) {
    a[i] = rd();
    if (i % len == 0) L[i / len] = i; // L[] 块的左端点 
    R[i / len] = i; // R[] 块的右端点
}

i/len 为 所在的块编号，i%len 为 的块内编号。块编号范围 ，块内编号范围 。

例题

loj.ac 数列分块入门 1 ~ 5

例题1

区间加法，单点查值。

对于每个小块，维护区间和和加法标记。每次区间加法，如果整个区间被覆盖就把标记加，如果区间被部分覆盖，就把被覆盖部分的每个元素加。查值时，答案为该元素加上其所在区间的标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define N 50007
#define M 230
ll a[N], tag[M];
int L[M], R[M];

int main() {
    int n = rd(), len = sqrt(n);
    for (int i = 0; i < n; ++i) {
        a[i] = rd();
        if (i % len == 0) L[i / len] = i;
        R[i / len] = i;
    }
    for (int i = 1; i <= n; ++i) {
        int op = rd(), l = rd() - 1, r = rd() - 1, c = rd();
        int bll = l / len, blr = r / len;
        if (op) {
            printf("%lld\n", a[r] + tag[blr]);
        } else {
            if (bll == blr) {
                for (int i = l; i <= r; ++i) a[i] += c;
            } else {
                for (int i = l; i <= R[bll]; ++i) a[i] += c;
                for (int i = L[blr]; i <= r; ++i) a[i] += c;
                for (int i = bll + 1; i < blr; ++i) tag[i] += c;
            }
        }
    }
    return 0;
}

例题2

区间加法，区间查询小于某个值 的元素个数。

对于每个块，开一个 vector 维护块内的升序列，并用标记维护区间加法。每次区间加法，如果整个区间被覆盖就把标记加，如果区间被部分覆盖，就把被覆盖部分的每个元素加，并把该区间的所有元素重新排序存进 vector 。查询时，如果整个区间被覆盖，用 lower_bound 查询统计，如果区间被部分覆盖，对被覆盖部分的元素暴力统计。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#define N 50007
#define M 230
ll tag[M], a[N];
int L[M], R[M];
vector<ll> v[M];

int main() {
    int n = rd(), len = sqrt(n);
    for (int i = 0; i < n; ++i) {
        v[i / len].pb(a[i] = rd());
        if (i % len == 0) L[i / len] = i;
        R[i / len] = i;
    }
    for (int i = 0; i <= (n - 1) / len; ++i) sort(v[i].begin(), v[i].end());
    for (int q = 1; q <= n; ++q) {
        int op = rd(), l = rd() - 1, r = rd() - 1;
        ll c = rd();
        int bll = l / len, blr = r / len;
        if (op) {
            c *= c;
            int cnt = 0;
            if (bll == blr) {
                for (int i = l; i <= r; ++i)
                    if (a[i] < c - tag[bll]) ++cnt;
            } else {
                for (int i = l; i <= R[bll]; ++i)
                    if (a[i] < c - tag[bll]) ++cnt;
                for (int i = L[blr]; i <= r; ++i)
                    if (a[i] < c - tag[blr]) ++cnt;
                for (int i = bll + 1; i < blr; ++i) {
                    auto it = lower_bound(v[i].begin(), v[i].end(), c - tag[i]);
                    cnt += it - v[i].begin();
                }
            }
            printf("%d\n", cnt);
        } else {
            if (bll == blr) {
                for (int i = l; i <= r; ++i) a[i] += c;
                v[bll].clear();
                for (int i = L[bll]; i <= R[bll]; ++i) v[bll].pb(a[i]);
                sort(v[bll].begin(), v[bll].end());
            } else {
                for (int i = l; i <= R[bll]; ++i) a[i] += c;
                v[bll].clear();
                for (int i = L[bll]; i <= R[bll]; ++i) v[bll].pb(a[i]);
                sort(v[bll].begin(), v[bll].end());
                for (int i = L[blr]; i <= r; ++i) a[i] += c;
                v[blr].clear();
                for (int i = L[blr]; i <= R[blr]; ++i) v[blr].pb(a[i]);
                sort(v[blr].begin(), v[blr].end());
                for (int i = bll + 1; i < blr; ++i) tag[i] += c;
            }
        }
    }
    return 0;
}

例题3

区间加法，区间查询小于某个值 的最大元素。

对于每个块，开一个 vector 维护块内的升序列，并用标记维护区间加法。每次区间加法，如果整个区间被覆盖就把标记加，如果区间被部分覆盖，就把被覆盖部分的每个元素加，并把该区间的所有元素重新排序存进 vector 。查询时，如果整个区间被覆盖，用 lower_bound 查询更新答案，如果区间被部分覆盖，对被覆盖部分的元素暴力查询更新答案，不要忘了加上对应标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#define N 100007
#define M 330
ll tag[M], a[N];
int L[M], R[M];
vector<ll> v[M];

int main() {
    int n = rd(), len = sqrt(n);
    for (int i = 0; i < n; ++i) {
        v[i / len].pb(a[i] = rd());
        if (i % len == 0) L[i / len] = i;
        R[i / len] = i;
    }
    for (int i = 0; i <= (n - 1) / len; ++i) sort(v[i].begin(), v[i].end());
    for (int q = 1; q <= n; ++q) {
        int op = rd(), l = rd() - 1, r = rd() - 1;
        ll c = rd();
        int bll = l / len, blr = r / len;
        if (op) {
            ll mx = -1e18;
            if (bll == blr) {
                for (int i = l; i <= r; ++i)
                    if (a[i] < c - tag[bll]) mx = max(mx, a[i] + tag[bll]);
            } else {
                for (int i = l; i <= R[bll]; ++i)
                    if (a[i] < c - tag[bll]) mx = max(mx, a[i] + tag[bll]);
                for (int i = L[blr]; i <= r; ++i)
                    if (a[i] < c - tag[blr]) mx = max(mx, a[i] + tag[blr]);
                for (int i = bll + 1; i < blr; ++i) {
                    auto it = lower_bound(v[i].begin(), v[i].end(), c - tag[i]);
                    if (it != v[i].begin()) mx = max(mx, (*(--it)) + tag[i]);
                }
            }
            printf("%lld\n", mx == -1e18 ? -1 : mx);
        } else {
            if (bll == blr) {
                for (int i = l; i <= r; ++i) a[i] += c;
                v[bll].clear();
                for (int i = L[bll]; i <= R[bll]; ++i) v[bll].pb(a[i]);
                sort(v[bll].begin(), v[bll].end());
            } else {
                for (int i = l; i <= R[bll]; ++i) a[i] += c;
                v[bll].clear();
                for (int i = L[bll]; i <= R[bll]; ++i) v[bll].pb(a[i]);
                sort(v[bll].begin(), v[bll].end());
                for (int i = L[blr]; i <= r; ++i) a[i] += c;
                v[blr].clear();
                for (int i = L[blr]; i <= R[blr]; ++i) v[blr].pb(a[i]);
                sort(v[blr].begin(), v[blr].end());
                for (int i = bll + 1; i < blr; ++i) tag[i] += c;
            }
        }
    }
    return 0;
}

例题4

区间加法，查询区间和。

对于每个块，维护区间和，和区间加法标记。每次区间加法，如果整个区间被覆盖就把标记加，如果区间被部分覆盖，就把被覆盖部分的每个元素加。查询时，如果整个区间被覆盖，就把区间和加到答案里，如果区间被部分覆盖，用每个被覆盖部分的元素更新答案，不要忘了加上对应标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#define N 50007
#define M 230
ll a[N], tag[M], sum[M];
int L[M], R[M];

int main() {
    int n = rd(), len = sqrt(n);
    for (int i = 0; i < n; ++i) {
        sum[i / len] += (a[i] = rd());
        if (i % len == 0) L[i / len] = i;
        R[i / len] = i;
    }
    for (int q = 1; q <= n; ++q) {
        int op = rd(), l = rd() - 1, r = rd() - 1;
        ll c = rd();
        int bll = l / len, blr = r / len;
        if (op) {
            c++;
            ll ans = 0;
            if (bll == blr) {
                ans = (ans + (r - l + 1) * tag[bll]) % c;
                for (int i = l; i <= r; ++i) ans = (ans + a[i]) % c;
            } else {
                for (int i = l; i <= R[bll]; ++i) ans = (ans + a[i] + tag[bll]) % c;
                for (int i = L[blr]; i <= r; ++i) ans = (ans + a[i] + tag[blr]) % c;
                for (int i = bll + 1; i < blr; ++i) ans = (ans + sum[i]) % c;
            }
            printf("%lld\n", ans);
        } else {
            if (bll == blr) {
                sum[bll] += c * (r - l + 1);
                for (int i = l; i <= r; ++i) a[i] += c;
            } else {
                for (int i = l; i <= R[bll]; ++i) {sum[bll] += c; a[i] += c;}
                for (int i = L[blr]; i <= r; ++i) {sum[blr] += c; a[i] += c;}
                for (int i = bll + 1; i < blr; ++i) {sum[i] += len * c; tag[i] += c;}
            }
        }
    }
    return 0;
}

例题5

区间开方，查询区间和。

对于每个块，维护区间和，和区间标记，标记这个区间里的元素是否都不能开方了。每次区间开方，如果整个区间被覆盖，根据标记判断该区间是否需要开方，如果需要就暴力把每一个开方，并更新区间和，如果不需要就跳过。如果区间被部分覆盖，就把被覆盖部分的每个元素暴力开方，并更新区间和。查询时，如果整个区间被覆盖，就把区间和加到答案里，如果区间被部分覆盖，用每个被覆盖部分的元素更新答案。这样的复杂度为什么是正确的呢？因为对于每一个元素其最多被开方 次，对于一个区间来说也是如此，所以复杂度是对的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#define N 50007
#define M 230
ll a[N], sum[M];
bool tag[M];
int L[M], R[M];

int main() {
    int n = rd(), len = sqrt(n);
    for (int i = 0; i < n; ++i) {
        sum[i / len] += (a[i] = rd());
        if (i % len == 0) L[i / len] = i;
        R[i / len] = i;
    }
    for (int q = 1; q <= n; ++q) {
        int op = rd(), l = rd() - 1, r = rd() - 1; rd();
        int bll = l / len, blr = r / len;
        if (op) {
            ll ans = 0;
            if (bll == blr) {
                for (int i = l; i <= r; ++i) ans += a[i];
            } else {
                for (int i = l; i <= R[bll]; ++i) ans += a[i];
                for (int i = L[blr]; i <= r; ++i) ans += a[i];
                for (int i = bll + 1; i < blr; ++i) ans += sum[i];
            }
            printf("%lld\n", ans);
        } else {
            if (bll == blr) {
                for (int i = l; i <= r; ++i) {
                    if (a[i] == 0 || a[i] == 1) continue;
                    sum[bll] -= a[i]; a[i] = sqrt(a[i]); sum[bll] += a[i];
                }
            } else {
                for (int i = l; i <= R[bll]; ++i) {
                    if (a[i] == 0 || a[i] == 1) continue;
                    sum[bll] -= a[i]; a[i] = sqrt(a[i]); sum[bll] += a[i];
                }
                for (int i = L[blr]; i <= r; ++i) {
                    if (a[i] == 0 || a[i] == 1) continue;
                    sum[blr] -= a[i]; a[i] = sqrt(a[i]); sum[blr] += a[i];
                }
                for (int i = bll + 1; i < blr; ++i) {
                    if (!tag[i]) {
                        bool f = 1;
                        for (int j = L[i]; j <= R[i]; ++j) {
                            if (a[j] == 0 || a[j] == 1) continue;
                            sum[i] -= a[j]; a[j] = sqrt(a[j]); sum[i] += a[j];
                            if (a[j] != 0 || a[j] != 1) f = 0;
                        }
                        tag[i] = f;
                    }
                }
            }
        }
    }
    return 0;
}

例题6

单点插入，单点询问。

这道题其实是定期重构。也就是说根据判断标准，对原数列进行重构。

具体做法如下：开一个 vector 用来保存些位置插入的值分别是多少，当 vector 的大小达到 时，对数列进行重构并清空 vector 。插入点时，先维护先前保存在 vector 中的点的插入位置，也就是说，如果一个点原本的插入位置是 ，那如果又来了一个点，它插入的位置 ，那么这个点插入的位置其实是 ；然后把当前的单点插入塞进 vector ，再判断是否需要重构，需要的话就进行重构，重构其实就是把 vector 里的点真的插入到数列里，具体方法就是一个指针指着原来的数组，一个指着 vector 。询问时，先判断询问的点是否在 vector 里，如果不在则答案在数列中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#define N 100007
int a[N << 1], b[N << 1];
vector<pii> Q;

int main() {
    int n = rd(), lim = sqrt(n), nn = n;
    for (int i = 1; i <= n; ++i) a[i] = rd();
    for (int q = 1; q <= nn; ++q) {
        int op = rd(), l = rd(), r = rd(); rd();
        if (op) {
            int cnt = 0; bool f = 0;
            for (auto t : Q) {
                int pos = t.fr, val = t.sc;
                if (pos == r) {printf("%d\n", val); f = 1; break;}
                else if (pos < r) ++cnt;
            }
            if (!f) printf("%d\n", a[r - cnt]);
        } else {
            for (auto &t : Q) {
                int &pos = t.fr;
                if (pos >= l) ++pos;
            }
            Q.pb(mp(l, r));
            int sz = (int)Q.size();
            if (sz >= lim) {
                sort(Q.begin(), Q.end());
                int tot = 0, pos1 = 1, pos2 = 0;
                while (pos1 <= n && pos2 < sz) {
                    for (; pos1 <= n && tot + 1 < Q[pos2].fr; b[++tot] = a[pos1], ++pos1);
                    b[++tot] = Q[pos2].sc; ++pos2;
                }
                for (; pos1 <= n; b[++tot] = a[pos1], ++pos1);
                for (; pos2 < sz; b[++tot] = Q[pos2].sc, ++pos2);
                Q.clear(); n = tot;
                for (int i = 1; i <= n; ++i) a[i] = b[i];
            }
        }
    }
    return 0;
}

例题7

区间乘法，区间加法，单点询问。

就是打两个标记，一个是乘法，一个是加法。需要注意的是，如果操作是区间乘法，那乘法标记和加法标记都要乘，如果是加法，那只有加法标记需要加。对于两边的小块，需要标记下放，下放后乘法标记需置 ，加法标记需置 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#define N 100007
#define mod 10007
#define M 321
int a[N], multag[M], addtag[M], L[M], R[M];

int main() {
    int n = rd(), len = sqrt(n);
    for (int i = 0; i < n; ++i) {
        a[i] = rd() % mod;
        if (i % len == 0)  {
            L[i / len] = i;
            multag[i / len] = 1;
        }
        R[i / len] = i;
    }
    for (int q = 1; q <= n; ++q) {
        int op = rd(), l = rd() - 1, r = rd() - 1, c = rd();
        int bll = l / len, blr = r / len;
        if (op == 0) {
            if (bll == blr) {
                for (int i = L[bll]; i <= R[bll]; ++i)
                    a[i] = (a[i] * multag[bll] % mod + addtag[bll]) % mod;
                multag[bll] = 1; addtag[bll] = 0;
                for (int i = l; i <= r; ++i) a[i] = (a[i] + c) % mod;
            } else {
                for (int i = L[bll]; i <= R[bll]; ++i)
                    a[i] = (a[i] * multag[bll] % mod + addtag[bll]) % mod;
                multag[bll] = 1; addtag[bll] = 0;
                for (int i = L[blr]; i <= R[blr]; ++i)
                    a[i] = (a[i] * multag[blr] % mod + addtag[blr]) % mod;
                multag[blr] = 1; addtag[blr] = 0;
                for (int i = l; i <= R[bll]; ++i) a[i] = (a[i] + c) % mod;
                for (int i = L[blr]; i <= r; ++i) a[i] = (a[i] + c) % mod;
                for (int i = bll + 1; i < blr; ++i)
                    addtag[i] = (addtag[i] + c) % mod;
            }
        } else if (op == 1) {
            if (bll == blr) {
                for (int i = L[bll]; i <= R[bll]; ++i)
                    a[i] = (a[i] * multag[bll] % mod + addtag[bll]) % mod;
                multag[bll] = 1; addtag[bll] = 0;
                for (int i = l; i <= r; ++i) a[i] = (a[i] * c) % mod;
            } else {
                for (int i = L[bll]; i <= R[bll]; ++i)
                    a[i] = (a[i] * multag[bll] % mod + addtag[bll]) % mod;
                multag[bll] = 1; addtag[bll] = 0;
                for (int i = L[blr]; i <= R[blr]; ++i)
                    a[i] = (a[i] * multag[blr] % mod + addtag[blr]) % mod;
                multag[blr] = 1; addtag[blr] = 0;
                for (int i = l; i <= R[bll]; ++i) a[i] = (a[i] * c) % mod;
                for (int i = L[blr]; i <= r; ++i) a[i] = (a[i] * c) % mod;
                for (int i = bll + 1; i < blr; ++i) {
                    multag[i] = (multag[i] * c) % mod;
                    addtag[i] = (addtag[i] * c) % mod;
                }
            }
        } else printf("%d\n", (a[r] * multag[blr] % mod + addtag[blr]) % mod);
    }
    return 0;
}

例题8

询问区间内某个值的个数并进行区间覆盖。

打两个标记，一个是区间覆盖标记，一个标志区间是否打过覆盖标记。每次询问时，如果没被打过标记，对于块内的每一段排序后用 upper_bound - lower_bound 查该小块中某个值的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#define N 100007
#define mod 10007
#define M 321
int a[N], L[M], R[M], tag[M];
bool istag[M];
vector<int> e[M];

inline void rebuild(int id) {
    e[id].clear(); istag[id] = false;
    for (int i = L[id]; i <= R[id]; ++i) e[id].pb(a[i]);
    sort(e[id].begin(), e[id].end());
}

int main() {
    int n = rd(), len = sqrt(n);
    for (int i = 0; i < n; ++i) {
        a[i] = rd(); int bl = i / len;
        if (i % len == 0) L[bl] = i;
        R[bl] = i;
        e[bl].pb(a[i]);
    }
    for (int i = 0; i <= (n - 1) / len; ++i) sort(e[i].begin(), e[i].end());
    for (int q = 1; q <= n; ++q) {
        int l = rd() - 1, r = rd() - 1, c = rd();
        int bll = l / len, blr = r / len, cnt = 0;
        if (bll == blr) {
            if (istag[bll]) {
                cnt += (r - l + 1) * (tag[bll] == c);
                for (int i = L[bll]; i <= R[bll]; ++i) a[i] = tag[bll];
            } else {
                for (int i = l; i <= r; ++i) cnt += (a[i] == c);
            }
            for (int i = l; i <= r; ++i) a[i] = c;
            rebuild(bll);
        } else {
            if (istag[bll]) {
                cnt += (R[bll] - l + 1) * (tag[bll] == c);
                for (int i = L[bll]; i <= R[bll]; ++i) a[i] = tag[bll];
            } else {
                for (int i = l; i <= R[bll]; ++i) cnt += (a[i] == c);
            }
            for (int i = l; i <= R[bll]; ++i) a[i] = c;
            rebuild(bll);
            if (istag[blr]) {
                cnt += (r - L[blr] + 1) * (tag[blr] == c);
                for (int i = L[blr]; i <= R[blr]; ++i) a[i] = tag[blr];
            } else {
                for (int i = L[blr]; i <= r; ++i) cnt += (a[i] == c);
            }
            for (int i = L[blr]; i <= r; ++i) a[i] = c;
            rebuild(blr);
            for (int i = bll + 1; i < blr; ++i) {
                if (istag[i]) {
                    cnt += len * (tag[i] == c);
                } else {
                    cnt += upper_bound(e[i].begin(), e[i].end(), c) - lower_bound(e[i].begin(), e[i].end(), c);
                }
                istag[i] = true; tag[i] = c;
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}
  • Post title：分块
  • Post author：Eva.Q
  • Create time：2023-08-26 21:40:05
  • Post link：https://qyy/2023/08/26/Algorithm/分块/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.