跳转至

线段树

模版
代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
i64 a[100005];
template<class Info, class T>
struct SegmentTree {
    int N;
    vector<Info> tr;
    SegmentTree(int n) {
        init(n);
    }
    void init(int n) {
        N = n;
        n <<= 2;
        tr.resize(0);
        tr.resize(n);
    }
    void build() {
        build(1, 1, N);
    }
    void build(int p, int L, int R) {
        if (L == R) {
            tr[p] = buildInit(L);
            return;
        }
        int mid = (L + R) >> 1;
        build(p << 1, L, mid);
        build(p << 1 | 1, mid + 1, R);
        pushup(p);
    }
    void pushup(int p) {
        tr[p] = merge(tr[p << 1], tr[p << 1 | 1]);
    }
    void rangeModify(int QL, int QR, T x) {
        return rangeModify(1, QL, QR, x);
    }
    void rangeModify(int p, int QL, int QR, T x) {
        if (QL <= tr[p].L && tr[p].R <= QR) {
            pushtag(p, x);
            return;
        }
        int mid = (tr[p].L + tr[p].R) >> 1;
        if (QL <= mid) rangeModify(p << 1, QL, QR, x);
        if (QR >= mid + 1) rangeModify(p << 1 | 1, QL, QR, x);
        pushup(p);
    }
    Info rangeQuery(int QL, int QR) {
        return rangeQuery(1, QL, QR);
    }
    Info rangeQuery(int p, int QL, int QR) {
        if (QL <= tr[p].L && tr[p].R <= QR) {
            return tr[p];
        }
        int mid = (tr[p].L + tr[p].R) >> 1;
        if (QR <= mid) return rangeQuery(p << 1, QL, QR);
        if (QL >= mid + 1) return rangeQuery(p << 1 | 1, QL, QR);
        return merge(rangeQuery(p << 1, QL, QR), rangeQuery(p << 1 | 1, QL, QR));
    }
    // 建树初始化
    Info buildInit(int L) {
        return {L, L, a[L] % P};
    }
    // 两节点合并
    Info merge(const Info &lhs, const Info &rhs) {
        return {lhs.L, rhs.R, (lhs.sum + rhs.sum) % P};
    }
    // 节点打标记
    void pushtag(int p, T x) {
        tr[p] = x;
    }
}; // SegmentTree
struct Info {
    int L, R;
    i64 sum;
};
代码
C++
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
i64 P;
i64 a[100005];
template<class Info, class Lazy, class T>
struct SegmentTree {
    int N;
    vector<Info> tr;
    vector<Lazy> tag;
    SegmentTree(int n) {
        init(n);
    }
    void init(int n) {
        N = n;
        n <<= 2;
        tr.resize(0);
        tr.resize(n);
        tag.resize(0);
        tag.resize(n);
    }
    void build() {
        build(1, 1, N);
    }
    void build(int p, int L, int R) {
        if (L == R) {
            tr[p] = buildInit(L);
            return;
        }
        int mid = (L + R) >> 1;
        build(p << 1, L, mid);
        build(p << 1 | 1, mid + 1, R);
        pushup(p);
    }
    void pushup(int p) {
        tr[p] = merge(tr[p << 1], tr[p << 1 | 1]);
    }
    void pushdown(int p) {
        pushtag(p << 1, tag[p]);
        pushtag(p << 1 | 1, tag[p]);
        tag[p] = Lazy();
    }
    void rangeModify(int QL, int QR, T x) {
        return rangeModify(1, QL, QR, x);
    }
    void rangeModify(int p, int QL, int QR, T x) {
        if (QL <= tr[p].L && tr[p].R <= QR) {
            pushtag(p, x);
            return;
        }
        pushdown(p);
        int mid = (tr[p].L + tr[p].R) >> 1;
        if (QL <= mid) rangeModify(p << 1, QL, QR, x);
        if (QR >= mid + 1) rangeModify(p << 1 | 1, QL, QR, x);
        pushup(p);
    }
    Info rangeQuery(int QL, int QR) {
        return rangeQuery(1, QL, QR);
    }
    Info rangeQuery(int p, int QL, int QR) {
        if (QL <= tr[p].L && tr[p].R <= QR) {
            return tr[p];
        }
        pushdown(p);
        int mid = (tr[p].L + tr[p].R) >> 1;
        if (QR <= mid) return rangeQuery(p << 1, QL, QR);
        if (QL >= mid + 1) return rangeQuery(p << 1 | 1, QL, QR);
        return merge(rangeQuery(p << 1, QL, QR), rangeQuery(p << 1 | 1, QL, QR));
    }
    // 建树初始化
    Info buildInit(int L) {
        return {L, L, a[L] % P};
    }
    // 两节点合并
    Info merge(const Info &lhs, const Info &rhs) {
        Info res;
        res.L = lhs.L;
        res.R = rhs.R;
        res.sum = (lhs.sum + rhs.sum) % P;
        return res;
        return {lhs.L, rhs.R, (lhs.sum + rhs.sum) % P};
    }
    // 节点打标记
    void pushtag(int p, T lazy) {
        if (lazy.prod != 1) {
            tag[p].prod = tag[p].prod * lazy.prod % P;
            tag[p].add = tag[p].add * lazy.prod % P;
            tr[p].sum = tr[p].sum * lazy.prod % P;
        }
        if (lazy.add != 0) {
            tag[p].add = (tag[p].add + lazy.add) % P;
            tr[p].sum = (tr[p].sum + (tr[p].R - tr[p].L + 1) * lazy.add % P) % P;
        }
    }
}; // SegmentTree
struct Info {
    int L, R;
    i64 sum;
};
struct Lazy {
    i64 add, prod;
    // 懒标记初始化
    Lazy() {
        add = 0;
        prod = 1;
    }
};

线段树合并

例题

树，每次操作给x到y上发一个类型为z的物品

问最终每个点存放数量最多的物品的类型。

代码
C++
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
using namespace std;
// 2024 OneWan
const int N = 100005;
vector<int> adj[N];
int fa[N][22], deep[N], tot;
void dfs(int u, int p) {
    fa[u][0] = p;
    deep[u] = deep[p] + 1;
    for (int i = 1 ; i <= 21 ; i++) {
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    for (auto &to : adj[u]) {
        if (to == p) continue;
        dfs(to, u);
    }
}
int LCA(int x, int y) {
    if (deep[x] < deep[y]) swap(x, y);
    for (int i = 21 ; i >= 0 ; i--) {
        if (deep[fa[x][i]] < deep[y]) continue;
        x = fa[x][i];
    }
    if (x == y) return x;
    for (int i = 21 ; i >= 0 ; i--) {
        if (fa[x][i] == fa[y][i]) continue;
        x = fa[x][i];
        y = fa[y][i];
    }
    return fa[x][0];
}
int Ls[N << 8], Rs[N << 8], sum[N << 8], typ[N << 8];
void pushup(int p) {
    if (sum[Ls[p]] >= sum[Rs[p]]) {
        sum[p] = sum[Ls[p]];
        typ[p] = typ[Ls[p]];
    } else {
        sum[p] = sum[Rs[p]];
        typ[p] = typ[Rs[p]];
    }
}
int change(int &p, int pos, int k, int L = 1, int R = N) {
    if (p == 0) p = ++tot;
    if (L == R) {
        sum[p] += k;
        typ[p] = pos;
        return p;
    }
    int mid = L + R >> 1;
    if (pos <= mid) change(Ls[p], pos, k, L, mid);
    else change(Rs[p], pos, k, mid + 1, R);
    pushup(p);
    return p;
}
int merge(int rtL, int rtR, int L = 1, int R = N) {
    if (rtL == 0 || rtR == 0) return rtL + rtR;
    if (L == R) {
        sum[rtL] += sum[rtR];
        typ[rtL] = L;
        return rtL;
    }
    int mid = L + R >> 1;
    Ls[rtL] = merge(Ls[rtL], Ls[rtR], L, mid);
    Rs[rtL] = merge(Rs[rtL], Rs[rtR], mid + 1, R);
    pushup(rtL);
    return rtL;
}
int ans[N];
int root[N];
void solve(int u, int p) {
    for (auto &to : adj[u]) {
        if (to == p) continue;
        solve(to, u);
        root[u] = merge(root[u], root[to]);
    }
    if (sum[root[u]]) {
        ans[u] = typ[root[u]];
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1 ; i < n ; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1 ; i <= m ; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        int k = LCA(x, y);
        root[x] = change(root[x], z, 1);
        root[y] = change(root[y], z, 1);
        root[k] = change(root[k], z, -1);
        if (fa[k][0]) {
            root[fa[k][0]] = change(root[fa[k][0]], z, -1);
        }
    }
    solve(1, 0);
    for (int i = 1 ; i <= n ; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}
习题

Problem - F - Codeforces

n排列中，求所有满足 \(\max-\min=R-L\) 的区间，(此代码可以求重复排列)

代码
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <bits/stdc++.h>
using namespace std;
// 2024 OneWan
const int N = 300005;
int n, a[N];
int st1[N], t1, st2[N], t2;
map <int, int> last;
struct Info {
    int L, R, mi, cnt;
    int lazy;
} tr[N<<2];
void build(int p, int L, int R) {
    tr[p].L = L;
    tr[p].R = R;
    tr[p].cnt = R - L + 1;
    if (L == R) {
        return;
    }
    int mid = L + R >> 1;
    build(p << 1, L, mid);
    build(p << 1 | 1, mid + 1, R);
}
void pushup(int p) {
    tr[p].mi = min(tr[p << 1].mi, tr[p << 1 | 1].mi);
    tr[p].cnt = (tr[p].mi == tr[p << 1].mi ? tr[p << 1].cnt : 0) + (tr[p].mi == tr[p << 1 | 1].mi ? tr[p << 1 | 1].cnt : 0);
}
void pushtag(int p, int tag) {
    tr[p].mi += tag;
    tr[p].lazy += tag;
}
void pushdown(int p) {
    if (tr[p].lazy) {
        pushtag(p << 1, tr[p].lazy);
        pushtag(p << 1 | 1, tr[p].lazy);
        tr[p].lazy = 0;
    }
}
void modify(int p, int QL, int QR, int k) {
    if (QL <= tr[p].L && tr[p].R <= QR) {
        pushtag(p, k);
        return;
    }
    pushdown(p);
    int mid = tr[p].L + tr[p].R >> 1;
    if (QR <= mid) modify(p << 1, QL, QR, k);
    else if (QL >= mid + 1) modify(p << 1 | 1, QL, QR, k);
    else {
        modify(p << 1, QL, QR, k);
        modify(p << 1 | 1, QL, QR, k);
    }
    pushup(p);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1, x, y; i <= n; i++) {
        cin >> x >> y;
        a[x] = y;
    }
    build(1, 1, n);
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        while (t1 && a[st1[t1]] < a[i]) { // 维护 max
            modify(1, st1[t1 - 1] + 1, st1[t1], -a[st1[t1]]); // 撤销
            t1--;
        }
        while (t2 && a[st2[t2]] > a[i]) { // 维护 min
            modify(1, st2[t2 - 1] + 1, st2[t2], a[st2[t2]]); // 撤销
            t2--;
        }
        modify(1, last[a[i]] + 1, i, -1);
        last[a[i]] = st1[++t1] = st2[++t2] = i;
        modify(1, st1[t1 - 1] + 1, i, a[i]);
        modify(1, st2[t2 - 1] + 1, i, -a[i]);
        ans += tr[1].cnt;
    }
    cout << ans << "\n";
    return 0;
}

L-最长连续相同字符_2023河南萌新联赛第（二）场：河南工业大学

如题。

代码
C++
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
const int MAXN = 100000;
string str;
int Lmx[MAXN << 4], Rmx[MAXN << 4], mx[MAXN << 4], Lc[MAXN << 4], Rc[MAXN << 4];
void push(const int p, const int L, const int R, const int mid) {
    const int x = p << 1, y = p << 1 | 1;
    Lmx[p] = Lmx[x];
    Rmx[p] = Rmx[y];
    if (Lmx[x] == mid - L + 1 && str[mid] == str[mid + 1]) {
        Lmx[p] += Lmx[y];
    }
    if (Rmx[y] == R - mid && str[mid] == str[mid + 1]) {
        Rmx[p] += Rmx[x];
    }
    if (mx[x] >= mx[y]) {
        mx[p] = mx[x];
        Lc[p] = Lc[x];
        Rc[p] = Rc[x];
    } else {
        mx[p] = mx[y];
        Lc[p] = Lc[y];
        Rc[p] = Rc[y];
    }
    if (str[mid] == str[mid + 1]) {
        if (mx[p] < Rmx[x] + Lmx[y]) {
            mx[p] = Rmx[x] + Lmx[y];
            Lc[p] = mid - Rmx[x] + 1;
            Rc[p] = mid + Lmx[y];
        } else if (mx[p] == Rmx[x] + Lmx[y]) {
            if (Lc[p] > mid - Rmx[x] + 1) {
                Lc[p] = mid - Rmx[x] + 1;
                Rc[p] = mid + Lmx[y];
            }
        }
    }
}
void build(const int p, const int L, const int R) {
    if (L == R) {
        Lmx[p] = Rmx[p] = mx[p] = 1;
        Lc[p] = Rc[p] = L;
        return;
    }
    const int mid = L + R >> 1;
    build(p << 1, L, mid);
    build(p << 1 | 1, mid + 1, R);
    push(p, L, R, mid);
}
void modify(const int p, const int pos, const char ch, const int L, const int R) {
    if (R < pos || L > pos) {
        return;
    }
    if (L == R) {
        str[L] = ch;
        return;
    }
    const int mid = L + R >> 1;
    modify(p << 1, pos, ch, L, mid);
    modify(p << 1 | 1, pos, ch, mid + 1, R);
    push(p, L, R, mid);
}
pair<int, int> query(const int p, const int QL, const int QR, const int L, const int R) {
    if (QR < L || QL > R) {
        return {1, 0};
    }
    if (QL <= L && R <= QR) {
        return {Lc[p], Rc[p]};
    }
    const int mid = L + R >> 1;
    auto resL = query(p << 1, QL, QR, L, mid);
    pair<int, int> resMid = {1, 0};
    if (str[mid] == str[mid + 1] && mid >= QL && mid + 1 <= QR) {
        resMid = {max(QL, mid - Rmx[p << 1] + 1), min(QR, mid + Lmx[p << 1 | 1])};
    }
    if (resL.second - resL.first + 1 < resMid.second - resMid.first + 1) {
        resL = resMid;
    }
    auto resR = query(p << 1 | 1, QL, QR, mid + 1, R);
    if (resL.second - resL.first + 1 < resR.second - resR.first + 1) {
        resL = resR;
    }
    return resL;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    cin >> str;
    str = " " + str;
    build(1, 1, n);
    for (int i = 0 ; i < m ; i++) {
        int op;
        cin >> op;
        if (op == 1) {
            int L, R;
            cin >> L >> R;
            if (L == 0) L = 1;
            auto [x, y] = query(1, L, R, 1, n);
            cout << x << " " << y << "\n";
        } else {
            int x;
            char ch;
            cin >> x >> ch;
            modify(1, x, ch, 1, n);
        }
    }
    return 0;
}

魔术师【算法赛】 - 蓝桥云课

image-20240423115727184

代码
C++
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include <bits/stdc++.h>
using namespace std;
// 2023 OneWan
const int N = 100000 + 5;
// const int M = 1 << __lg(N + 5) + 1;
const int M = N << 4;
const long long mod = 998244353;

struct Node {
    int L, R;
    long long sum[3];
    Node() {
        for (int i = 0 ; i < 3 ; i++) {
            sum[i] = 0;
        }
    }
    friend Node operator+ (const Node &lhs, const Node &rhs) {
        Node res;
        res.L = lhs.L;
        res.R = rhs.R;
        for (int i = 0 ; i < 3 ; i++) {
            res.sum[i] = (lhs.sum[i] + rhs.sum[i]) % mod;
        }
        return res;
    }

} tr[M];
struct Tag {
    int to[3];
    long long mul[3];
    Tag() {
        for (int i = 0 ; i < 3 ; i++) {
            to[i] = i;
            mul[i] = 1;
        }
    }
} lazy[M];

int a[N];

void pushtag(int p, Tag tag) {
    {
        Node res;
        res.L = tr[p].L;
        res.R = tr[p].R;
        for (int i = 0 ; i < 3 ; i++) {
            res.sum[tag.to[i]] = (res.sum[tag.to[i]] + tag.mul[i] * tr[p].sum[i] % mod) % mod;
        }
        tr[p] = res;
    }
    {
        Tag res;
        for (int i = 0 ; i < 3 ; i++) {
            res.to[i] = tag.to[lazy[p].to[i]];
            res.mul[i] = lazy[p].mul[i] * tag.mul[lazy[p].to[i]] % mod;    
        }
        lazy[p] = res;
    }
}
// 
void pushdown(int p) {
    pushtag(p << 1, lazy[p]);
    pushtag(p << 1 | 1, lazy[p]);
    lazy[p] = Tag();
}
int n;
void build(int p = 1, int L = 1, int R = n) {
    tr[p].L = L;
    tr[p].R = R;
    if (L == R) {
        tr[p].sum[a[L]] = 1;
        return;
    }
    int mid = L + R >> 1;
    build(p << 1, L, mid);
    build(p << 1 | 1, mid + 1, R);
    tr[p] = tr[p << 1] + tr[p << 1 | 1];
}

void modify(int p, int QL, int QR, Tag tag) {
    if (QL <= tr[p].L && tr[p].R <= QR) {
        pushtag(p, tag);
        return;
    }
    pushdown(p);
    int mid = tr[p].L + tr[p].R >> 1;
    if (QL <= mid) modify(p << 1, QL, QR, tag);
    if (QR >= mid + 1) modify(p << 1 | 1, QL, QR, tag);
    tr[p] = tr[p << 1] + tr[p << 1 | 1];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int m;
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
        a[i]--;
    }
    build();
    for (int i = 1 ; i <= m ; i++) {
        int L, R, op;
        cin >> L >> R >> op;
        Tag tag;
        if (op == 1) {
            int x, y;
            cin >> x >> y;
            x--;
            y--;
            tag.to[x] = y;
            tag.to[y] = x;
        }
        if (op == 2) {
            int x, y;
            cin >> x >> y;
            x--;
            y--;
            tag.to[x] = y;
        }
        if (op == 3) {
            int x;
            cin >> x;
            x--;
            tag.mul[x] = 2;
        }
        modify(1, L, R, tag);
        cout << tr[1].sum[0] << " " << tr[1].sum[1] << " " << tr[1].sum[2] << "\n";
    }
    return 0;
}