线段树

结构体封装，需根据题目需求手动更改维护不同的量
下面代码展示维护区间最大值及最大值所在的位置

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
struct tree {
    #define ls u << 1
    #define rs u << 1 | 1
    //自定义线段树所要维护的量，存入结构体
    struct node {
        //左右建议还是加上吧，并没有更复杂
        int l, r;
        int mx, add, mxpos;//mx：区间最大值   add：区间增大的懒标记    mxpos：区间最大值出现的位置
        //根据所维护的量，重载+
        node operator+(const node &o) {
            node res;
            res.l = l;
            res.r = o.r;
            if (mx > o.mx) {
                res.mx = mx;
                res.mxpos = mxpos;
            }
            else {
                res.mx = o.mx;
                res.mxpos = o.mxpos;
            }
            return res;
        }
    }tr[N << 2];
    //要根据所维护不同量而修改
    void pushup(int u) {
        if (tr[ls].mx > tr[rs].mx) {
            tr[u].mx = tr[ls].mx;
            tr[u].mxpos = tr[ls].mxpos;
        }
        else {
            tr[u].mx = tr[rs].mx;
            tr[u].mxpos = tr[rs].mxpos;
        }
    }
    //要根据所维护不同量而修改
    void pushdown(int u) {
        if (tr[u].add) {
            tr[ls].mx += tr[u].add;
            tr[ls].add += tr[u].add;
            tr[rs].mx += tr[u].add;
            tr[rs].add += tr[u].add;
            tr[u].add = 0;
        }
    }

    void build(int u, int l, int r) {
        //要根据所维护不同量而修改
        tr[u] = {l, r, 0, 0, 0};
        if (l == r) {
            tr[u].mxpos = l;
            return ;
        }
        int mid = (l + r) / 2;
        build(ls, l, mid);
        build(rs, mid + 1, r);
        pushup(u);
    }

    void modify(int u, int l, int r, int val) {
        if (tr[u].l >= l && tr[u].r <= r) {
            //要根据所维护不同量而修改
            tr[u].mx += val;
            tr[u].add += val;
            return ;
        }
        int mid = (tr[u].l + tr[u].r) / 2;
        pushdown(u);
        if (l <= mid) {
            modify(ls, l, r, val);
        }
        if (r >= mid + 1) {
            modify(rs, l, r, val);
        }
        pushup(u);
    }

    node ask(int u, int l, int r) {
        if (l <= tr[u].l && tr[u].r <= r) {
            return tr[u];
        }
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) / 2;
        if (r <= mid) return ask(ls, l, r);
        if (l > mid) return ask(rs, l, r);
        return ask(ls, l, r) + ask(rs, l, r);
    }
}t;

评论区仅供交流，有问题请提 issue 反馈。