分块就是将一段数据分成一些小块， 对每个块单独处理使其不超过时间限制, 分块更多是一种思想，他介于线段树和树状数组之间。

一.给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，区间求和。

输入格式

第一行输入一个数字 n。

第二行输入 n 个数字，第 i 个数字为 a_i，以空格隔开。

接下来输入 n 行询问，每行输入四个数字 \mathrm{opt}、l、r、c，以空格隔开。

若 \mathrm{opt} = 0，表示将位于 [l, r] 的之间的数字都加 c。

若 \mathrm{opt} = 1，表示询问位于 [l, r] 的所有数字的和 \bmod (c+1)。

思路 :

  • 将数组分块每次加的时候，如果L与R在同一块里面，直接遍历该数组，最差时间复杂度O(nsqrt(n))，如果不是
    则将与左右两个块相同的数组内数字直接操作，将两个之间的用一个类似Lazytag的数组保存修改两量，

  • 同理对于查询时候，如果L与R属于同一个块，则直接遍历，最差时间复杂度是O(nsqrt(n))

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 n;
    cin >> n;

    i64 len = sqrt(n);
    vector<i64> a(n + 1), b(n + 1), f(n + 1), p(n + 1);
    for (i64 i = 1; i <= n; i++) {
        cin >> a[i];
        f[i] = (i - 1) / len + 1;
        b[f[i]] += a[i];
    }

    auto add = [&](i64 l, i64 r, i64 c) -> void {
        i64 g = f[l], h = f[r];
        if (g == h) {
            for (i64 i = l; i <= r; i++) {
                a[i] += c;
                b[f[i]] += c;
            }
        } else {
            for (i64 i = l; f[i] == f[l]; i++) {
                a[i] += c;
                b[f[i]] += c;
            }

            for (i64 i = r; f[i] == f[r]; i--) {
                a[i] += c;
                b[f[i]] += c;
            }

            for (i64 i = f[l] + 1; i < f[r]; i++) {
                p[i] += c;
            }
        }
    };

    auto query = [&](i64 l, i64 r, i64 c) -> i64 {
        if (f[l] == f[r]) {
            i64 sum = 0;
            for (i64 i = l; i <= r; i++) {
                sum = (sum + a[i] + p[f[i]]) % (c + 1);
            }
            return sum;
        } else {
            i64 sum = 0;
            for (i64 i = l; f[i] == f[l]; i++) {
                sum = (sum + a[i] + p[f[i]]) % (c + 1);
            }

            for (i64 j = r; f[j] == f[r]; j--) {
                sum = (sum + a[j] + p[f[j]]) % (c + 1);
            }

            for (i64 i = f[l] + 1; i < f[r]; i++) {
                sum = (sum + b[i] + p[i] * len) % (c + 1);
            }
            return sum;
        }
    };

    for (i64 i = 1; i <= n; i++) {
        i64 opt, l, r, c;
        cin >> opt >> l >> r >> c;

        if (opt == 0) {
            add(l, r, c);
        } else {
            cout << query(l, r, c) << '\n';
        }
    }

    return 0;
}

二. 给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的元素个数。

输入格式

第一行输入一个数字 n。

第二行输入 n 个数字，第 i 个数字为 a_i，以空格隔开。

接下来输入 n 行询问，每行输入四个数字 \mathrm{opt}、l、r、c，以空格隔开。

若 \mathrm{opt} = 0，表示将位于 [l, r] 的之间的数字都加 c。

若 \mathrm{opt} = 1，表示询问 [l, r] 中，小于 c^2 的数字的个数。

输出格式

对于每次询问，输出一行一个数字表示答案。

样例

输入复制

1
2
3
4
5
6
4
1 2 2 3
0 1 3 1
1 1 3 2
1 1 4 1
1 2 3 2

输出复制

1
2
3
3
0
2

数据范围与提示

对于 100\% 的数据，1 \leq n \leq 50000, -2^{31} \leq \mathrm{others}、\mathrm{ans} \leq 2^{31}-1。

思路
一样分块后：
加法时：

         - 当$id[l] == id[r]$ 时候直接暴力遍历，最坏复杂度O\(nsqrt\(n\)\)
         - 当$id[l] != id[r]$ 时候： 先处理两个裂块， 暴力维护。对于完整的块，每个块设置一个复制数组，操作后对这个块内进行sort， 时间复杂度$O(log(sqrt(n))$ 套个n后也可以过。
    询问时：
          - 当$id[l] == id[r]$ 时候直接暴力遍历，最坏复杂度O\(nsqrt\(n\)\)
          - 当$id[l] != id[r]$ 时候： 先处理两个裂块， 暴力维护。对于完整的块，块内二分单调复制数组b，找到块内比$c*c$ 小的数字个数。 

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    int len = sqrt(n);
    vector<i64> a(n + 1), b(n + 1), id(n + 1), g(n + 1), cnt(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        id[i] = (i - 1) / len + 1;
        b[i] = a[i];
    }

    auto work = [&](int id) -> void {
        int st = 1 + (id - 1) * len;
        for (int i = st; i < min(n + 1, st + len); i++) {
            b[i] = a[i];
        }
        sort(b.begin() + st, min(b.end(), b.begin() + st + len));
    };

    for (int i = 1; i <= n; i += len) {
        work(id[i]);
    }

    auto add = [&](int l, int r, i64 c) -> void {
        if (id[l] == id[r]) {
            for (int i = l; i <= r; i++) {
                a[i] += c;
            }
            work(id[l]);
        } else {
            for (int i = l; id[l] == id[i]; i++) {
                a[i] += c;
            }
            work(id[l]);

            for (int i = r; id[r] == id[i]; i--) {
                a[i] += c;
            }
            work(id[r]);

            for (int i = id[l] + 1; i < id[r]; i++) {
                g[i] += c;
            }
        }
    };

    auto query = [&](int l, int r, i64 c) -> int {
        if (id[l] == id[r]) {
            int sum = 0;
            for (int i = l; i <= r; i++) {
                if (a[i] + g[id[i]] < c) {
                    sum++;
                }
            }
            return sum;
        } else {
            int sum = 0;
            for (int i = l; id[i] == id[l]; i++) {
                if (a[i] + g[id[i]] < c) {
                    sum++;
                }
            }
            for (int i = r; id[i] == id[r]; i--) {
                if (a[i] + g[id[i]] < c) {
                    sum++;
                }
            }

            for (int i = id[l] + 1; i < id[r]; i++) {
                int l = 1 + (i - 1) * len, r = i * len;
                int ls = l;
                while (l <= r) {
                    int mid = (l + r) >> 1;
                    if (g[id[mid]] + b[mid] < c) {
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                int res = max(0, r - ls + 1);
                sum += res;
            }
            return sum;
        }
    };  

    for (int i = 1; i <= n; i++) {
        i64 opt, l, r, c;
        cin >> opt >> l >> r >> c;

        if (opt == 0) {
            add(l, r, c);
        } else {
            cout << query(l, r, c * c) << '\n';
        }
    }

    return 0;
}

三. 区间加法，询问区间内小于某个值 x 的前驱（比其小的最大元素）。

题目描述

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，询问区间内小于某个值 x 的前驱（比其小的最大元素）。

输入格式

第一行输入一个数字 n。

第二行输入 n 个数字，第 i 个数字为 a_i，以空格隔开。

接下来输入 n 行询问，每行输入四个数字 \mathrm{opt}、l、r、c，以空格隔开。

若 \mathrm{opt} = 0，表示将位于 [l, r] 的之间的数字都加 c。

若 \mathrm{opt} = 1，表示询问 [l, r] 中 c 的前驱的值（不存在则输出 -1）。

输出格式

对于每次询问，输出一行一个数字表示答案。

样例

输入复制

1
2
3
4
5
6
4
1 2 2 3
0 1 3 1
1 1 4 4
0 1 2 2
1 1 2 4

输出复制

1
2
3
-1

数据范围与提示

对于 100\% 的数据，1 \leq n \leq 100000, -2^{31} \leq \mathrm{others}、\mathrm{ans} \leq 2^{31}-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
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 n;
    cin >> n;

    i64 len = sqrt(n);
    vector<i64> a(n + 1), b(n + 1), g(n + 1), id(n + 1);
    for (i64 i = 1; i <= n; i++) {
        cin >> a[i];
        id[i] = (i - 1) / len + 1;
    }

    auto work = [&](i64 id) -> void {
        i64 st = 1 + (id - 1) * len;
        for (i64 i = st; i < min(n + 1, st + len); i++) {
            b[i] = a[i];
        }
        sort(b.begin() + st, min(b.end(), b.begin() + st + len));
    };  

    for (int i = 1; i <= n; i += len) {
        work(id[i]);
    }

    auto add = [&](i64 l, i64 r, i64 c) -> void {
        if (id[l] == id[r]) {
            for (i64 i = l; i <= r; i++) {
                a[i] += c;
            }
            work(id[l]);
        } else {
            for (i64 i = l; id[i] == id[l]; i++) {
                a[i] += c;
            }
            work(id[l]);

            for (i64 i = r; id[i] == id[r]; i--) {
                a[i] += c;
            }
            work(id[r]);

            for (i64 i = id[l] + 1; i < id[r]; i++) {
                g[i] += c;
            }
        }
    };

    auto query = [&](i64 l, i64 r, i64 c) -> i64 {
        if (id[l] == id[r]) {
            i64 ans = -1;
            for (i64 i = l; i <= r; i++) {
                if (a[i] + g[id[i]] < c) {
                    ans = max(ans, a[i] + g[id[i]]);
                }
            }
            return ans;
        } else {
            i64 ans = -1;
            for (i64 i = l; id[l] == id[i]; i++) {
                if (a[i] + g[id[i]] < c) {
                    ans = max(ans, a[i] + g[id[i]]);
                }
            }

            for (i64 i = r; id[i] == id[r]; i--) {
                if (a[i] + g[id[i]] < c) {
                    ans = max(ans, a[i] + g[id[i]]);
                }
            }

            for (i64 i = id[l] + 1; i < id[r]; i++) {
                i64 l = 1 + (i - 1) * len, r = i * len;
                i64 mid;
                while (l <= r) {
                    mid = (l + r) >> 1;
                    if (b[mid] + g[id[mid]] < c) {
                        ans = max(ans, b[mid] + g[id[mid]]);
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
            }
            return ans;
        }
    };

    for (i64 i = 1; i <= n; i++) {
        i64 opt, l, r, c;
        cin >> opt >> l >> r >> c;

        if (opt == 1) {
            cout << query(l, r, c) << '\n';
        } else {
            add(l, r, c);
        }
    }
    return 0;
}

数列4：开方，区间求和

给出一个长为 n 的数列 a_1 \ldots a_n，以及 n 个操作，操作涉及区间开方，区间求和。

输入格式

第一行输入一个数字 n。

第二行输入 n 个数字，第 i 个数字为 a_i，以空格隔开。

接下来输入 n 行询问，每行输入四个数字 \mathrm{opt}, l, r, c，以空格隔开。

若 \mathrm{opt} = 0，表示将位于 [l, r] 的之间的数字都开方。对于区间中每个 a_i(l\le i\le r),\: a_i \leftarrow \left\lfloor \sqrt{a_i}\right\rfloor

若 \mathrm{opt} = 1，表示询问位于 [l, r] 的所有数字的和。

思路：

对于1e9范围内的整数，开方最多7次就会变成1， 和线段树一样，如果区间内所有都是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
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<i64> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int len = sqrt(n);
    int siz = n / len + ((n % len) ? 1 : 0);
    //cerr << siz << '\n';
    vector<i64> b(n + 1), id(n + 1), c(siz + 1), ov(siz + 1);
    for (int i = 1; i <= n; i++) {
        id[i] = (i - 1) / len + 1;
        c[id[i]]++;
        b[id[i]] += a[i];
    }   

    for (int i = 1; i <= n; i++) {
        if (a[i] == 1) {
            ov[id[i]]++; 
        }
    }

    auto f = [&](int l, int r) -> void {
        if (id[l] == id[r]) {
            for (int i = l; i <= r; i++) {
                if (a[i] != 1) {
                    b[id[i]] -= a[i];
                    a[i] = (i64)sqrt(a[i]);
                    b[id[i]] += a[i];

                    if (a[i] == 1) {
                        ov[id[i]]++;
                    }
                }
            }
            return;
        }
        for (int i = l; id[i] == id[l]; i++) {
            if (a[i] != 1) {
                b[id[i]] -= a[i];
                a[i] = (i64)sqrt(a[i]);
                b[id[i]] += a[i];

                if (a[i] == 1) {
                    ov[id[i]]++;
                }
            }
        }

        for (int i = r; id[i] == id[r]; i--) {
            if (a[i] != 1) {
                b[id[i]] -= a[i];
                a[i] = (i64)sqrt(a[i]);
                b[id[i]] += a[i];

                if (a[i] == 1) {
                    ov[id[i]]++;
                }
            }
        }

        for (int i = id[l] + 1; i < id[r]; i++) {
            if (ov[i] != c[i]) {
                //cerr << "F:" << i << ' ';
                for (int j = 1 + (i - 1) * len; j <= i * len; j++) {
                    //cout << id[j] << '\n';
                    if (a[j] != 1) {
                        b[id[j]] -= a[j];
                        a[j] = (int)sqrt(a[j]);
                        b[id[j]] += a[j];

                        if (a[j] == 1) {
                            ov[id[j]]++;
                        }
                    }
                }
            }
        }
    };

    auto query = [&](int l, int r) -> i64 {
        if (id[l] == id[r]) {
            i64 ans = 0;
            for (int i = l; i <= r; i++) {
                ans += a[i];
            }
            return ans;
        }
        i64 res = 0;
        for (int i = l; id[i] == id[l]; i++) {
            res += a[i];
        }

        for (int i = id[l] + 1; i < id[r]; i++) {
            res += b[i];
        }

        for (int i = r; id[i] == id[r]; i--) {
            res += a[i];
        }

        return res;
    };

    for (int i = 1; i <= n; i++) {
        int opt, l, r, c;
        cin >> opt >> l >> r >> c;

        if (opt == 0) {
            f(l, r);
        } else {
            cout << query(l, r) << '\n';
        }
    }

    return 0;
}