数据结构 提高组刷题

发表于 更新于 分类于 阅读次数： 本文字数： 41k
题目来自洛谷题单 https://www.luogu.com.cn/training/1010。

以下题目大部分来自 https://www.luogu.com.cn/training/1010，少数题作为题单的前置知识用于巩固数据结构。

并查集

连通性判断

P1197 [JSOI2008] 星球大战

先建图再一个一个去掉点显然难以维护，我们考虑倒着操作，每次删去一个点的答案就是加这个点之前的答案。

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;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

struct DSU {
    int n;
    vector<int> p, sz;
    DSU(int n_) {
        n = n_;
        init(n);
    }
    void init(int n) {
        p.resize(n + 1);
        sz.resize(n + 1, 1);
        iota(p.begin() + 1, p.end(), 1);
    }
    int find(int x) {
        while (x != p[x]) {
            x = p[x] = p[p[x]];
        }
        return x;
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (sz[x] > sz[y]) {
            swap(x, y);
        }
        p[x] = y;
        sz[y] += sz[x];
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
};

void solve() {
    int n, m;
    cin >> n >> m;
    DSU dsu(n);
    vector<vector<int>> e(n);
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    int q;
    cin >> q;
    vector<bool> vis(n);
    vector<array<int, 2>> e2(q);
    for (int i = 0; i < q; i++) {
        int x;
        cin >> x;
        vis[x] = true;
        e2[i] = {x, 0};
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            ans++;
            for (auto y : e[i]) {
                if (!vis[y]) {
                    if (dsu.merge(i, y)) {
                        ans--;
                    }
                }
            }
        }
    }
    int res = ans;
    for (int i = q - 1; i >= 0; i--) {
        int x = e2[i][0];
        ans++;
        for (auto y : e[x]) {
            if (!vis[y]) {
                if (dsu.merge(y, x)) {
                    ans--;
                }
            }
        }
        vis[x] = false;
        e2[i][1] = ans;
    }
    for (int i = 0; i < q; i++) {
        cout << e2[i][1] << "\n";
    }
    cout << res << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

[P3958 NOIP 2017 提高组] 奶酪

由于老鼠只能在空洞之间穿梭，我们把能够穿梭的空洞合并（圆心间距离和半径比较），然后判断每一个连通块能否从最下面到最上面即可。

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 namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

struct DSU {
    int n;
    vector<int> p, sz;
    DSU(int n_) {
        n = n_;
        init(n);
    }
    void init(int n) {
        p.resize(n + 1);
        sz.resize(n + 1, 1);
        iota(p.begin() + 1, p.end(), 1);
    }
    int find(int x) {
        while (x != p[x]) {
            x = p[x] = p[p[x]];
        }
        return x;
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (sz[x] > sz[y]) {
            swap(x, y);
        }
        sz[y] += sz[x];
        p[x] = y;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
};

void solve() {
    int n, h, r;
    cin >> n >> h >> r;
    vector<array<int, 3>> a(n + 1);
    vector<bool> is_low(n + 1), is_high(n + 1);
    for (int i = 1; i <= n; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        a[i] = {x, y, z};
        if (z <= r) {
            is_low[i] = true;
        }
        if (h - z <= r) {
            is_high[i] = true;
        }
    }
    DSU dsu(n);
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            auto check = [&](int x, int y) {
                if (1ll * (a[x][0] - a[y][0]) * (a[x][0] - a[y][0]) +
                        1ll * (a[x][1] - a[y][1]) * (a[x][1] - a[y][1]) +
                        1ll * (a[x][2] - a[y][2]) * (a[x][2] - a[y][2]) <=
                    4ll * r * r) {
                    return true;
                }
                return false;
            };
            if (check(i, j)) {
                dsu.merge(i, j);
            }
        }
    }
    vector<vector<int>> e(n + 1);
    for (int i = 1; i <= n; i++) {
        e[dsu.find(i)].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        bool low = false, high = false;
        for (auto y : e[i]) {
            if (is_low[y] == true) {
                low = true;
            }
            if (is_high[y] == true) {
                high = true;
            }
        }
        if (low && high) {
            cout << "Yes\n";
            return;
        }
    }
    cout << "No\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

P1783 海滩防御

有了上一题的基础，我们这里额外的操作就是二分答案（半径），但是由于半径是浮点数，我们可以选择把所有长度乘 1000，最后将答案除以 1000。这里不要乘100，会有精度问题。

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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

struct DSU {
    int n;
    vector<int> p, sz;
    DSU(int n_) {
        n = n_;
        init(n);
    }
    void init(int n) {
        p.resize(n + 1);
        sz.resize(n + 1, 1);
        iota(p.begin() + 1, p.end(), 1);
    }
    int find(int x) {
        while (x != p[x]) {
            x = p[x] = p[p[x]];
        }
        return x;
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (sz[x] > sz[y]) {
            swap(x, y);
        }
        sz[y] += sz[x];
        p[x] = y;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<array<int, 2>> a(m + 1);
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        a[i] = {x, y};
    }
    int lo = 1, hi = 10000 * n;
    int ans = 1e9;
    while (lo <= hi) {
        // cerr << "lo = " << lo << " hi = " << hi << endl;
        int mid = lo + (hi - lo) / 2;
        auto check = [&](int x) {
            DSU dsu(m);
            for (int i = 1; i <= m; i++) {
                for (int j = i + 1; j <= m; j++) {
                    if (1000000ll * (a[i][0] - a[j][0]) * (a[i][0] - a[j][0]) +
                            1000000ll * (a[i][1] - a[j][1]) *
                                (a[i][1] - a[j][1]) <=
                        4ll * x * x) {
                        dsu.merge(i, j);
                    }
                }
            }
            vector<vector<int>> e(m + 1);
            for (int i = 1; i <= m; i++) {
                e[dsu.find(i)].push_back(i);
            }
            for (int i = 1; i <= m; i++) {
                bool left = false, right = false;
                for (auto y : e[i]) {
                    if (a[y][0] * 1000 <= x) {
                        left = true;
                    }
                    if (a[y][0] * 1000 + x >= n * 1000) {
                        right = true;
                    }
                }
                if (left && right) {
                    return true;
                }
            }
            return false;
        };
        if (check(mid)) {
            ans = min(ans, mid);
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    cout << fixed << setprecision(2) << 1.0 * ans / 1000 << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

非加权维护

[P1525 NOIP 2010 提高组] 关押罪犯

扩展域并查集。我们从贪心的角度思考，要让最小值尽量小，我们就排序从大到小地将两个点隔开，这样可以避免最大值出现。我们建立大小为 \(2n\) 的并查集，对于每对冲突的人 \(x,y\)，连边 \((x,y+n)\) 和 \((x+n, y)\) ，代表 \(x,y\) 不同时出现。但是，一旦 \((x,x+n)\) 或 \((y,y+n)\)​ 连通，说明此时不论如何都会冲突了，直接输出答案。

稍微说一下扩展域并查集，有点像 2-Sat 的思想，\(a,b\) 不能同时出现就把 \(a\) 和 \(b\) 的反状态 \(b+n\) 连边，\(b\) 和 \(a\) 的反状态 \(a+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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

struct DSU {
    int n;
    vector<int> p, sz;
    DSU(int n_) {
        n = n_;
        init(n);
    }
    void init(int n) {
        p.resize(n + 1);
        sz.resize(n + 1, 1);
        iota(p.begin() + 1, p.end(), 1);
    }
    int find(int x) {
        while (x != p[x]) {
            x = p[x] = p[p[x]];
        }
        return x;
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (sz[x] > sz[y]) {
            swap(x, y);
        }
        sz[y] += sz[x];
        p[x] = y;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<array<int, 3>> a(m + 1);
    for (int i = 1; i <= m; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        a[i] = {w, x, y};
    }
    sort(a.begin() + 1, a.end(), greater());
    DSU dsu(2 * n);
    for (int i = 1; i <= m; i++) {
        auto [w, x, y] = a[i];
        dsu.merge(x, y + n);
        dsu.merge(x + n, y);
        if (dsu.same(x, x + n) || dsu.same(y, y + n)) {
            cout << w << "\n";
            return;
        }
    }
    cout << 0 << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

P2024 [NOI2001] 食物链

同样使用扩展域并查集，不过这里是 ABC 三类关系，我们并不具体清楚三者的关系，所以选择在三个区域都进行操作。

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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

struct DSU {
    int n;
    vector<int> p, sz;
    DSU(int n_) {
        n = n_;
        init(n);
    }
    void init(int n) {
        p.resize(n + 1);
        sz.resize(n + 1, 1);
        iota(p.begin() + 1, p.end(), 1);
    }
    int find(int x) {
        while (x != p[x]) {
            x = p[x] = p[p[x]];
        }
        return x;
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (sz[x] > sz[y]) {
            swap(x, y);
        }
        sz[y] += sz[x];
        p[x] = y;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
};

void solve() {
    int n, k;
    cin >> n >> k;
    DSU dsu(3 * n);
    int ans = 0;
    int d[] = {0, n, 2 * n, 0, n, 2 * n};
    for (int i = 1; i <= k; i++) {
        int op, x, y;
        cin >> op >> x >> y;
        if (x > n || y > n || dsu.same(x, x + n) ||
            dsu.same(x + n, x + 2 * n) || dsu.same(x + 2 * n, x)) {
            ans++;
            continue;
        }
        if (op == 1) {
            for (int i = 0; i < 3; i++) {
                if (dsu.same(x + d[i], y + d[i + 1]) ||
                    dsu.same(x + d[i], y + d[i + 2])) {
                    ans++;
                    break;
                }
                dsu.merge(x + d[i], y + d[i]);
            }
        } else {
            if (x == y) {
                ans++;
                continue;
            }
            for (int i = 0; i < 3; i++) {
                if (dsu.same(x + d[i], y + d[i]) ||
                    dsu.same(x + d[i], y + d[i + 2])) {
                    ans++;
                    break;
                }
                dsu.merge(x + d[i], y + d[i + 1]);
            }
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

加权维护

P1196 [NOI2002] 银河英雄传说

本地区别于普通并查集维护连通性和连通块大小的地方在于：我们需要回答连通块内两点的距离。由于该题目是以链的形式首位合并的，我们可以维护两点到根节点的距离。利用前缀和的思想，答案就是 \(\mid v_x-v_y \mid - 1\)​。

注意实现带权并查集和普通并查集的区别：在 find 函数中我们用递归的思路更新 v[x] += v[p[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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

struct DSU {
    int n;
    vector<int> p, sz, v;
    DSU(int n_) {
        n = n_;
        init(n);
    }
    void init(int n) {
        p.resize(n + 1);
        sz.resize(n + 1, 1);
        v.resize(n + 1);
        iota(p.begin() + 1, p.end(), 1);
    }
    int find(int x) {
        if (x == p[x]) {
            return x;
        }
        int o = p[x];
        p[x] = find(p[x]);
        v[x] += v[o];
        return p[x];
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        v[x] += sz[y];
        sz[y] += sz[x];
        p[x] = y;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
    int query(int x) {
        find(x);
        return v[x];
    }
};

void solve() {
    int n = 30000;
    int q;
    cin >> q;
    DSU dsu(n);
    for (int i = 1; i <= q; i++) {
        char op;
        int x, y;
        cin >> op >> x >> y;
        if (op == 'M') {
            dsu.merge(x, y);
        } else {
            if (!dsu.same(x, y)) {
                cout << -1 << "\n";
                continue;
            }
            cout << abs(dsu.query(x) - dsu.query(y)) - 1 << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

[P5092 USACO04OPEN] Cube Sta

跟上题几乎一模一样。

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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

struct DSU {
    int n;
    vector<int> p, sz, v;
    DSU(int n_) {
        n = n_;
        init(n_);
    }
    void init(int n) {
        p.resize(n + 1);
        iota(p.begin() + 1, p.end(), 1);
        v.resize(n + 1);
        sz.resize(n + 1, 1);
    }
    int find(int x) {
        if (x == p[x]) {
            return x;
        }
        int o = p[x];
        p[x] = find(p[x]);
        v[x] += v[o];
        return p[x];
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        v[x] += sz[y];
        sz[y] += sz[x];
        p[x] = y;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
    int query(int x) {
        find(x);
        return v[x];
    }
};

void solve() {
    int n = 30000;
    DSU dsu(n);
    int q;
    cin >> q;
    while (q--) {
        char op;
        int x, y;
        cin >> op >> x;
        if (op == 'M') {
            cin >> y;
            dsu.merge(x, y);
        } else {
            cout << dsu.query(x) << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

树状数组 / 线段树

P2574 XOR的艺术

区间赋值其实就是把区间的 0 1 翻转，tag 用异或维护，info 的 apply 就是用区间大小减去 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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

template <class Info, class Tag>
struct LazySegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) { init(n_, v_); }
    template <class T>
    LazySegmentTree(vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) { init(vector(n_ + 1, v_)); }
    template <class T>
    void init(vector<T> init_) {
        n = init_.size() - 1;
        info.assign(4 * (n + 1), Info());
        tag.assign(4 * (n + 1), Tag());
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = Info(init_[l]);
                return;
            }
            int m = l + (r - l) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (l == r) {
            info[p] = v;
            return;
        }
        int m = l + (r - l) / 2;
        push(p);
        if (x <= m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m + 1, r, x, v);
        }
        pull(p);
    }
    void modify(int x, const Info &v) { modify(1, 1, n, x, v); }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l > y || r < x) {
            return Info();
        }
        if (x <= l && r <= y) {
            return info[p];
        }
        int m = l + (r - l) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) +
               rangeQuery(2 * p + 1, m + 1, r, x, y);
    }
    Info rangeQuery(int l, int r) { return rangeQuery(1, 1, n, l, r); }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l > y || r < x) {
            return;
        }
        if (x <= l && r <= y) {
            apply(p, v);
            return;
        }
        push(p);
        int m = l + (r - l) / 2;
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m + 1, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        rangeApply(1, 1, n, l, r, v);
    }
};

struct Tag {
    int x = 0;
    void apply(const Tag &t) { x ^= t.x; }
};

struct Info {
    int x = 0;
    int size = 1;
    Info() {};
    Info(int x) : x(x) {}
    Info(int x, int size) : x(x), size(size) {}
    void apply(const Tag &t) {
        if (t.x) {
            x = size - x;
        }
    }
};

Info operator+(const Info &a, const Info &b) {
    return Info(a.x + b.x, a.size + b.size);
}

void solve() {
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;
    s = " " + s;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = (s[i] == '1');
    }
    LazySegmentTree<Info, Tag> seg(a);
    while (m--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 0) {
            seg.rangeApply(l, r, Tag(1));
        } else {
            cout << seg.rangeQuery(l, r).x << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

[P2894 USACO08FEB] Hotel G

由于需要找到最左边的满足条件的区间，需要用到线段树的查找前驱操作。但是这里不能简单地调用线段树模版的 findFirst 函数，因为那个函数本质就是在线段树上二分，只找单点满足条件，而这里不仅要考虑答案在左右区间，答案还有可能就在中间，且答案不为单点的形式，而是一个区间。

我们懒标记记录上次操作的类型（1 代表退房，此时整个区间都可以住，答案就是区间长度，2 代表入住，此时清空区间长度）。

对于查找前驱操作，需要注意特判一下全局的长度是否满足条件；而懒标记尤其要注意不能把空的懒标记（值不是 1 或 2 下传）。考虑上次操作大区间下传一个标记 1 给小区间，自身被清空为 0 ，如果再次操作这个大区间，下传标记 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
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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

template <class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) { init(n_, v_); }
    template <class T>
    LazySegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) { init(std::vector(n_ + 1, v_)); }
    template <class T>
    void init(std::vector<T> init_) {
        n = init_.size() - 1;
        info.assign(4 * (n + 1), Info());
        tag.assign(4 * (n + 1), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = Info(init_[l]);  // 使用 Info 的构造函数
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    // modify 为重新赋值
    void modify(int p, int l, int r, int x, const Info &v) {
        if (l == r) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x <= m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m + 1, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) { modify(1, 1, n, p, v); }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l > y || r < x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) +
               rangeQuery(2 * p + 1, m + 1, r, x, y);
    }
    Info rangeQuery(int l, int r) { return rangeQuery(1, 1, n, l, r); }
    // apply 为修改
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l > y || r < x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m + 1, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 1, n, l, r, v);
    }
    int findFirst(int p, int l, int r, int x) {
        if (l == r) {
            return l;
        }
        push(p);
        int mid = (l + r) / 2;
        if (info[p * 2].ans >= x) {
            return findFirst(2 * p, l, mid, x);
        }
        if (info[2 * p].rmax + info[2 * p + 1].lmax >= x) {
            return mid - info[p * 2].rmax + 1;
        }
        return findFirst(2 * p + 1, mid + 1, r, x);
    }
};

struct Tag {
    int x;
    Tag(int t = 0) : x(t) {}
    void apply(const Tag &t) {
        if (t.x) {
            x = t.x;
        }
    }
};

struct Info {
    int ans = 0;
    int lmax = 0;
    int rmax = 0;
    int size = 1;
    Info() {}
    Info(int x) : ans(x), lmax(x), rmax(x), size(1) {}
    void apply(const Tag &t) {
        if (t.x == 1) {
            lmax = rmax = ans = size;
        } else if (t.x == 2) {
            lmax = rmax = ans = 0;
        }
    }
};

Info operator+(const Info &a, const Info &b) {
    Info info;
    info.size = a.size + b.size;
    info.lmax = ((a.lmax == a.size) ? (a.lmax + b.lmax) : a.lmax);
    info.rmax = ((b.rmax == b.size) ? (b.rmax + a.rmax) : b.rmax);
    info.ans = max({a.ans, b.ans, a.rmax + b.lmax});
    return info;
}

void solve() {
    int n, m;
    cin >> n >> m;
    LazySegmentTree<Info, Tag> seg(n, 1);

    while (m--) {
        int op, x, y;
        cin >> op >> x;
        if (op == 1) {
            if (seg.rangeQuery(1, n).ans >= x) {
                int res = seg.findFirst(1, 1, n, x);
                cout << res << "\n";
                seg.rangeApply(res, res + x - 1, Tag(2));
            } else {
                cout << 0 << "\n";
            }
        } else {
            cin >> y;
            seg.rangeApply(x, x + y - 1, Tag(1));
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

P4145 上帝造题的七分钟 2 / 花神游历各国

开根号操作是难以维护的，但是 \(10^{12}\) 的数据范围下最多开 6 次根号就会变为 1，对于全是 1 的区间，我们并不需要再一个一个进行操作，因此区间维护的次数只有 \(O(n)\) 次，总复杂度还是 \(O(m\log n)\)，可以接受。需要维护区间和和区间最大值。实现上，可以采用单调修改线段树或懒标记线段树，但是不要从 \(l\) 遍历到 \(r\)，这样做的常数还是太大了，写一个区间修改函数，在终止条件 l == r 下再停止操作即可。

还有一种并查集 + 树状数组的做法，并查集连向下一个不为 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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

template <class Info>
struct SegmentTree {
    int n;
    vector<Info> info;

    SegmentTree(int n) : n(n), info(4 * n) {}

    SegmentTree(const vector<Info> &init) : SegmentTree(init.size() - 1) {
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = init[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }

    void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; }

    void apply(int p, int l, int r) {
        if (info[p].mx <= 1) return;  // 不再继续开方
        if (l == r) {
            info[p].apply();
            return;
        }
        int m = (l + r) / 2;
        apply(2 * p, l, m);
        apply(2 * p + 1, m + 1, r);
        pull(p);
    }

    void rangeApply(int p, int l, int r, int x, int y) {
        if (l > y || r < x || info[p].mx == 1) return;  // 终止条件
        if (l == r) {
            info[p].apply();
            return;
        }
        int m = (l + r) / 2;
        rangeApply(2 * p, l, m, x, y);
        rangeApply(2 * p + 1, m + 1, r, x, y);
        pull(p);
    }

    void rangeApply(int l, int r) { rangeApply(1, 1, n, l, r); }

    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l > y || r < x) return Info();
        if (l >= x && r <= y) return info[p];
        int m = (l + r) / 2;
        return rangeQuery(2 * p, l, m, x, y) +
               rangeQuery(2 * p + 1, m + 1, r, x, y);
    }

    Info rangeQuery(int l, int r) { return rangeQuery(1, 1, n, l, r); }
};

struct Info {
    i64 val = 0;
    i64 mx = 0;
    Info() {}
    Info(i64 val) : val(val), mx(val) {}
    Info(i64 val, i64 mx) : val(val), mx(mx) {}

    void apply() {
        val = sqrt(val);
        mx = sqrt(mx);
    }
};

Info operator+(const Info &a, const Info &b) {
    return Info(a.val + b.val, max(a.mx, b.mx));
}

void solve() {
    int n, m;
    cin >> n;
    vector<Info> a(n + 1);
    for (int i = 1; i <= n; i++) {
        i64 x;
        cin >> x;
        a[i] = Info(x);
    }
    SegmentTree<Info> seg(a);
    cin >> m;
    while (m--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (l > r) swap(l, r);
        if (op == 0) {
            seg.rangeApply(l, r);  // **优化：整段修改**
        } else {
            cout << seg.rangeQuery(l, r).val << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    while (t--) {
        solve();
    }
    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
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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

template <class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) { init(n_, v_); }
    template <class T>
    LazySegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) { init(std::vector(n_ + 1, v_)); }
    template <class T>
    void init(std::vector<T> init_) {
        n = init_.size() - 1;
        info.assign(4 << (int)log2(n + 1), Info());
        tag.assign(4 << (int)log2(n + 1), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = Info(init_[l]);  
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (l == r) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x <= m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m + 1, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) { modify(1, 1, n, p, v); }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l > y || r < x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) +
               rangeQuery(2 * p + 1, m + 1, r, x, y);
    }
    Info rangeQuery(int l, int r) { return rangeQuery(1, 1, n, l, r); }
    // apply 为修改
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l > y || r < x) {
            return;
        }
        if (l == r && l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (info[2 * p].mx > 1) {
            rangeApply(2 * p, l, m, x, y, v);
        }
        if (info[2 * p + 1].mx > 1) {
            rangeApply(2 * p + 1, m + 1, r, x, y, v);
        }
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 1, n, l, r, v);
    }
};

struct Tag {
    int x = 0;
    Tag() {}
    Tag(int x) : x(x) {}
    void apply(const Tag &t) & {
        if (t.x) {
            x = t.x;
        }
    }
};

struct Info {
    i64 val = 0;
    i64 mx = 0;
    Info() {}
    Info(i64 val) : val(val), mx(val) {}
    Info(i64 val, i64 mx) : val(val), mx(mx) {}
    void apply(const Tag &t) & {
        if (t.x) {
            val = sqrt(val);
            mx = sqrt(mx);
        }
    }
};
Info operator+(const Info &a, const Info &b) {
    return Info(a.val + b.val, max(a.mx, b.mx));
}

void solve() {
    int n, m;
    cin >> n;
    vector<Info> a(n + 1);
    for (int i = 1; i <= n; i++) {
        i64 x;
        cin >> x;
        a[i] = Info(x);
    }
    LazySegmentTree<Info, Tag> seg(a);
    cin >> m;
    while (m--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (l > r) {
            swap(l, r);
        }
        if (op == 0) {
            seg.rangeApply(l, r, Tag(1));
        } else {
            cout << seg.rangeQuery(l, r).val << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    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
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 namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

struct DSU {
    int n;
    vector<int> p, sz;
    DSU(int n_) {
        n = n_;
        init(n);
    }
    void init(int n) {
        p.resize(n + 1);
        sz.resize(n + 1, 1);
        iota(p.begin() + 1, p.end(), 1);
    }
    int find(int x) {
        while (x != p[x]) {
            x = p[x] = p[p[x]];
        }
        return x;
    }
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (sz[x] > sz[y]) {
            swap(x, y);
        }
        sz[y] += sz[x];
        p[x] = y;
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sz[find(x)]; }
};

struct Fenwick {
    int n;
    vector<i64> a;
    Fenwick(int n) { init(n); }
    void init(int n_) {
        n = n_;
        a.assign(n + 1, 0ll);
    }
    void add(int x, i64 v) {
        for (int i = x; i <= n; i += i & (-i)) {
            a[i] += v;
        }
    }
    i64 sum(int x) {
        i64 res = 0;
        for (int i = x; i >= 1; i -= i & -i) {
            res += a[i];
        }
        return res;
    }
    i64 rangeSum(int l, int r) { return sum(r) - sum(l - 1); }
};

void solve() {
    int n;
    cin >> n;
    Fenwick fen(n);
    vector<i64> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        fen.add(i, a[i]);
    }
    DSU dsu(n + 1);
    int m;
    cin >> m;
    while (m--) {
        int op, l, r;
        cin >> op >> l >> r;
        if (l > r) {
            swap(l, r);
        }
        if (op == 0) {
            while (l <= r) {
                i64 t = (i64)sqrt(a[l]);
                fen.add(l, t - a[l]);
                a[l] = t;
                dsu.p[l] = (a[l] <= 1 ? l + 1 : l);
                l = (dsu.p[l] == l ? l + 1 : dsu.find(dsu.p[l]));
            }
        } else {
            cout << fen.rangeSum(l, r) << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

P4513 小白逛公园

处理区间内最大子段和，需要分三种情况：左儿子最大值，右儿子最大值，中间最大值（取左儿子右边最值和右儿子左边最值），所以维护区间和（更新很简单）、从左边开始的最大子段和（取左儿子的或者左儿子的区间和 + 右儿子左边最大子段和）、从右边开始的最大子段和（同理）、全局最大子段和。单点修改线段树即可。

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;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

template <class Info, class Merge = plus<Info>>
struct SegmentTree {
    const int n;
    const Merge merge;
    vector<Info> info;
    SegmentTree(int n) : n(n), merge(Merge()), info(4 << (int)log2(n + 1)) {}
    SegmentTree(vector<Info> init) : SegmentTree(init.size() - 1) {
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = init[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    void pull(int p) { info[p] = merge(info[2 * p], info[2 * p + 1]); }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (l == r) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x <= m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m + 1, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) { modify(1, 1, n, p, v); }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        // cerr << "l = " << l << " r = " << r << " sum = " << info[p].sum
        //      << " ans = " << info[p].ans << endl;
        if (l > y || r < x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return merge(rangeQuery(2 * p, l, m, x, y),
                     rangeQuery(2 * p + 1, m + 1, r, x, y));
    }
    Info rangeQuery(int l, int r) { return rangeQuery(1, 1, n, l, r); }
};

struct Info {
    i64 sum = INT_MIN;
    i64 ans = INT_MIN;
    i64 lans = INT_MIN;
    i64 rans = INT_MIN;
    Info() {}
    Info(i64 x) : sum(x), ans(x), lans(x), rans(x) {}
};

Info operator+(const Info &a, const Info &b) {
    Info res;
    res.sum = a.sum + b.sum;
    res.lans = max(a.lans, a.sum + b.lans);
    res.rans = max(b.rans, b.sum + a.rans);
    res.ans = max({a.ans, b.ans, a.rans + b.lans, a.rans, b.lans});
    return res;
}

void solve() {
    int n, m;
    cin >> n >> m;
    SegmentTree<Info> seg(n);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        seg.modify(i, x);
    }
    while (m--) {
        seg.rangeQuery(2, 3);

        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            if (l > r) {
                swap(l, r);
            }
            cout << seg.rangeQuery(l, r).ans << "\n";
        } else {
            seg.modify(l, r);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

[P2572 SCOI2010] 序列操作

如果前面都做了，这里肯定没有多大问题了，维护区间和，区间 1 和 0 的左连续，右连续，连续最值。但是要注意下 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
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
246
247
248
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

template <class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) { init(n_, v_); }
    template <class T>
    LazySegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) { init(std::vector(n_ + 1, v_)); }
    template <class T>
    void init(std::vector<T> init_) {
        n = init_.size() - 1;
        info.assign(4 << (int)log2(n + 1), Info());
        tag.assign(4 << (int)log2(n + 1), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = Info(init_[l]);  // 使用 Info 的构造函数
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    void pull(int p) { info[p] = info[2 * p] + info[2 * p + 1]; }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    // modify 为重新赋值
    void modify(int p, int l, int r, int x, const Info &v) {
        if (l == r) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x <= m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m + 1, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) { modify(1, 1, n, p, v); }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l > y || r < x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) +
               rangeQuery(2 * p + 1, m + 1, r, x, y);
    }
    Info rangeQuery(int l, int r) { return rangeQuery(1, 1, n, l, r); }
    // apply 为修改
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l > y || r < x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m + 1, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 1, n, l, r, v);
    }
    template <class F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template <class F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template <class F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template <class F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 0, n, l, r, pred);
    }
};

struct Tag {
    int x = 0;  // 1:变0，2:变1，3:取反
    Tag() {}
    Tag(int x) : x(x) {}
    void apply(const Tag &t) {
        if (!t.x) return;
        if (!x) {
            x = t.x;
        } else if (t.x == 3) {
            if (x == 1)
                x = 2;
            else if (x == 2)
                x = 1;
            else if (x == 3)
                x = 0;
        } else {
            x = t.x;
        }
    }
};

struct Info {
    i64 sum = 0;
    i64 ans0 = 0;
    i64 ans1 = 0;
    i64 ans0l = 0;
    i64 ans0r = 0;
    i64 ans1l = 0;
    i64 ans1r = 0;
    i64 size = 1;
    Info() {}
    Info(int x)
        : sum(x),
          ans0(1 - x),
          ans1(x),
          ans0l(1 - x),
          ans0r(1 - x),
          ans1l(x),
          ans1r(x) {}
    void apply(const Tag &t) {
        if (t.x == 1) {
            sum = 0;
            ans0 = ans0l = ans0r = size;
            ans1 = ans1l = ans1r = 0;
        } else if (t.x == 2) {
            sum = size;
            ans0 = ans0l = ans0r = 0;
            ans1 = ans1l = ans1r = size;
        } else if (t.x == 3) {
            sum = size - sum;
            swap(ans0, ans1);
            swap(ans0l, ans1l);
            swap(ans0r, ans1r);
        }
    }
};

Info operator+(const Info &a, const Info &b) {
    Info info;
    info.size = a.size + b.size;
    info.ans0l = a.ans0l == a.size ? a.ans0l + b.ans0l : a.ans0l;
    info.ans1l = a.ans1l == a.size ? a.ans1l + b.ans1l : a.ans1l;
    info.ans0r = b.ans0r == b.size ? b.ans0r + a.ans0r : b.ans0r;
    info.ans1r = b.ans1r == b.size ? b.ans1r + a.ans1r : b.ans1r;
    info.sum = a.sum + b.sum;
    info.ans0 = max({a.ans0, b.ans0, a.ans0r + b.ans0l});
    info.ans1 = max({a.ans1, b.ans1, a.ans1r + b.ans1l});
    return info;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    LazySegmentTree<Info, Tag> seg(a);
    while (m--) {
        int op, l, r;
        cin >> op >> l >> r;
        l++, r++;
        if (op == 0) {
            seg.rangeApply(l, r, Tag(1));
        } else if (op == 1) {
            seg.rangeApply(l, r, Tag(2));
        } else if (op == 2) {
            seg.rangeApply(l, r, Tag(3));
        } else if (op == 3) {
            cout << seg.rangeQuery(l, r).sum << "\n";
        } else {
            cout << seg.rangeQuery(l, r).ans1 << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

P5889 跳树

我们需要维护向上、向左、向右三种操作，但是操作的顺序会有影响。注意到我们可以先向上再向下，而二叉树的编号是有规律的（左儿子为 \(2p\)，右儿子为 \(2p+1\)，向上移动就是整除 2 ），因此我们可以维护一个二进制数（从低位到高位每一位都代表该位置向下的信息，为 0 的话就是向左，为 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
127
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

template <class Info, class Merge = plus<Info>>
struct SegmentTree {
    const int n;
    const Merge merge;
    vector<Info> info;
    SegmentTree(int n) : n(n), merge(Merge()), info(4 << (int)log2(n + 1)) {}
    SegmentTree(vector<Info> init) : SegmentTree(init.size() - 1) {
        function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l == r) {
                info[p] = init[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m + 1, r);
            pull(p);
        };
        build(1, 1, n);
    }
    void pull(int p) { info[p] = merge(info[2 * p], info[2 * p + 1]); }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (l == r) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x <= m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m + 1, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) { modify(1, 1, n, p, v); }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l > y || r < x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return merge(rangeQuery(2 * p, l, m, x, y),
                     rangeQuery(2 * p + 1, m + 1, r, x, y));
    }
    Info rangeQuery(int l, int r) { return rangeQuery(1, 1, n, l, r); }
};

struct Info {
    int up = 0;
    int down = 0;
    i64 num = 0;
    Info() {}
    Info(int x) {
        if (x == 1) {
            down = 1;
        } else if (x == 2) {
            down = 1;
            num = 1;
        } else if (x == 3) {
            up = 1;
        }
    }
};
Info operator+(const Info &a, const Info &b) {
    if (!a.up && !a.down) {
        return b;
    }
    if (!b.up && !b.down) {
        return a;
    }
    Info info;
    if (a.down > b.up) {
        info.up = a.up;
        info.down = a.down + b.down - b.up;
        info.num = ((a.num >> b.up) << b.down) + b.num;
    } else {
        info.up = a.up + b.up - a.down;
        info.down = b.down;
        info.num = b.num;
    }
    return info;
}

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<Info> a(m + 1);
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        a[i] = Info(x);
    }
    SegmentTree<Info> seg(a);
    while (q--) {
        int op, l, r;
        i64 s;
        cin >> op;
        if (op == 1) {
            cin >> s >> l >> r;
            Info x = seg.rangeQuery(l, r);
            cout << (max(1ll, s >> x.up) << x.down) + x.num << "\n";
        } else {
            cin >> l >> r;
            seg.modify(l, Info(r));
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

[P6186 NOI Online #1 提高组] 冒泡排序

首先在不考虑交换的情况下，考虑进行一轮冒泡排序的影响：这一轮的实质就是对于该轮的所有前缀最大值，一直往后移动，直到遇到下一个前缀最大值或结尾，这样操作之后，这几个前缀最大值与前面的数形成的逆序对数不会改变，但是其他数与前面的数形成的逆序对数都会减少 1，因此，设前缀最大值有 \(x\) 个，每轮操作后减少 \(n - x\) 个逆序对数。

因此，我们可以用树状数组来统计逆序对数（这里均指与前面的数形成的逆序对数）：如果一个数逆序对数为 0，它就是第一轮的前缀最大值，为 1 的话就是前两轮的前缀最大值，因此类推... 这样，我们通过树状数组 + 差分的思想可以求出每一轮结束后剩余的逆序对个数。下面的实现中由于把最初始的全部逆序对数放在了编号 1，第 0 次的结果应该是 \([1, 2]\)，区间修改放在编号 2。

接着考虑交换的情况：交换实际上对别的数不会造成任何影响，如果 \(a_x > a_{x+1}\)，那么总逆序对数实际上会增加 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
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

struct Fenwick {
    int n;
    vector<i64> a;
    Fenwick(int n_ = 0) { init(n_); }
    void init(int n_) {
        n = n_;
        a.assign(n + 1, 0);
    }
    void add(int x, i64 v) {
        for (int i = x; i <= n; i += i & (-i)) {
            a[i] += v;
        }
    }
    i64 sum(int x) {
        i64 res = 0;
        for (int i = x; i > 0; i -= i & (-i)) {
            res += a[i];
        }
        return res;
    }
    int rangeSum(int l, int r) { return sum(r) - sum(l - 1); }
};

void solve() {
    int n, m;
    i64 ans = 0, tmp = 0;
    cin >> n >> m;
    Fenwick bit1(n), bit2(n + 1);
    vector<int> a(n + 1), b(n + 1), d(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        b[i] = i - 1 - bit1.sum(a[i] - 1);
        d[b[i]]++;
        ans += b[i];
        bit1.add(a[i], 1);
    }
    bit2.add(1, ans);
    for (int i = 0; i < n; i++) {
        tmp += d[i];
        bit2.add(i + 2, -(n - tmp));
    }
    while (m--) {
        int op;
        i64 x;
        cin >> op >> x;
        x = min(x, (i64)n - 1);
        if (op == 1) {
            if (a[x] < a[x + 1]) {
                swap(a[x], a[x + 1]);
                swap(b[x], b[x + 1]);
                bit2.add(1, 1);
                bit2.add(b[x + 1] + 2, -1);
                b[x + 1]++;
            } else {
                swap(a[x], a[x + 1]);
                swap(b[x], b[x + 1]);
                bit2.add(1, -1);
                b[x]--;
                bit2.add(b[x] + 2, 1);
            }
        } else {
            cout << bit2.sum(x + 1) << "\n";
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}