跳转至

分块

序列分块

  • 对于区修区查，分块可以实现 \(O(\sqrt n)\) 修改，\(O(\sqrt n)\) 查询的时间复杂度；
  • 对于单修区查和区修单查，可以做到 \(O(1)\) 修改，\(O(\sqrt n)\) 查询的时间复杂度；或 \(O(\sqrt n)\) 修改，\(O(1)\) 查询的时间复杂度；

有些算法的修改操作数量和查询操作数量并不同阶，比如莫队。它的修改操作数量约是查询操作数量的 \(\sqrt 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
 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
#include<cstdio>
#include<cmath>
#include<ctype.h>
#define ll long long
using namespace std;
const int N = 1E5 + 10;
const int N2 = 3.2E2 + 10;

struct my_istream {
    template<typename _Tp>
    inline my_istream& operator>>(_Tp &x) {
        char ch;
        bool flag = false;
        while(!isdigit(ch = getchar())) (ch == '-') && (flag = true);
        x = ch - 48;
        while(isdigit(ch = getchar())) x = x * 10 + ch - 48;
        flag && (x = -x);
        return *this;
    }
} cin;

struct my_ostream {
    int buf[60], nb;
    inline my_ostream() { nb = 0; }
    template<typename _Tp>
    inline my_ostream& operator<<(_Tp x) {
        while(x) buf[++nb] = x % 10, x /= 10;
        while(nb) putchar(buf[nb--] + 48);
        return *this;
    }
    inline my_ostream& operator<<(char c) {
        putchar(c);
        return *this;
    }
} cout;

int n, m;
ll a[N];

int blen, blo[N];
int len[N2], beg[N], ed[N];
ll sum[N2], tag[N2];

void build() {
    blen = sqrt(n);
    for(int i = 1; i <= n; i++) {
        blo[i] = (i + blen - 1) / blen;
        sum[blo[i]] += a[i];
        len[blo[i]]++;
    }
    for(int i = 1; i <= n; i++) {
        if(blo[i] == blo[i - 1]) beg[i] = beg[i - 1];
        else beg[i] = i;
    }
    ed[n] = n;
    for(int i = n - 1; i >= 1; i--) {
        if(blo[i] == blo[i + 1]) ed[i] = ed[i + 1];
        else ed[i] = i;
    }
}

void modify(int l, int r, ll k) {
    if(blo[l] == blo[r]) {
        sum[blo[l]] += k * (r - l + 1);
        for(int i = l; i <= r; i++) {
            a[i] += k;
        }
        return;
    }
    sum[blo[l]] += k * (ed[l] - l + 1);
    for(int i = l; i <= ed[l]; i++) {
        a[i] += k;
    }
    for(int i = blo[l] + 1; i < blo[r]; i++) {
        tag[i] += k;
        sum[i] += k * len[i];
    }
    sum[blo[r]] += k * (r - beg[r] + 1);
    for(int i = beg[r]; i <= r; i++) {
        a[i] += k;
    }
}

ll query(int l, int r) {
    ll res = 0;
    if(blo[l] == blo[r]) {
        for(int i = l; i <= r; i++) {
            res += a[i] + tag[blo[l]];
        }
        return res;
    }
    for(int i = l; i <= ed[l]; i++) {
        res += a[i] + tag[blo[l]];
    }
    for(int i = blo[l] + 1; i < blo[r]; i++) {
        res += sum[i];
    }
    for(int i = beg[r]; i <= r; i++) {
        res += a[i] + tag[blo[r]];
    }
    return res;
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    build();

    while(m--) {
        int op, x, y;
        ll k;
        cin >> op;
        if(op == 1) {
            cin >> x >> y >> k;
            modify(x, y, k);
        } else {
            cin >> x >> y;
            cout << query(x, y) << '\n';
        }
    }

    return 0;
}

值域分块

对于某些值域上的操作（例如，将区间中所有数字 \(x\) 修改为数字 \(y\)），可以使用值域分块求解。

P3834 【模板】可持久化线段树 2

题意

查询静态区间第 \(k\) 小。

考虑对值域分块，查询时先暴力求出答案在哪个大块中，然后暴力在大块中查询答案。这需要我们维护出区间中某一值域块中的数字数量 \(\sum_{i\in [l,r]}{[blo(a_i)=y]}\) 以及区间中某一个值出现的次数 \(\sum_{i\in [l,r]}{[a_i=y]}\)。

考虑进行序列分块。整块是容易维护的，只需记录 \(s_{1\ x,y}=\sum_{blo1(i)\le x}{[blo2(a_i)= y]}\) 和 \(s_{2\ x,y}=\sum_{blo1(i)\le x}{[a_i=y]}\)，占用 \(O(V\sqrt n)\) 的空间。考虑如何处理边角料，容易发现每次查询时边角料的大小不会超过 \(O(\sqrt n)\)。给边角料单独开两个桶 \(f_{1\ y}=\sum[a_i=y]\) 和 \(f_{2\ y}=\sum[blo2(a_i)=y]\)，暴力扫一遍边角料，统计出 \(f_1\) 和 \(f_2\)。查询时将边角料的贡献也加入即可。

时间复杂度 \(O\big(m\sqrt n + m\sqrt V\big)\)。

代码 
  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
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
const int N2 = 5e2 + 10;
const int V = 2e5;

struct my_istream {
    char ch;
    template<typename _Tp>
    inline my_istream& operator>>(_Tp& x) {
        while(!isdigit(ch = getchar_unlocked()));
        x = ch - 48;
        while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - 48;
        return *this;
    }
} fin;

struct my_ostream {
    char buf[60], nb;
    inline my_ostream() { nb = 0; }
    inline my_ostream& operator<<(char c) {
        putchar(c);
        return *this;
    }
    template<typename _Tp>
    inline my_ostream& operator<<(_Tp x) {
        do buf[++nb] = x % 10, x /= 10; while(x);
        while(nb) putchar(buf[nb--] + 48);
        return *this;
    }
} fout;

int n, m;
int a[N];

int num[N], nn;

void lisanhua() {
    for(int i = 1; i <= n; i++) num[++nn] = a[i];
    sort(num + 1, num + 1 + nn);
    nn = unique(num + 1, num + 1 + nn) - (num + 1);
    for(int i = 1; i <= n; i++) a[i] = lower_bound(num + 1, num + 1 + nn, a[i]) - num;
}

int blen, bcnt;
int blo[N], bg[N2], ed[N2];
int s1[N2][N], s2[N2][N2];

int f1[N], f2[N2];
int sta[2 * N2], top;
int query(int l, int r, int k) {
    if(blo[l] == blo[r]) {
        for(int i = l; i <= r; i++) {
            sta[++top] = a[i];
            ++f1[a[i]];
            ++f2[blo[a[i]]];
        }
        l = blo[l];
        r = l - 1;
    } else {
        if(l != bg[blo[l]]) {
            for(int i = l; i <= ed[blo[l]]; i++) {
                sta[++top] = a[i];
                ++f1[a[i]];
                ++f2[blo[a[i]]];
            }
            l = ed[blo[l]] + 1;
        }
        if(r != ed[blo[r]]) {
            for(int i = bg[blo[r]]; i <= r; i++) {
                sta[++top] = a[i];
                ++f1[a[i]];
                ++f2[blo[a[i]]];
            }
            r = bg[blo[r]] - 1;
        }
        l = blo[l];
        r = blo[r];
    }
    int res = 0, sum = 0;
    while(true) {
        if(sum + s2[r][res + 1] - s2[l - 1][res + 1] + f2[res + 1] >= k) break;
        ++res;
        sum += s2[r][res] - s2[l - 1][res] + f2[res];
    }
    res = ed[res];
    while(true) {
        ++res;
        if(sum + s1[r][res] - s1[l - 1][res] + f1[res] >= k) break;
        sum += s1[r][res] - s1[l - 1][res] + f1[res];
    }
    while(top) {
        f1[sta[top]] = 0;
        f2[blo[sta[top--]]] = 0;
    }
    return num[res];
}

int main() {

    fin >> n >> m;
    for(int i = 1; i <= n; i++) fin >> a[i];

    lisanhua();

    blen = sqrt(n);
    bcnt = (n + blen - 1) / blen;
    for(int i = 1; i <= n; i++) blo[i] = (i + blen - 1) / blen;
    for(int i = 1; i <= bcnt; i++) bg[i] = (i - 1) * blen + 1;
    for(int i = 1; i <= bcnt; i++) ed[i] = min(n, i * blen);

    for(int i = 1; i <= n; i++) {
        ++s1[blo[i]][a[i]];
        ++s2[blo[i]][blo[a[i]]];
    }

    for(int i = 1; i <= bcnt; i++) {
        for(int j = 1; j <= n; j++) s1[i][j] += s1[i - 1][j];
        for(int j = 1; j <= bcnt; j++) s2[i][j] += s2[i - 1][j];
    }

    while(m--) {
        int l, r, k;
        fin >> l >> r >> k;
        fout << query(l, r, k) << '\n';
    }

    return 0;
}

P4119 [Ynoi2018] 未来日记

题意

给定一个长为 \(n\) 的序列。有 \(m\) 次操作：

  • 1 l r x y：把区间 \([l,r]\) 中所有数字 \(x\) 变成 \(y\)；
  • 2 l r k：查询区间 \([l,r]\) 中的 \(k\) 小值；

考虑修改操作：对于边角料，直接暴力修改即可；对于对于整块，我们可以直接修改前缀和数组 \(s_1\) 和 \(s_2\) 中所有受到影响的位置。

然而查询操作的边角料会用到原数组 \(a\)。如何保证查询时边角料内的 \(a\) 数组最新？

如果枚举所有修改操作，将它们按顺序更新在当前块上，则无异于暴力修改，最劣时间复杂度将达到 \(O(n^2)\)。

考虑如何将同一个块的多次修改合并到一起，实现单次单块 \(O(\sqrt n)\) 的快速重构。由于无需考虑下标限制，整块的修改操作等价于染色问题（将所有数值 \(a\) 更改为数值 \(b\)），可以直接使用并查集维护。重构时暴力查询每个点在哪个集合即可。

具体的，我们始终保持并查集的根节点 \(rt\) 的 \(a[rt]\) 处于最新状态。find(x) 找到根后，根的值就是当前节点的值。

代码 
  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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
#include<iostream>
#include<cmath>
using namespace std;
const int N = 1e5 + 10;
const int N2 = 500;
const int V = 1e5;

struct fast_istream {
    char ch;
    template<typename _Tp>
    inline fast_istream& operator>>(_Tp &x) {
        while(!isdigit(ch = getchar_unlocked()));
        x = ch - 48;
        while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - 48;
        return *this;
    }
} fin;

struct fast_ostream {
    int buf[60], nb;
    inline fast_ostream& operator<<(char c) {
        putchar_unlocked(c);
        return *this;
    }
    template<typename _Tp>
    inline fast_ostream& operator<<(_Tp x) {
        do buf[++nb] = x % 10, x /= 10; while(x);
        while(nb) putchar_unlocked(buf[nb--] + 48);
        return *this;
    }
} fout;

int n, m;
int a[N];

int blen1, bcnt1, blo1[N];
int bg1[N2], ed1[N2];

int blen2, bcnt2, blo2[N];
int bg2[N2], ed2[N2];

int s1[N2][N], s2[N2][N2];

int rt[N2][N], fa[N];
inline int find(int x) {
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
inline void merge(int x, int y) {
    fa[find(y)] = find(x);
}
// 将 p 加入 v 并查集中
inline void insert(int b, int v, int p) {
    if(rt[b][v] == 0) {
        rt[b][v] = p;
    } else merge(rt[b][v], p);
}

inline void update_unf_arr(int b) {
    int l = bg1[b], r = ed1[b];
    for(int i = l; i <= r; i++) {
        a[i] = a[find(i)];
    }
}

int buf[N2], nb;
inline void rebuild_unf(int b, int x, int y) {
    rt[b][x] = 0;
    rt[b][y] = 0;
    int l = bg1[b], r = ed1[b];
    for(int i = l; i <= r; i++) {
        if(a[i] == x || a[i] == y) fa[i] = i, buf[++nb] = i;
    }
    for(int i = 1; i <= nb; i++) {
        insert(b, a[buf[i]], buf[i]);
    }
    nb = 0;
}

inline void init() {
    blen1 = sqrt(n);
    bcnt1 = (n + blen1 - 1) / blen1;
    for(int i = 1; i <= n; i++) blo1[i] = (i + blen1 - 1) / blen1;
    for(int i = 1; i <= bcnt1; i++) bg1[i] = (i - 1) * blen1 + 1;
    for(int i = 1; i <= bcnt1; i++) ed1[i] = i * blen1;
    ed1[bcnt1] = n;

    blen2 = sqrt(V);
    bcnt2 = (n + blen2 - 1) / blen2;
    for(int i = 1; i <= n; i++) blo2[i] = (i + blen2 - 1) / blen2;
    for(int i = 1; i <= bcnt2; i++) bg2[i] = (i - 1) * blen2 + 1;
    for(int i = 1; i <= bcnt2; i++) ed2[i] = i * blen2;
    ed2[bcnt2] = V;

    for(int i = 1; i <= n; i++) {
        ++s1[blo1[i]][a[i]];
        ++s2[blo1[i]][blo2[a[i]]];
    }

    for(int i = 1; i <= bcnt1; i++) {
        for(int j = 1; j <= V; j++) s1[i][j] += s1[i - 1][j];
        for(int j = 1; j <= bcnt2; j++) s2[i][j] += s2[i - 1][j];
    }

    for(int i = 1; i <= n; i++) fa[i] = i;
    for(int i = 1; i <= n; i++) insert(blo1[i], a[i], i);
}

inline void baoli(int l, int r, int x, int y) {
    int bx = blo2[x], by = blo2[y], tmp = 0;
    int b = blo1[l];
    update_unf_arr(b);
    for(int i = l; i <= r; i++) {
        if(a[i] == x) {
            a[i] = y;
            tmp++;
        }
    }
    for(int i = b; i <= bcnt1; i++) {
        s1[i][x] = s1[i][x] - tmp;
        s1[i][y] = s1[i][y] + tmp;
        s2[i][bx] = s2[i][bx] - tmp;
        s2[i][by] = s2[i][by] + tmp;
    }
    rebuild_unf(b, x, y);
}

inline void modify(int l, int r, int x, int y) {
    int bx = blo2[x], by = blo2[y], cnt = 0;
    if(blo1[l] == blo1[r]) {
        baoli(l, r, x, y);
        return;
    }
    if(l != bg1[blo1[l]]) {
        baoli(l, ed1[blo1[l]], x, y);
        l = ed1[blo1[l]] + 1;
    }
    if(r != ed1[blo1[r]]) {
        baoli(bg1[blo1[r]], r, x, y);
        r = bg1[blo1[r]] - 1;
    }
    l = blo1[l];
    r = blo1[r];
    for(int b = l; b <= r; b++) {
        int tmp = cnt;
        cnt += s1[b][x] - s1[b - 1][x];
        s1[b - 1][x] -= tmp;
        s1[b - 1][y] += tmp;
        s2[b - 1][bx] -= tmp;
        s2[b - 1][by] += tmp;
        if(cnt == tmp) continue;
        if(rt[b][y] == 0) {
            rt[b][y] = rt[b][x];
            a[find(rt[b][y])] = y;
        } else merge(rt[b][y], rt[b][x]);
        rt[b][x] = 0;
    }
    for(int i = r; i <= bcnt1; i++) {
        s1[i][x] = s1[i][x] - cnt;
        s1[i][y] = s1[i][y] + cnt;
        s2[i][bx] = s2[i][bx] - cnt;
        s2[i][by] = s2[i][by] + cnt;
    }
}

int f1[V], f2[N2];
int sta[2 * N2], top;
int query(int l, int r, int k) {
    int bl, br;
    if(blo1[l] == blo1[r]) {
        update_unf_arr(blo1[l]);
        bl = blo1[l] + 1;
        br = blo1[l];
        for(int i = l; i <= r; i++) {
            ++f1[a[i]];
            ++f2[blo2[a[i]]];
            sta[++top] = a[i];
        }
    } else {
        if(l != bg1[blo1[l]]) {
            update_unf_arr(blo1[l]);
            for(int i = l; i <= ed1[blo1[l]]; i++) {
                ++f1[a[i]];
                ++f2[blo2[a[i]]];
                sta[++top] = a[i];
            }
            l = ed1[blo1[l]] + 1;
        }
        if(r != ed1[blo1[r]]) {
            update_unf_arr(blo1[r]);
            for(int i = bg1[blo1[r]]; i <= r; i++) {
                ++f1[a[i]];
                ++f2[blo2[a[i]]];
                sta[++top] = a[i];
            }
            r = bg1[blo1[r]] - 1;
        }
        bl = blo1[l], br = blo1[r];
    }
    int res = 0, sum = 0;
    while(res <= bcnt2) {
        if(sum + s2[br][res + 1] - s2[bl - 1][res + 1] + f2[res + 1] >= k) {
            break;
        }
        ++res;
        sum += s2[br][res] - s2[bl - 1][res] + f2[res];
    }
    res = ed2[res];
    while(true) {
        ++res;
        if(sum + s1[br][res] - s1[bl - 1][res] + f1[res] >= k) {
            break;
        }
        sum += s1[br][res] - s1[bl - 1][res] + f1[res];
    }
    while(top) {
        f1[sta[top]] = 0;
        f2[blo2[sta[top]]] = 0;
        --top;
    }
    return res;
}

int main() {

    fin >> n >> m;
    for(int i = 1; i <= n; i++) fin >> a[i];

    init();

    while(m--) {
        int op, l, r, k, x, y;
        fin >> op >> l >> r;
        if(op == 1) {
            fin >> x >> y;
            if(x == y) continue;
            modify(l, r, x, y);
        } else {
            fin >> k;
            fout << query(l, r, k) << '\n';
        }
    }

    return 0;
}

 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
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
const int N2 = 320;
const int V = 1e5;

struct fast_istream {
    char ch;
    template<typename _Tp>
    inline fast_istream& operator>>(_Tp &x) {
        while(!isdigit(ch = getchar_unlocked()));
        x = ch - 48;
        while(isdigit(ch = getchar_unlocked())) x = x * 10 + ch - 48;
        return *this;
    }
} fin;

struct fast_ostream {
    int buf[60], nb;
    inline fast_ostream& operator<<(char c) {
        putchar(c);
        return *this;
    }
    template<typename _Tp>
    inline fast_ostream& operator<<(_Tp x) {
        do buf[++nb] = x % 10, x /= 10; while(x);
        while(nb) putchar(buf[nb--] + 48);
        return *this;
    }
} fout;

int n, m;
int a[N];

inline void modify(int l, int r, int x, int y) {
    for(int i = l; i <= r; i++) {
        if(a[i] == x) a[i] = y;
    }
}

int num[N];
int query(int l, int r, int k) {
    for(int i = l; i <= r; i++) {
        num[i - l + 1] = a[i];
    }
    int len = r - l + 1;
    sort(num + 1, num + 1 + len);
    return num[k];
}

int main() {

    fin >> n >> m;
    for(int i = 1; i <= n; i++) fin >> a[i];

    while(m--) {
        int op, l, r, k, x, y;
        fin >> op >> l >> r;
        if(op == 1) {
            fin >> x >> y;
            if(x == y) continue;
            modify(l, r, x, y);
        } else {
            fin >> k;
            fout << query(l, r, k) << '\n';
        }
    }

    return 0;
}

 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
#include "testlib.h"
using namespace std;

int n = 500;
int m = 400;
int v = 5;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cout << n << ' ' << m << '\n';
    for(int i = 1; i <= n; i++) {
        cout << rng() % v + 1 << ' ';
    }
    cout << '\n';

    for(int i = 1; i <= m; i++) {
        int l = rng() % n + 1;
        int r = rng() % n + 1;
        if(l > r) swap(l, r);
        if(rng() & 1) {
            int x = rng() % v + 1;
            int y = rng() % v + 1;
            cout << 1 << ' ' << l << ' ' << r << ' ' << x << ' ' << y << '\n';
        } else {
            int k = rng() % (r - l + 1) + 1;
            cout << 0 << ' ' << l << ' ' << r << ' ' << k << '\n';
        }
    }

    return 0;
}