跳转至

块状数据结构

块状数组

模版
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
template<class T1, class T2>
struct Block {
    int B;
    vector<int> belong, size, st, ed;
    vector<T1> ainfo;
    vector<T2> binfo;
    Block(int n) {
        init(n);
    }
    void init(int n) {
        B = sqrt(n);
        st.resize(0);
        st.resize(B + 1);
        ed.resize(0);
        ed.resize(B + 1);
        size.resize(0);
        size.resize(B + 1);
        belong.resize(0);
        belong.resize(n + 1);
        ainfo.resize(0);
        ainfo.resize(n + 1);
        binfo.resize(0);
        binfo.resize(B + 1);
        int cnt = n / B;
        for (int i = 1 ; i <= B ; i++) {
            st[i] = cnt * (i - 1) + 1;
            ed[i] = cnt * i;
        }
        ed[B] = n;
        for (int i = 1 ; i <= B ; i++) {
            for (int j = st[i] ; j <= ed[i] ; j++) {
                belong[j] = i;
            }
            size[i] = ed[i] - st[i] + 1;
        }
    }
    void modify(int L, int R, int k) {
        int x = belong[L], y = belong[R];
        if (x == y) { // 位于同一块暴力修改
            for (int i = L ; i <= R ; i++) {

            }
            return;
        }
        for (int i = L ; i <= ed[x] ; i++) { // 暴力修改左边多出的点

        }
        for (int i = st[y] ; i <= R ; i++) { // 暴力修改右边多出的点

        }
        for (int i = x + 1 ; i <= y - 1 ; i++) { // 暴力修改中间所有完整块

        }
    }
    i64 query(int L, int R) {
        i64 res = 0;
        int x = belong[L], y = belong[R];
        if (x == y) { // 位于同一块暴力查询
            for (int i = L ; i <= R ; i++) {

            }
            return res;
        }
        for (int i = L ; i <= ed[x] ; i++) { // 暴力查询左边多出的点

        }
        for (int i = st[y] ; i <= R ; i++) { // 暴力查询右边多出的点

        }
        for (int i = x + 1 ; i <= y - 1 ; i++) { // 暴力查询中间所有完整块

        }
        return res;
    }
};
例题

#6280. 数列分块入门 4 - LibreOJ

操作一: 区间加 \(C\)

操作二: 查询区间和模 \(C+1\)

代码
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
108
109
110
111
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
template<class T1, class T2>
struct Block {
    int B;
    vector<int> belong, size, st, ed;
    vector<T1> ainfo;
    vector<T2> binfo;
    Block(int n) {
        init(n);
    }
    void init(int n) {
        B = sqrt(n);
        st.resize(0);
        st.resize(B + 1);
        ed.resize(0);
        ed.resize(B + 1);
        size.resize(0);
        size.resize(B + 1);
        belong.resize(0);
        belong.resize(n + 1);
        ainfo.resize(0);
        ainfo.resize(n + 1);
        binfo.resize(0);
        binfo.resize(B + 1);
        int cnt = n / B;
        for (int i = 1 ; i <= B ; i++) {
            st[i] = cnt * (i - 1) + 1;
            ed[i] = cnt * i;
        }
        ed[B] = n;
        for (int i = 1 ; i <= B ; i++) {
            for (int j = st[i] ; j <= ed[i] ; j++) {
                belong[j] = i;
            }
            size[i] = ed[i] - st[i] + 1;
        }
    }
    void modify(int L, int R, i64 k) {
        int x = belong[L], y = belong[R];
        if (x == y) { // 位于同一块暴力修改
            for (int i = L ; i <= R ; i++) {
                ainfo[i] += k;
                binfo[x].sum += k;
            }
            return;
        }
        for (int i = L ; i <= ed[x] ; i++) { // 暴力修改左边多出的点
            ainfo[i] += k;
            binfo[x].sum += k;
        }
        for (int i = st[y] ; i <= R ; i++) { // 暴力修改右边多出的点
            ainfo[i] += k;
            binfo[y].sum += k;
        }
        for (int i = x + 1 ; i <= y - 1 ; i++) { // 暴力修改中间所有完整块
            binfo[i].sum += k * size[i];
            binfo[i].delta += k;
        }
    }
    i64 query(int L, int R, int P) {
        i64 res = 0;
        int x = belong[L], y = belong[R];
        if (x == y) { // 位于同一块暴力查询
            for (int i = L ; i <= R ; i++) {
                res = (res + ainfo[i] + binfo[x].delta) % P;
            }
            return res;
        }
        for (int i = L ; i <= ed[x] ; i++) { // 暴力查询左边多出的点
            res = (res + ainfo[i] + binfo[x].delta) % P;
        }
        for (int i = st[y] ; i <= R ; i++) { // 暴力查询右边多出的点
            res = (res + ainfo[i] + binfo[y].delta) % P;
        }
        for (int i = x + 1 ; i <= y - 1 ; i++) { // 暴力查询中间所有完整块
            res = (res + binfo[i].sum) % P;
        }
        return res;
    }
};
struct Info {
    i64 sum, delta;
};
int main() {
    int n;
    cin >> n;
    Block<int, Info> b(n);
    for (int i = 1 ; i <= n ; i++) {
        int x;
        cin >> x;
        b.modify(i, i, x);
    }
    for (int i = 0 ; i < n ; i++) {
        int op, L, R, c;
        cin >> op >> L >> R >> c;
        if (op == 0) {
            b.modify(L, R, c);
        } else {
            cout << b.query(L, R, c + 1) << "\n";
        }
    }
    return 0;
}

P2801 教主的魔法 - 洛谷

操作一: 区间加

操作二: 查询区间大于等于 \(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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
template<class T1, class T2>
struct Block {
    int B;
    vector<int> belong, size, st, ed, sorted;
    vector<T1> ainfo;
    vector<T2> binfo;
    Block(int n) {
        init(n);
    }
    void init(int n) {
        B = sqrt(n);
        st.resize(0);
        st.resize(B + 1);
        ed.resize(0);
        ed.resize(B + 1);
        size.resize(0);
        size.resize(B + 1);
        belong.resize(0);
        belong.resize(n + 1);
        ainfo.resize(0);
        ainfo.resize(n + 1);
        binfo.resize(0);
        binfo.resize(B + 1);
        sorted.resize(0);
        sorted.resize(n + 1);
        int cnt = n / B;
        for (int i = 1 ; i <= B ; i++) {
            st[i] = cnt * (i - 1) + 1;
            ed[i] = cnt * i;
        }
        ed[B] = n;
        for (int i = 1 ; i <= B ; i++) {
            for (int j = st[i] ; j <= ed[i] ; j++) {
                belong[j] = i;
            }
            size[i] = ed[i] - st[i] + 1;
        }
    }
    void sort(int idx) {
        for (int i = st[idx] ; i <= ed[idx] ; i++) {
            sorted[i] = ainfo[i];
        }
        ::sort(begin(sorted) + st[idx], begin(sorted) + ed[idx] + 1);
    }
    void modify(int L, int R, int k) {
        int x = belong[L], y = belong[R];
        if (x == y) { // 位于同一块暴力修改
            for (int i = L ; i <= R ; i++) {
                ainfo[i] += k;
            }
            sort(x);
            return;
        }
        for (int i = L ; i <= ed[x] ; i++) { // 暴力修改左边多出的点
            ainfo[i] += k;
        }
        for (int i = st[y] ; i <= R ; i++) { // 暴力修改右边多出的点
            ainfo[i] += k;
        }
        for (int i = x + 1 ; i <= y - 1 ; i++) { // 暴力修改中间所有完整块
            binfo[i] += k;
        }
        sort(x);
        sort(y);
    }
    i64 query(int L, int R, int k) {
        i64 res = 0;
        int x = belong[L], y = belong[R];
        if (x == y) { // 位于同一块暴力查询
            for (int i = L ; i <= R ; i++) {
                if (ainfo[i] + binfo[x] >= k) {
                    res++;
                }
            }
            return res;
        }
        for (int i = L ; i <= ed[x] ; i++) { // 暴力查询左边多出的点
            if (ainfo[i] + binfo[x] >= k) {
                res++;
            }
        }
        for (int i = st[y] ; i <= R ; i++) { // 暴力查询右边多出的点
            if (ainfo[i] + binfo[y] >= k) {
                res++;
            }
        }
        for (int i = x + 1 ; i <= y - 1 ; i++) { // 暴力查询中间所有完整块
            res += ed[i] - (lower_bound(begin(sorted) + st[i], begin(sorted) + ed[i] + 1, k - binfo[i]) - begin(sorted)) + 1;
        }
        return res;
    }
};
int main() {
    int n, q;
    cin >> n >> q;
    Block<int, int> b(n);
    for (int i = 1 ; i <= n ; i++) {
        int x;
        cin >> x;
        b.ainfo[i] = x;
    }
    for (int i = 1 ; i <= b.B ; i++) {
        b.sort(i);
    }
    while (q--) {
        char ch;
        int L, R, k;
        cin >> ch >> L >> R >> k;
        if (ch == 'M') {
            b.modify(L, R, k);
        } else {
            cout << b.query(L, R, k) << "\n";
        }
    }
    return 0;
}

树分块

例题

P6177 Count on a tree II/【模板】树分块 - 洛谷

一棵树, 每个点都有点权, 多次查询 \(u\) 和 \(v\), 问 \(u\) 到 \(v\) 路径上的颜色数, 强制在线

代码
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
bitset<40000> bs[205][205], res;
vector<int> adj[40005];
int a[40005];
int deep[40005], fa[40005][17], mxdeep[40005];
int id[40005], rev[205], tot;
void dfs(int u, int p) {
    mxdeep[u] = deep[u] = deep[p] + 1;
    fa[u][0] = p;
    for (int i = 1 ; (1 << i) <= deep[u] ; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (auto &to : adj[u]) {
        if (to == p) continue;
        dfs(to, u);
        mxdeep[u] = max(mxdeep[u], mxdeep[to]);
    }
    // 选择点个数超过 200 的作为关键点, 以保证期望距离 <= 200
    if (mxdeep[u] - deep[u] >= 200 && u != 1) {
        id[u] = ++tot;
        rev[tot] = u;
        mxdeep[u] = deep[u];
    }
}
int ttot, top, st[40005], up[40005];
void build(int u, int p) {
    if (id[u] != 0) {
        // u 是关键点
        top = fa[u][0];
        bs[st[ttot]][id[u]][a[u]] = 1;
        while (id[top] == 0 && top != 0) {
            // 暴力跳到上一个关键点或者跳出去为止
            bs[st[ttot]][id[u]][a[top]] = 1;
            top = fa[top][0];
        }
        if (top != 0) {
            bs[st[ttot]][id[u]][a[top]] = 1;
        }
        // bs[a][b] 表示从关键点 b 到关键点 a 路径的颜色(包含点 a 和点 b)
        up[u] = rev[st[ttot]]; // up[u] 表示点 u 的上一个关键点
        st[++ttot] = id[u]; // 把当前关键点 u 入栈
        for (int i = ttot - 2 ; i >= 1 ; i--) { // 前缀和处理从当前关键点 u 到它前方关键点的颜色
            // bs[st[i]][st[ttot - 1]] 表示关键点 u 的前一个关键点到前方关键点 st[i] 的颜色
            // bs[st[ttot - 1]][id[u]] 表示关键点 u 到前一个关键点的颜色
            // bs[st[i]][id[u]]        表示关键点 u 到前方关键点 st[i] 的颜色
            bs[st[i]][id[u]] = bs[st[i]][st[ttot - 1]] | bs[st[ttot - 1]][id[u]];
        }
    }
    for (auto &to : adj[u]) {
        if (to == p) continue;
        build(to, u);
    }
    if (id[u] != 0) {
        // 关键点 u 出栈
        ttot--;
    }
}
int LCA(int x, int y) {
    if (deep[x] < deep[y]) swap(x, y);
    for (int i = 16 ; i >= 0 ; i--) {
        if (deep[fa[x][i]] < deep[y]) continue;
        x = fa[x][i];
    }
    if (x == y) return x;
    for (int i = 16 ; i >= 0 ; i--) {
        if (fa[x][i] == fa[y][i]) continue;
        x = fa[x][i];
        y = fa[y][i];
    }
    return fa[x][0];
}
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> idx;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        idx.push_back(a[i]);
    }
    sort(begin(idx), end(idx));
    idx.resize(unique(begin(idx), end(idx)) - begin(idx));
    for (int i = 1 ; i <= n ; i++) {
        a[i] = lower_bound(begin(idx), end(idx), a[i]) - begin(idx);
    }
    for (int i = 1 ; i < n ; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    id[1] = ++tot;
    rev[tot] = 1;
    dfs(1, 0);
    build(1, 0);
    int ans = 0;
    for (int i = 1 ; i <= m ; i++) {
        int x, y;
        cin >> x >> y;
        x ^= ans;
        int z = LCA(x, y);
        res.reset();
        while (id[x] == 0 && x != z) {
            // 暴力跳到上一个关键点或者 z 为止
            res[a[x]] = 1;
            x = fa[x][0];
        }
        while (id[y] == 0 && y != z) {
            // 暴力跳到上一个关键点或者 z 为止
            res[a[y]] = 1;
            y = fa[y][0];
        }
        if (x != z) {
            int k = x;
            while (deep[up[x]] >= deep[z]) {
                // 暴力跳到离 z 最近且在z下方的关键点
                x = up[x];
            }
            if (k != x) {
                // 小优化, 如果没有跳就不用操作
                res |= bs[id[x]][id[k]];
            }
            while (x != z) {
                // 暴力跳到 z
                res[a[x]] = 1;
                x = fa[x][0];
            }
        }
        if (y != z) {
            int k = y;
            while (deep[up[y]] >= deep[z]) {
                // 暴力跳到离 z 最近且在z下方的关键点
                y = up[y];
            }
            if (k != y) {
                // 小优化, 如果没有跳就不用操作
                res |= bs[id[y]][id[k]];
            }
            while (y != z) {
                // 暴力跳到 z
                res[a[y]] = 1;
                y = fa[y][0];
            }
        }
        // 加上 z
        res[a[z]] = 1;
        ans = res.count();
        cout << ans << "\n";
    }
    return 0;
}