线段树

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
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(vector<Info>(n_ + 1, v_)); }
    LazySegmentTree(vector<Info> t_) { init(t_); }
    void init(vector<Info> a)  //[1,n]
    {
        n = a.size() - 1;
        info.assign((n << 2) + 1, Info());
        tag.assign((n << 2) + 1, Tag());
        function<void(int, int, int)> build = [&](int x, int l, int r) -> void {
            if (l == r) {
                info[x] = a[l];
                return;
            }
            int mid = (l + r) >> 1;
            build(x << 1, l, mid);
            build(x << 1 | 1, mid + 1, r);
            pushup(x);
        };
        build(1, 1, n);
    }
    void pushup(int x) { info[x] = info[x << 1] + info[x << 1 | 1]; }
    void apply(int p, const Tag& v) {
        info[p].apply(v);  // 标记更新其他变量
        tag[p].apply(v);   // 更新标记
    }
    void pushdown(int x) {
        apply(x << 1, tag[x]);  // 下传标记
        apply(x << 1 | 1, tag[x]);
        tag[x] = Tag();  // 清空标记
    }
    void update(int x, int l, int r, int p, const Info& v) {
        if (l == r) {
            info[x] = v;
            return;
        }
        int mid = (l + r) >> 1;
        pushdown(x);
        if (p <= mid)
            update(x << 1, l, mid, p, v);
        else
            update(x << 1 | 1, mid + 1, r, p, v);
        pushup(x);
    }
    void update(int p, const Info& v) { update(1, 1, n, p, v); }
    Info query(int x, int l, int r, int ql, int qr) {
        if (l > qr || r < ql)
            return Info();
        if (ql <= l && r <= qr)
            return info[x];
        int mid = (l + r) >> 1;
        pushdown(x);
        return query(x << 1, l, mid, ql, qr) +
               query(x << 1 | 1, mid + 1, r, ql, qr);
    }
    Info query(int ql, int qr) { return query(1, 1, n, ql, qr); }
    void rangeupdate(int x, int l, int r, int ql, int qr, const Tag& v) {
        if (l > qr || r < ql)
            return;
        if (ql <= l && r <= qr) {
            apply(x, v);
            return;
        }
        int mid = (l + r) >> 1;
        pushdown(x);
        rangeupdate(x << 1, l, mid, ql, qr, v);
        rangeupdate(x << 1 | 1, mid + 1, r, ql, qr, v);
        pushup(x);
    }
    void rangeupdate(int ql, int qr, const Tag& v) {
        rangeupdate(1, 1, n, ql, qr, v);
    }
    template <class F>
    int findFirst(int x, int l, int r, int ql, int qr, F pred) {
        if (l > qr || r < ql || !pred(info[x]))
            return -1;
        if (l == r)
            return l;
        int mid = (l + r) >> 1;
        pushdown(x);
        int res = findFirst(x << 1, l, mid, ql, qr, pred);
        if (res == -1)
            res = findFirst(x << 1 | 1, mid + 1, r, ql, qr, pred);
        return res;
    }
    template <class F>
    int findFirst(int l, int r, F pred) {
        return findFirst(1, 1, n, l, r, pred);
    }
    template <class F>
    int findLast(int x, int l, int r, int ql, int qr, F pred) {
        if (l > qr || r < ql || !pred(info[x]))
            return -1;
        if (l == r)
            return l;
        int mid = (l + r) >> 1;
        pushdown(x);
        int res = findLast(x << 1 | 1, mid + 1, r, ql, qr, pred);
        if (res == -1)
            res = findLast(x << 1, l, mid, ql, qr, pred);
        return res;
    }
    template <class F>
    int findLast(int l, int r, F pred) {
        return findLast(1, 1, n, l, r, pred);
    }
};
struct Tag {
    ll add = 0;
    void apply(const Tag& v) { add += v.add; }  // 标记怎么合并
};
struct Info {
    ll sum = 0, len = 1;
    void apply(const Tag& v) { sum += len * v.add; }  // 标记怎么更新节点信息
};
Info operator+(const Info& a, const Info& b) {  // 维护的信息怎么合并
    Info c = Info();
    c.sum = a.sum + b.sum;
    c.len = a.len + b.len;
    return c;
};