分块是一种很灵活的数据结构，能用 $sqrt$ 的时间解决 $log$ 不能解决的事情。

以下题目按洛谷颜色排列 $\color{red}{qwq}$

P2464 [SDOI2008] 郁闷的小 J

题意简述

查询区间内某个数的出现次数，包含单点修改操作。

思路

$f_{i,j}$ 为 $j$ 这个数在前 $i$ 块内的出现次数，维护这个东西即可。

代码

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
#include<bits/stdc++.h>
using LL = long long;

const int N = 1e5 + 5, M = 320;
int n, q, a[N], b[N * 2], cur;
struct Query {
    std::string op;
    int x, y, p;
} Q[N];
int num, st[M], ed[M], belong[N], f[M][N];
int calc(int l, int r, int pos) {
    int x = belong[l], y = belong[r];
    if (x == y) {
        int res = 0;
        for (int i = l; i <= r; ++ i) {
            res += a[i] == pos;
        }
        return res;
    }
    int res = f[y - 1][pos] - f[x][pos];
    for (int i = l; i <= ed[x]; ++ i) {
        res += a[i] == pos;
    }
    for (int i = st[y]; i <= r; ++ i) {
        res += a[i] == pos;
    }
    return res;
}
signed main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
    std::cin >> n >> q;
    for (int i = 1; i <= n; ++ i) {
        std::cin >> a[i];
    }
    std::copy(a + 1, a + n + 1, b + 1);
    cur = n;
    for (int i = 1; i <= q; ++ i) {
        std::string op;
        int x, y, p;
        std::cin >> op;
        if (op == "Q") {
            std::cin >> x >> y >> p;
            Q[i] = {op, x, y, p};

        } else {
            std::cin >> x >> p;
            Q[i] = {op, x, 0, p};
            b[++ cur] = p;
        }
    }
    std::sort(b + 1, b + cur + 1);
    cur = std::unique(b + 1, b + cur + 1) - (b + 1);
    for (int i = 1; i <= n; ++ i) {
        a[i] = std::lower_bound(b + 1, b + cur + 1, a[i]) - b;
    }
    num = sqrt(n);
    for (int i = 1; i <= num; ++ i) {
        st[i] = n / num * (i - 1) + 1;
        ed[i] = n / num * i;
    }
    ed[num] = n;
    for (int i = 1; i <= num; ++ i) {
        std::fill(belong + st[i], belong + ed[i] + 1, i);
        for (int j = st[i]; j <= ed[i]; ++ j) {
            ++ f[i][a[j]];
        }
        for (int j = 1; j <= cur; ++ j) {
            f[i][j] += f[i - 1][j];
        }
    }
    for (int i = 1; i <= q; ++ i) {
        auto [op, x, y, p] = Q[i];
        if (op == "Q") {
            int pos = std::lower_bound(b + 1, b + cur + 1, p) - b;
            std::cout << calc(x, y, pos) << '\n';
        } else {
            int pos = belong[x];
            int kk = std::lower_bound(b + 1, b + cur + 1, p) - b;
            for (int j = pos; j <= num; ++ j) {
                -- f[j][a[x]];
                ++ f[j][kk];
            }
            a[x] = kk;
        }
    }
    return 0;
}

P3396 哈希冲突

题意简述

给出长度为 $n$ 的序列 $A$ ，有若干次询问和修改，修改操作为将 $A_x=y$ ，查询操作为查询数组下标 $\mod x \equiv y$ 对应序列权值总和。

思路

这个题相对基础一些，考虑暴力查询

1
2
3
for (int i = y; i <= n; i += x) {
    ans += a[i];
}

这样的复杂度为 $\Theta(\frac{n}{x})$ ，与 $x$ 的大小成负相关，所以我们考虑根号分治，暴力查询 $x \geq \sqrt n$ 的答案，预处理$x < \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
#include<bits/stdc++.h>
using LL = long long;

const int N = 150005;
int n, q, a[N];
int sum[400][400];
signed main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
    std::cin >> n >> q;
    int m = sqrt(n);
    for (int i = 1; i <= n; ++ i) {
        std::cin >> a[i];
        for (int j = 1; j <= m; ++ j) {
            sum[j][i % j] += a[i];
        }
    }
    while (q -- ) {
        std::string op;
        int x, y;
        std::cin >> op >> x >> y;
        if (op == "A") {
            if (x <= m) {
                std::cout << sum[x][y] << '\n';
            } else {
                int ans = 0;
                for (int i = y; i <= n; i += x) {
                    ans += a[i];
                }
                std::cout << ans << '\n';
            }
        } else {
            for (int i = 1; i <= m; ++ i) {
                sum[i][x % i] -= a[x] - y;
            }
            a[x] = y;
        }
    }
    return 0;
}

P3203 [HNOI2010]弹飞绵羊

题意简述

给出长度为 $n$ 的数组，当你处于下标 $x$ 时，你能跳到下标为 $x+a_x$ 的地方。

每次询问当你处于下标 $k$ 时，跳到 $> n$ 的位置需要跳的次数，以及单点修改。

思路

我们考虑对块内的元素进行处理，设 $f_x$ 为 $x$ 第一次跳出它所属的块的下标， $g_x$ 为 $x$ 跳出它所属的块所需要跳的次数。

类似于并查集的路径压缩

1
2
3
4
5
6
7
8
9
for (int i = ed[x]; i >= st[x]; -- i) {
    if (i + a[i] > ed[x]) {
        f[i] = i + a[i];
        g[x] = 1;
    } else {
        f[i] = f[i + a[i]];
        g[x] = g[i + a[i]] + 1;
    }
}

查询时暴力往后跳即可

单点修改时，我们只需修改所属块内的信息

单次操作时间复杂度为 $\Theta(\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
#include<bits/stdc++.h>
using LL = long long;

const int N = 2e5 + 5, M = 450;
int n, q, a[N];
int num, st[M], ed[M], belong[N], step[N], to[N];
signed main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    std::cin >> n;
    for (int i = 1; i <= n; ++ i) {
        std::cin >> a[i];
    }
    num = sqrt(n);
    for (int i = 1; i <= num; ++ i) {
        st[i] = n / num * (i - 1) + 1;
        ed[i] = n / num * i;
    }
    ed[num] = n;
    for (int i = 1; i <= num; ++ i) {
        std::fill(belong + st[i], belong + ed[i] + 1, i);
        for (int j = ed[i]; j >= st[i]; -- j) {
            if (j + a[j] > ed[i]) {
                step[j] = 1;
                to[j] = j + a[j];
            } else {
                step[j] = step[j + a[j]] + 1;
                to[j] = to[j + a[j]];
            }
        }
    }
    std::cin >> q;
    while (q -- ) {
        int op, x, y;
        std::cin >> op >> x;
        ++ x;
        if (op == 2) {
            std::cin >> y;
            if (a[x] == y) {
                continue;
            }
            a[x] = y;
            for (int j = ed[belong[x]]; j >= st[belong[x]]; -- j) {
                if (j + a[j] > ed[belong[x]]) {
                    step[j] = 1;
                    to[j] = j + a[j];
                } else {
                    step[j] = step[j + a[j]] + 1;
                    to[j] = to[j + a[j]];
                }
            }
        } else {
            int res = 0;
            while (x <= n) {
                res += step[x];
                x = to[x];
            }
            std::cout << res << '\n';
        }
    }
    return 0;
}

P3730 曼哈顿交易

题意简述

查询区间出现次数第 $k$ 小的出现次数。

思路

第一反应，莫队套主席树？但是 $\Theta(n\sqrt n \log n)$ 的复杂度看着很不靠谱(卡卡常应该行?)所以只能另辟蹊径。

考虑值域分块，维护出现次数以及次数的个数，查询时扫描每个块，直到找到第 $k$ 小的次数。

代码

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
#include<bits/stdc++.h>
using LL = long long;

const int N = 1e5 + 5, M = 320;
int n, m, a[N], b[N], cur;
int block;
struct Query {
    int l, r, k, id;
    bool operator < (const Query &o) const {
        return l / block == o.l / block ? r != o.r && ((l / block) & 1) ^ (r < o.r) : l < o.l;
    }
} Q[N];
int num, st[M], ed[M], belong[N], siz[M];
int ans[N], cnt[N], val[N];
void add(int x) {
    -- val[x - 1];
    -- siz[belong[x - 1]];
    ++ val[x];
    ++ siz[belong[x]];
}
void del(int x) {
    -- val[x];
    -- siz[belong[x]];
    ++ val[x - 1];
    ++ siz[belong[x - 1]];
}
int query(int k) {
    for (int i = 1; i <= num; ++ i) {
        if (k > siz[i]) {
            k -= siz[i];
        } else {
            for (int j = st[i]; j <= ed[i]; ++ j) {
                if ((k -= val[j]) <= 0) {
                    return j;
                }
            }
        }
    }
    return -1;
}
signed main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
    std::cin >> n >> m;
    for (int i = 1; i <= n; ++ i) {
        std::cin >> a[i];
    }
    std::copy(a + 1, a + n + 1, b + 1);
    std::sort(b + 1, b + n + 1);
    cur = std::unique(b + 1, b + n + 1) - (b + 1);
    for (int i = 1; i <= n; ++ i) {
        a[i] = std::lower_bound(b + 1, b + cur + 1, a[i]) - b;
    }
    block = sqrt(n);
    for (int i = 1; i <= m; ++ i) {
        int l, r, k;
        std::cin >> l >> r >> k;
        Q[i] = {l, r, k, i};
    }
    std::sort(Q + 1, Q + m + 1);
    // 值域(出现次数)分块
    num = sqrt(n);
    for (int i = 1; i <= num; ++ i) {
        st[i] = n / num * (i - 1) + 1;
        ed[i] = n / num * i;
    }
    ed[num] = n;
    for (int i = 1; i <= num; ++ i) {
        std::fill(belong + st[i], belong + ed[i] + 1, i);
    }
    for (int i = 1, L = 1, R = 0; i <= m; ++ i) {
        auto &[l, r, k, id] = Q[i];
        while (L > l) {
            -- L;
            ++ cnt[a[L]];
            add(cnt[a[L]]);
        }
        while (R < r) {
            ++ R;
            ++ cnt[a[R]];
            add(cnt[a[R]]);
        }
        while (L < l) {
            del(cnt[a[L]]);
            -- cnt[a[L]];
            ++ L;
        }
        while (R > r) {
            del(cnt[a[R]]);
            -- cnt[a[R]];
            -- R;
        }
        ans[id] = query(k);
    }
    for (int i = 1; i <= m; ++ i) {
        std::cout << ans[i] << '\n';
    }
    return 0;
}

P4135 作诗

题意简述

查询区间出现次数为偶数的数的个数，强制在线。

思路

维护每个数相对于块的出现次数前缀和，暴力查询判断即可。

代码

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
#include<bits/stdc++.h>
using LL = long long;

const int N = 1e5 + 5;
int n, c, m, a[N], b[N], cur;
int num, st[320], ed[320], belong[N], f[320][320], g[320][N], cnt[N];
int calc(int l, int r) {
    int x = belong[l], y = belong[r];
    if (x == y) {
        for (int i = l; i <= r; ++ i) {
            cnt[a[i]] = 0;
        }
        int res = 0;
        for (int i = l; i <= r; ++ i) {
            ++ cnt[a[i]];
            if ((cnt[a[i]] & 1) && cnt[a[i]] > 1) {
                -- res;
            } else if (!(cnt[a[i]] & 1)) {
                ++ res;
            }
        }
        return res;
    }
    int res = f[x + 1][y - 1];
    for (int i = l; i <= ed[x]; ++ i) {
        cnt[a[i]] = 0;
    }
    for (int i = st[y]; i <= r; ++ i) {
        cnt[a[i]] = 0;
    }
    for (int i = l; i <= ed[x]; ++ i) {
        ++ cnt[a[i]];
        int k = cnt[a[i]] + g[y - 1][a[i]] - g[x][a[i]];
        if ((k & 1) && k > 1) {
            -- res;
        } else if (!(k & 1)) {
            ++ res;
        }
    }
    for (int i = st[y]; i <= r; ++ i) {
        ++ cnt[a[i]];
        int k = cnt[a[i]] + g[y - 1][a[i]] - g[x][a[i]];
        if ((k & 1) && k > 1) {
            -- res;
        } else if (!(k & 1)) {
            ++ res;
        }
    }
    return res;
}
signed main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    std::cin >> n >> c >> m;
    for (int i = 1; i <= n; ++ i) {
        std::cin >> a[i];
    }
    std::copy(a + 1, a + n + 1, b + 1);
    std::sort(b + 1, b + n + 1);
    cur = std::unique(b + 1, b + n + 1) - (b + 1);
    for (int i = 1; i <= n; ++ i) {
        a[i] = std::lower_bound(b + 1, b + cur + 1, a[i]) - b;
    }
    num = sqrt(n);
    for (int i = 1; i <= num; ++ i) {
        st[i] = n / num * (i - 1) + 1;
        ed[i] = n / num * i;
    }
    ed[num] = n;
    for (int i = 1; i <= num; ++ i) {
        for (int j = st[i]; j <= ed[i]; ++ j) {
            belong[j] = i;
            ++ g[i][a[j]];
        }
        for (int j = 1; j <= cur; ++ j) {
            g[i][j] += g[i - 1][j];
        }
    }
    for (int i = 1; i <= num; ++ i) {
        std::fill(cnt + 1, cnt + cur + 1, 0);
        for (int j = i; j <= num; ++ j) {
            int res = f[i][j - 1];
            for (int k = st[j]; k <= ed[j]; ++ k) {
                ++ cnt[a[k]];
                if ((cnt[a[k]] & 1) && cnt[a[k]] > 1) {
                    -- res;
                } else if (!(cnt[a[k]] & 1)) {
                    ++ res;
                }
            }
            f[i][j] = res;
        }
    }
    int lastans = 0;
    while (m -- ) {
        int l, r;
        std::cin >> l >> r;
        l = (l + lastans) % n + 1;
        r = (r + lastans) % n + 1;
        if (l > r) {
            std::swap(l, r);
        }
        std::cout << (lastans = calc(l, r)) << '\n';
    }
    return 0;
}

P4168 [Violet]蒲公英

题意简述

区间查询出现次数最多的且编号最小的数，强制在线。

思路

设 $f_{x, y}$ 为块 $x$ 到块 $y$ 内的答案，$c_{x, y}$ 为块 $x$ 到块 $y$ 内最多的出现次数，然后暴力判断更新？

代码

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
#include<bits/stdc++.h>
using LL = long long;

const int N = 4e4 + 5;
int n, q, a[N], b[N], cur;
int num, st[N], ed[N], belong[N], f[205][205], sum[205][N], cnt[N];
int c(int l, int r, int x) {
    if (l > r) {
        return 0;
    }
    return sum[r][x] - sum[l - 1][x];
}
int calc(int l, int r) {
    int x = belong[l], y = belong[r];
    if (x == y) {
        int MAX = 0;
        for (int i = l; i <= r; ++ i) {
            ++ cnt[a[i]];
            if (cnt[a[i]] > cnt[MAX]) {
                MAX = a[i];
            } else if (cnt[a[i]] == cnt[MAX] && MAX > a[i]) {
                MAX = a[i];
            }
        }
        for (int i = l; i <= r; ++ i) {
            cnt[a[i]] = 0;
        }
        return MAX;
    }
    int MAX = f[x + 1][y - 1];
    for (int i = l; i <= ed[x]; ++ i) {
        ++ cnt[a[i]];
        if (c(x + 1, y - 1, a[i]) + cnt[a[i]] > c(x + 1, y - 1, MAX) + cnt[MAX]) {
            MAX = a[i];
        } else if (c(x + 1, y - 1, a[i]) + cnt[a[i]] == c(x + 1, y - 1, MAX) + cnt[MAX] && MAX > a[i]) {
            MAX = a[i];
        }
    }
    for (int i = st[y]; i <= r; ++ i) {
        ++ cnt[a[i]];
        if (c(x + 1, y - 1, a[i]) + cnt[a[i]] > c(x + 1, y - 1, MAX) + cnt[MAX]) {
            MAX = a[i];
        } else if (c(x + 1, y - 1, a[i]) + cnt[a[i]] == c(x + 1, y - 1, MAX) + cnt[MAX] && MAX > a[i]) {
            MAX = a[i];
        }
    }
    for (int i = l; i <= ed[x]; ++ i) {
        cnt[a[i]] = 0;
    }
    for (int i = st[y]; i <= r; ++ i) {
        cnt[a[i]] = 0;
    }
    return MAX;
}
signed main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    
    std::cin >> n >> q;
    for (int i = 1; i <= n; ++ i) {
        std::cin >> a[i];
        b[++ cur] = a[i];
    }
    std::sort(b + 1, b + cur + 1);
    cur = std::unique(b + 1, b + cur + 1) - (b + 1);
    for (int i = 1; i <= n; ++ i) {
        a[i] = std::lower_bound(b + 1, b + cur + 1, a[i]) - b;
    }
    num = sqrt(n);
    for (int i = 1; i <= num; ++ i) {
        st[i] = n / num * (i - 1) + 1;
        ed[i] = n / num * i;
    }
    ed[num] = n;
    for (int i = 1; i <= num; ++ i) {
        for (int j = st[i]; j <= ed[i]; ++ j) {
            belong[j] = i;
            ++ sum[i][a[j]];
        }
        for (int j = 1; j <= cur; ++ j) {
            sum[i][j] += sum[i - 1][j];
        }
    }
    for (int i = 1; i <= num; ++ i) {
        for (int j = i; j <= num; ++ j) {
            int MAX = f[i][j - 1];
            for (int k = st[j]; k <= ed[j]; ++ k) {
                if (c(i, j, a[k]) > c(i, j, MAX)) {
                    MAX = a[k];
                } else if (c(i, j, a[k]) == c(i, j, MAX) && MAX > a[k]) {
                    MAX = a[k];
                }
            }
            f[i][j] = MAX;
        }
    }
    int lastans = 0;
    while (q -- ) {
        int l, r;
        std::cin >> l >> r;
        l = ((l + lastans - 1) % n) + 1;
        r = ((r + lastans - 1) % n) + 1;
        if (l > r) {
            std::swap(l, r);
        }
        std::cout << (lastans = b[calc(l, r)]) << '\n';
    }
    return 0;
}

P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III

题意简述

区间查询众数出现次数，强制在线。

思路

和蒲公英有异曲同工之妙，直接贴题解了2333，Ynoi的分块题太神了%

ynoiyyds

代码

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
#include<bits/stdc++.h>
using LL = long long;

const int N = 5e5 + 5;
int n, m, a[N], b[N], cur;
std::vector< int > pos[N];
int st[N], ed[N], belong[N], num;
int f[720][720], cnt[N], idx[N];
int Query(int l, int r) {
	int x = belong[l], y = belong[r], ans = 0;
	if (x == y) {
		for (int i = l; i <= r; ++ i) {
            cnt[a[i]] = 0;
        }
		for (int i = l; i <= r; ++ i) {
            ans = std::max(ans, ++cnt[a[i]]);
        }
		return ans;
	}
	ans = f[x + 1][y - 1];
	for (int i = l; i <= ed[x]; ++ i) {
		while (idx[i] + ans < pos[a[i]].size() && pos[a[i]][idx[i] + ans] <= r) {
            ++ ans;
        }
	}
	for (int i = st[y]; i <= r; ++ i) {
		while (idx[i] - ans >= 0 && pos[a[i]][idx[i] - ans] >= l) {
            ++ ans;
        }
	}
	return ans;
}
signed main() {
	std::cin.tie(nullptr)->sync_with_stdio(false);

	std::cin >> n >> m;
	for (int i = 1; i <= n; ++ i) {
		std::cin >> a[i];
	}
	std::copy(a + 1, a + n + 1, b + 1);
	std::sort(b + 1, b + n + 1);
    cur = std::unique(b + 1, b + n + 1) - (b + 1);
	for (int i = 1; i <= n; ++ i) {
		a[i] = std::lower_bound(b + 1, b + cur + 1, a[i]) - b;
		pos[a[i]].push_back(i);
		idx[i] = (int)pos[a[i]].size() - 1;
	}
	num = sqrt(n);
	for (int i = 1; i <= num; ++ i) {
		st[i] = n / num * (i - 1) + 1;
		ed[i] = n / num * i;
	}
	ed[num] = n;
	for (int i = 1; i <= num; ++ i) {
		for (int j = st[i]; j <= ed[i]; ++ j) {
			belong[j] = i;
		}
		memset(cnt, 0, sizeof cnt);
		for (int j = i; j <= num; ++ j) {
			f[i][j] = f[i][j - 1];
			for (int k = st[j]; k <= ed[j]; ++ k) {
				f[i][j] = std::max(f[i][j], ++ cnt[a[k]]);
			}
		}
	}
	int lastans = 0;
	while (m -- ) {
		int l, r;
		std::cin >> l >> r;
		l ^= lastans;
		r ^= lastans;
		std::cout << (lastans = Query(l, r)) << '\n';
	}
	return 0;
}

to be continued…