序列上的分块

树上分块

时间复杂度优化的 Tricks

1. 复杂度瓶颈在清空标记上

假设我们有 O(m)O(m) 的标记需要清空（比如说用于计数的桶这种，需要在 testcase 开始之前清空的），但是一共有 O(n)O(n) 轮。如果每一轮结束都暴力清空，那么时间复杂度会来到 O(nm)O(nm) 通常是不可承受的。

这时，我们定义数组 tag[i]\texttt{tag[\(i\)]} 记录标记 ii 最后一次使用是第几个 testcase。那么这样，如果当前 testcase 的 id 和 tag[i]\texttt{tag[\(i\)]} 记录的不一样，就可以直接清空；否则就可以正常的进行操作了。

例题

序列分块

CF121E - Lucky Array

我们发现要“维护 4,7,44,…4,7,44,\dots 等特殊数字的个数”这个任务很难用线段树操作，所以转而尝试分块。假设块长为 BB，分了 n/Bn/B 块。

因为 ai≤104a_i\le 10^4 且这样的 lucky number 的数量只有 3030 多个，所以我们在块上开 10410^4 个桶记录值域，即 bucket[v]=∣{i:ai=v}∣\text{bucket}[v]=|\{ i: a_i=v \}|

这里还有区间加的操作，我们在块上维护 tag 表示区间累计加了多少，查询 lucky number 个数的时候相应减去即可。时间复杂度 O(nn),B=nO(n\sqrt n),B=\sqrt n

AC Code

带着 tag 查询 lucky number 的时候需要注意 value >= tag 这个问题，不然数组会越界。

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/extc++.h>
#include <bits/stdc++.h>
constexpr int N = 1e5 + 10;
constexpr int V = 1e4 + 10;
constexpr int B = 400;

std::vector<int> P;
int ck[V];
int n, m;
int a[N];
int L[B], R[B], belong[N], bsize, bnum;
int map[B][V], tag[B];

void init_ck() {
    for (int b = 1; b <= 4; b++) {
        for (int i = 0; i < (1 << b); i++) {
            int t = 0;
            for (int j = 0; j < b; j++) {
                if (i & (1 << j)) t = t * 10 + 4;
                else t = t * 10 + 7;
            }
            if (t < V) {
                ck[t] = 1;
                P.push_back(t);
            }
        }
    }
}
int check(int x) { return ck[x]; }

void rebuild(int l, int r, int v) {
    int id = belong[l];
    if (tag[id] == 0) {
        if (v == 0) return;
        for (int i = l; i <= r; i++) {
            map[id][a[i]]--;
            a[i] += v;
            map[id][a[i]]++;
        }
    } else {
        for (int i = L[id]; i <= R[id]; i++) {
            map[id][a[i]]--;
            a[i] += tag[id];
            if (l <= i && i <= r) a[i] += v;
            map[id][a[i]]++;
        }
        tag[id] = 0;
    }
}

void add(int l, int r, int v) {
    int s = belong[l], e = belong[r];
    if (s == e) rebuild(l, r, v);
    else {
        rebuild(l, R[s], v);
        rebuild(L[e], r, v);
        for (int i = s + 1; i < e; i++) tag[i] += v;
    }
}

int query(int l, int r) {
    int s = belong[l], e = belong[r];
    int ans = 0;
    if (s == e) {
        rebuild(l, r, 0);
        for (int i = l; i <= r; i++) ans += ck[a[i]];
    } else {
        rebuild(l, R[s], 0);
        rebuild(L[e], r, 0);
        for (int i = l; i <= R[s]; i++) ans += ck[a[i]];
        for (int i = L[e]; i <= r; i++) ans += ck[a[i]];
        for (int i = s + 1; i < e; i++) {
            for (int p : P)
                if (p >= tag[i]) ans += map[i][p - tag[i]];
        }
    }
    return ans;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    std::cout.tie(nullptr);

    init_ck();

    std::cin >> n >> m;
    bsize = std::sqrt(P.size() * n);
    bnum  = (n + bsize - 1) / bsize;
    for (int i = 1; i <= bnum; i++) {
        L[i] = (i - 1) * bsize + 1;
        R[i] = std::min(i * bsize, n);
        for (int j = L[i]; j <= R[i]; j++) belong[j] = i;
    }

    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        map[belong[i]][a[i]]++;
    }

    std::string op;
    int l, r, v;
    while (m--) {
        std::cin >> op >> l >> r;
        if (op == "add") {
            std::cin >> v;
            add(l, r, v);
        } else {
            std::cout << query(l, r) << '\n';
        }
    }
}

LOJ#6282. 数列分块入门 6

当然可以用平衡树过题，不过我们还是来看一看用分块怎么做.

以下 N,QN,Q 同阶

我们令块长为 B=NB=\sqrt N，则共 N/BN/B 块。在每一个块上，维护 std::vector 保存块内的数，这些块的 vector 按顺序拼接起来就是完整的数组。

  • 对于查询操作，我们可以 O(N/B)O(N/B) 暴力找出 pospos 所在的块，然后直接输出 vector 内的数。时间复杂度 O(N/B)O(N/B)
  • 对于插入操作，我们先 O(N/B)O(N/B) 找出 pospos 所在的块，然后直接用 vector.insert() 插入。insert() 的复杂度是 O(B)O(B) 的，所以插入的复杂度是 O(B+N/B)O(B+N/B)

但是另外一个问题是，每一次插入操作都会让某一个块的长度越来越长，导致 B0B_0 越来越大。比如说，如果 QQ 次操作都是把数插入到最后一个块的第一个位置，那么最后一块的块长将来到 O(Q)=O(N)O(Q)=O(N)，总时间复杂度将来到 O(NQ)O(NQ) 肯定是不行的。

所以针对最后一块的失衡问题，我们考虑重构操作：收集所有元素，然后重新分配到每一个块中，这样单次重构的复杂度是 O(N)O(N) 的. 如果在每 O(Q)O(\sqrt Q) 次插入后都重构一次：

  • 因为最多 QQ 次操作，所以最多有 O(Q)O(\sqrt Q) 次重构操作，重构的整体复杂度是 O(NQ)O(N\sqrt Q) 的.
  • 而且，因为每 O(Q)O(\sqrt Q) 次操作后就重构一次，插入操作时，块长最多为 B+QB+\sqrt Q，依然是 O(N)O(\sqrt N) 的，保证了插入的复杂度正确性
  • 查询依然还是 O(N/B)O(N/B)

所以综上，重构的总时间复杂度 O(NQ)O(N\sqrt Q)，插入查询的单词时间复杂度为 O(N)O(\sqrt N)，于是总时间复杂度为 O(NN)O(N\sqrt N).

AC Code
 
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
#include <bits/stdc++.h>
constexpr int N = 1e5 + 10;
constexpr int B = 500;

struct block {
    int len;
    std::pair<int, int> range;
    std::vector<int> elem;
};

int n, opt, l, r, c;
int sqrtn, bcnt, totlen, icnt{0};
std::array<int, N> a, bel;
std::array<block, B> blk;

void rebuild() {
    std::vector<int> a;
    a.push_back(-1);
    for (int i = 1; i <= bcnt; i++) {
        a.insert(a.end(), blk[i].elem.begin(), blk[i].elem.end());
        blk[i].elem.clear();
    }

    sqrtn = std::sqrt(totlen);
    bcnt = (totlen + sqrtn - 1) / sqrtn;
    for (int i = 1; i <= bcnt; i++) {
        auto [l, r] = blk[i].range = {(i - 1) * sqrtn + 1, std::min(totlen, i * sqrtn)};
        blk[i].len = r - l + 1;
        for (int j = l; j <= r; j++)
            blk[i].elem.push_back(a[j]);
    }

    icnt = 0;
}

void insert(int pos, int val) {
    for (int i = 1; i <= bcnt; i++) {
        if (pos > blk[i].len)
            pos -= blk[i].len;
        else {
            blk[i].elem.insert(blk[i].elem.begin() + pos - 1, val);
            blk[i].len++, totlen++, icnt++;

            if (icnt >= sqrtn)
                rebuild();

            break;
        }
    }
}

void get(int pos) {
    for (int i = 1; i <= bcnt; i++) {
        if (pos > blk[i].len)
            pos -= blk[i].len;
        else {
            std::cout << blk[i].elem[pos - 1] << "\n";
            break;
        }
    }
}

int main() {
    std::cin >> n;
    sqrtn = std::sqrt(n);
    bcnt = (n + sqrtn - 1) / sqrtn;
    totlen = n;

    for (int i = 1; i <= n; i++)
        std::cin >> a[i];

    for (int i = 1; i <= bcnt; i++) {
        auto [l, r] = blk[i].range = {(i - 1) * sqrtn + 1, std::min(i * sqrtn, n)};
        blk[i].len = blk[i].range.second - blk[i].range.first + 1;
        for (int j = l; j <= r; j++)
            bel[j] = i, blk[i].elem.push_back(a[j]);
    }

    for (int _ = 1; _ <= n; _++) {
        std::cin >> opt >> l >> r >> c;

        opt == 0 ? insert(l, r) : get(r);
    }
}

LOJ#6283. 数列分块入门 7

提示：在每个块上维护懒标记 tag = { add, mul } 表示块内所有元素的真实值为

ai′←ai⋅mul+add a_i'\gets a_i \cdot \texttt{mul} + \texttt{add}

时间复杂度 O(nn)O(n\sqrt n)

AC Code
 
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
#include <bits/stdc++.h>
using ll = long long;
constexpr int N = 1e5 + 10;
constexpr int B = 505;
constexpr int M = 10007;

struct tag {
    ll add{0}, mul{1}; // x * mul + add

    bool is_null() { return add == 0 && mul == 1; }
    void clear() { add = 0, mul = 1; }
    void apply_mul(ll v) { (mul *= v) %= M, (add *= v) %= M; }
    void apply_add(ll v) { (add += v) %= M; }
    void merge(tag T) {
        assert(T.add == 0 or T.mul == 1);

        if (T.add != 0)
            apply_add(T.add);
        else
            apply_mul(T.mul);
    }
};

struct block {
    tag t;
    int l, r;
};

int n, opt, l, r, c;
int sqrtn, blkcnt;
std::array<int, N> bel;
std::array<ll, N> a;
std::array<block, B> blks;

void rebuild(int L, int R, tag v) {
    int b = bel[L];
    for (int i = blks[b].l; i <= blks[b].r; i++) {
        a[i] = (a[i] * blks[b].t.mul % M + blks[b].t.add) % M;

        if (L <= i && i <= R) {
            if (v.add != 0)
                (a[i] += v.add) %= M;
            else
                (a[i] *= v.mul) %= M;
        }
    }
    blks[b].t.clear();
}

void apply(int L, int R, tag T) {
    int s = bel[L], e = bel[R];
    if (s == e)
        rebuild(L, R, T);
    else {
        rebuild(L, blks[s].r, T);
        rebuild(blks[e].l, R, T);
        for (int i = s + 1; i <= e - 1; i++)
            blks[i].t.merge(T);
    }
}

void query(int pos) {
    int b = bel[pos];
    std::cout << (a[pos] * blks[b].t.mul % M + blks[b].t.add) % M << "\n";
}

int main() {
    std::cin >> n;
    for (int i = 1; i <= n; i++)
        std::cin >> a[i], a[i] %= M;

    sqrtn = std::sqrt(n), blkcnt = (n + sqrtn - 1) / sqrtn;
    for (int i = 1; i <= blkcnt; i++) {
        l = (i - 1) * sqrtn + 1, r = std::min(i * sqrtn, n);
        blks[i].l = l, blks[i].r = r;
        for (int j = l; j <= r; j++)
            bel[j] = i;
    }

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

        if (opt == 0)
            apply(l, r, {c, 1});
        else if (opt == 1)
            apply(l, r, {0, c});
        else
            query(r);
    }
}
杂项
License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。