本文「【模板】线段树 3」的代码为新内容，其他为旧内容

核心思想：

  1. 设当前操作为将区间内值与 vv 取 min⁡\min，如果当前节点完全被操作区间包含（既满足普通线段树停止递归的条件），分类讨论：

    • max⁡≤v\max\le v

    • secmax<v<max⁡\mathrm{secmax}<v<\max

    • v≤secmaxv\le\mathrm{secmax}

  2. 对于有多种懒标记的情况，要么钦定他们的顺序，要么将他们转化成几种没有顺序关系（或者说是顺序上不冲突）的懒标记（比如几种加减标记）。

  3. 对于维护历史最值的要求，考虑标记的生命周期。

Luogu P6242 【模板】线段树 3

代码：

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXn = 5e5;
const int NINF = 0xc0c0c0c0c0c0c0c0;

template <typename T>
inline void read(T &a) {
    char c;for (c = getchar(); (c < '0' || c > '9') && c != '-'; c = getchar());bool f = c == '-';T x = f ? 0 : (c ^ '0');for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) {x = x * 10 + (c ^ '0');}a = f ? -x : x;
}
template <typename T, typename ...Argv>
inline void read(T &a, Argv &...argv) {
    read(a), read(argv...);
}

#define ls (id << 1)
#define rs (id << 1 | 1)
const int MAXnd = MAXn * 4;
int le[MAXnd + 10], ri[MAXnd + 10], mid[MAXnd + 10], len[MAXnd + 10];
int sum[MAXnd + 10], mx[MAXnd + 10], cntmx[MAXnd + 10], secmx[MAXnd + 10], hismx[MAXnd + 10];
int lz1[MAXnd + 10], lz2[MAXnd + 10], lz3[MAXnd + 10], lz4[MAXnd + 10];
/*
lz1: 最大值的增减值
lz2: 最大值的增减值生命周期中的最大值
lz3: 非最大值的增减值
lz4: 非最大值历史的增减值生命周期中的最大值
*/
inline void put(int id, int v1, int v2, int v3, int v4) {
    sum[id] += v1 * cntmx[id] + v3 * (len[id] - cntmx[id]);
    hismx[id] = max(hismx[id], mx[id] + v2);
    mx[id] += v1;
    if (secmx[id] != NINF) secmx[id] += v3;
    lz2[id] = max(lz2[id], lz1[id] + v2);
    lz1[id] += v1;
    lz4[id] = max(lz4[id], lz3[id] + v4);
    lz3[id] += v3;
}
inline void putadd(int id, int v) {
    put(id, v, v, v, v);
}
inline void putmin(int id, int v) {
    put(id, v - mx[id], v - mx[id], 0, 0);
}
inline void pushdown(int id) {
    int maxx = max(mx[ls], mx[rs]);
    if (mx[ls] == maxx) put(ls, lz1[id], lz2[id], lz3[id], lz4[id]);
    else put(ls, lz3[id], lz4[id], lz3[id], lz4[id]);
    if (mx[rs] == maxx) put(rs, lz1[id], lz2[id], lz3[id], lz4[id]);
    else put(rs, lz3[id], lz4[id], lz3[id], lz4[id]);
    lz1[id] = lz2[id] = lz3[id] = lz4[id] = 0;
}
inline void pushup(int id) {
    sum[id] = sum[ls] + sum[rs];
    mx[id] = max(mx[ls], mx[rs]);
    cntmx[id] = ((mx[ls] == mx[id]) ? cntmx[ls] : 0) + ((mx[rs] == mx[id]) ? cntmx[rs] : 0);
    secmx[id] = max((mx[ls] == mx[id]) ? secmx[ls] : mx[ls], (mx[rs] == mx[id]) ? secmx[rs] : mx[rs]);
    hismx[id] = max(hismx[ls], hismx[rs]);
}
void build(int id, int l, int r, int *a) {
    le[id] = l;
    ri[id] = r;
    mid[id] = (l + r) >> 1;
    len[id] = r - l + 1;
    if (le[id] == ri[id]) {
        sum[id] = a[le[id]];
        mx[id] = a[le[id]];
        cntmx[id] = 1;
        secmx[id] = NINF;
        hismx[id] = a[le[id]];
    } else {
        build(ls, le[id], mid[id], a);
        build(rs, mid[id] + 1, ri[id], a);
        pushup(id);
    }
}
void modifyadd(int id, int l, int r, int v) {
    if (le[id] >= l && ri[id] <= r) {
        putadd(id, v);
    } else {
        pushdown(id);
        if (l <= mid[id]) modifyadd(ls, l, r, v);
        if (r > mid[id]) modifyadd(rs, l, r, v);
        pushup(id);
    }
}
void modifymin(int id, int l, int r, int v) {
    if (v >= mx[id]) {
        ;
    } else if (v > secmx[id] && le[id] >= l && ri[id] <= r) {
        putmin(id, v);
    } else {
        pushdown(id);
        if (l <= mid[id]) modifymin(ls, l, r, v);
        if (r > mid[id]) modifymin(rs, l, r, v);
        pushup(id);
    }
}
int querysum(int id, int l, int r) {
    if (le[id] >= l && ri[id] <= r) {
        return sum[id];
    } else {
        pushdown(id);
        int ans = 0;
        if (l <= mid[id]) ans += querysum(ls, l, r);
        if (r > mid[id]) ans += querysum(rs, l, r);
        return ans;
    }
}
int querymax(int id, int l, int r) {
    if (le[id] >= l && ri[id] <= r) {
        return mx[id];
    } else {
        pushdown(id);
        int ans = NINF;
        if (l <= mid[id]) ans = max(ans, querymax(ls, l, r));
        if (r > mid[id]) ans = max(ans, querymax(rs, l, r));
        return ans;
    }
}
int queryhismax(int id, int l, int r) {
    if (le[id] >= l && ri[id] <= r) {
        return hismx[id];
    } else {
        pushdown(id);
        int ans = NINF;
        if (l <= mid[id]) ans = max(ans, queryhismax(ls, l, r));
        if (r > mid[id]) ans = max(ans, queryhismax(rs, l, r));
        return ans;
    }
}
#undef ls
#undef rs

int n, m;
int a[MAXn + 10];
signed main() {
    read(n, m);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
    }
    build(1, 1, n, a);
    for (int i = 1, opt, l, r, x; i <= m; ++i) {
        read(opt, l, r);
        if (opt == 1) {
            read(x);
            modifyadd(1, l, r, x);
        } else if (opt == 2) {
            read(x);
            modifymin(1, l, r, x);
        } else if (opt == 3) {
            printf("%lld\n", querysum(1, l, r));
        } else if (opt == 4) {
            printf("%lld\n", querymax(1, l, r));
        } else {
            printf("%lld\n", queryhismax(1, l, r));
        }
    }
    return 0;
}

DarkBzoj #4695. 最假女选手

解法一用的是钦定懒标记顺序的方法，解法二用的是转化成没有顺序关系的懒标记的方法。

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
#define ls (id << 1)
#define rs (id << 1 | 1)
int le[MAXnd + 10], ri[MAXnd + 10], mid[MAXnd + 10];
int mx[MAXnd + 10], cntmx[MAXnd + 10], secmx[MAXnd + 10], mn[MAXnd + 10], cntmn[MAXnd + 10], secmn[MAXnd + 10];
int sum[MAXnd + 10];
int lzadd[MAXnd + 10], lzmx[MAXnd + 10], lzmn[MAXnd + 10];
/*
钦定顺序: lzadd > lzmx = lzmn
*/
inline void pushup(int id)  {
    sum[id] = sum[ls] + sum[rs];
    if (mx[ls] > mx[rs]) {
        mx[id] = mx[ls];
        cntmx[id] = cntmx[ls];
        secmx[id] = max(secmx[ls], mx[rs]);
    } else if (mx[ls] < mx[rs]) {
        mx[id] = mx[rs];
        cntmx[id] = cntmx[rs];
        secmx[id] = max(mx[ls], secmx[rs]);
    } else {
        mx[id] = mx[ls];
        cntmx[id] = cntmx[ls] + cntmx[rs];
        secmx[id] = max(secmx[ls], secmx[rs]);
    }
    if (mn[ls] < mn[rs]) {
        mn[id] = mn[ls];
        cntmn[id] = cntmn[ls];
        secmn[id] = min(secmn[ls], mn[rs]);
    } else if (mn[ls] > mn[rs]) {
        mn[id] = mn[rs];
        cntmn[id] = cntmn[rs];
        secmn[id] = min(mn[ls], secmn[rs]);
    } else {
        mn[id] = mn[ls];
        cntmn[id] = cntmn[ls] + cntmn[rs];
        secmn[id] = min(secmn[ls], secmn[rs]);
    }
}
inline void putadd(int id, int padd) {
    sum[id] += padd * (ri[id] - le[id] + 1);
    mx[id] += padd;
    mn[id] += padd;
    if (secmx[id] != -INF) secmx[id] += padd;
    if (secmn[id] != INF) secmn[id] += padd;
    if (lzmx[id] != -INF) lzmx[id] += padd;
    if (lzmn[id] != INF) lzmn[id] += padd;
    lzadd[id] += padd;
}
inline void putmx(int id, int pmx) {
    if (mn[id] >= pmx) return;
    sum[id] += (pmx - mn[id]) * cntmn[id];
    if (secmx[id] == mn[id]) secmx[id] = pmx;
    if (mx[id] == mn[id]) mx[id] = pmx;
    if (lzmn[id] < pmx) lzmn[id] = pmx;
    mn[id] = lzmx[id] = pmx;
}
inline void putmn(int id, int pmn) {
    if (mx[id] <= pmn) return;
    sum[id] -= (mx[id] - pmn) * cntmx[id];
    if (secmn[id] == mx[id]) secmn[id] = pmn;
    if (mn[id] == mx[id]) mn[id] = pmn;
    if (lzmx[id] > pmn) lzmx[id] = pmn;
    mx[id] = lzmn[id] = pmn;
}
inline void pushdown(int id) {
    if (lzadd[id]) { // 注意顺序lzadd与其他懒标记的顺序
        putadd(ls, lzadd[id]);
        putadd(rs, lzadd[id]);
        lzadd[id] = 0;
    }
    if (lzmx[id] != -INF) {
        putmx(ls, lzmx[id]);
        putmx(rs, lzmx[id]);
        lzmx[id] = -INF;
    }
    if (lzmn[id] != INF) {
        putmn(ls, lzmn[id]);
        putmn(rs, lzmn[id]);
        lzmn[id] = INF;
    }
}
void Build(int id, int l, int r, int *a) {
    le[id] = l;
    ri[id] = r;
    mid[id] = (l + r) >> 1;
    lzmx[id] = -INF;
    lzmn[id] = INF;
    if (l == r) {
        mx[id] = mn[id] = sum[id] = a[l];
        cntmx[id] = cntmn[id] = 1;
        secmx[id] = -INF;
        secmn[id] = INF;
    } else {
        Build(ls, l, mid[id], a);
        Build(rs, mid[id] + 1, r, a);
        pushup(id);
    }
}
void modifyAdd(int id, int l, int r, int v) {
    if (le[id] >= l && ri[id] <= r) {
        putadd(id, v);
    } else {
        pushdown(id);
        if (l <= mid[id]) modifyAdd(ls, l, r, v);
        if (r > mid[id]) modifyAdd(rs, l, r, v);
        pushup(id);
    }
}
void modifyMax(int id, int l, int r, int v) {
    if (mn[id] >= v) return;
    if (secmn[id] > v && le[id] >= l && ri[id] <= r) {
        putmx(id, v);
    } else {
        pushdown(id);
        if (l <= mid[id]) modifyMax(ls, l, r, v);
        if (r > mid[id]) modifyMax(rs, l, r, v);
        pushup(id);
    }
}
void modifyMin(int id, int l, int r, int v) {
    if (mx[id] <= v) return;
    if (secmx[id] < v && le[id] >= l && ri[id] <= r) {
        putmn(id, v);
    } else {
        pushdown(id);
        if (l <= mid[id]) modifyMin(ls, l, r, v);
        if (r > mid[id]) modifyMin(rs, l, r, v);
        pushup(id);
    }
}
int querySum(int id, int l, int r) {
    if (le[id] >= l && ri[id] <= r) {
        return sum[id];
    } else {
        pushdown(id);
        int ans = 0;
        if (l <= mid[id]) ans += querySum(ls, l, r);
        if (r > mid[id]) ans += querySum(rs, l, r);
        return ans;
    }
}
int queryMax(int id, int l, int r) {
    if (le[id] >= l && ri[id] <= r) {
        return mx[id];
    } else {
        pushdown(id);
        int ans = -INF;
        if (l <= mid[id]) ans = max(ans, queryMax(ls, l, r));
        if (r > mid[id]) ans = max(ans, queryMax(rs, l, r));
        return ans;
    }
}
int queryMin(int id, int l, int r) {
    if (le[id] >= l && ri[id] <= r) {
        return mn[id];
    } else {
        pushdown(id);
        int ans = INF;
        if (l <= mid[id]) ans = min(ans, queryMin(ls, l, r));
        if (r > mid[id]) ans = min(ans, queryMin(rs, l, r));
        return ans;
    }
}
#undef ls
#undef rs
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
#define ls (id << 1)
#define rs (id << 1 | 1)
int le[MAXnd + 10], ri[MAXnd + 10], mid[MAXnd + 10], len[MAXnd + 10];
int mx[MAXnd + 10], cntmx[MAXnd + 10], secmx[MAXnd + 10], mn[MAXnd + 10], cntmn[MAXnd + 10], secmn[MAXnd + 10];
int sum[MAXnd + 10];
int lz1[MAXnd + 10], lz2[MAXnd + 10], lz3[MAXnd + 10];
/*
lz1: 最大值的增减值
lz2: 最小值的增减值
lz3: 非最小最大值的增减值
*/
inline void pushup(int id) {
    if (mx[ls] > mx[rs]) {
        mx[id] = mx[ls];
        cntmx[id] = cntmx[ls];
        secmx[id] = max(secmx[ls], mx[rs]);
    } else if (mx[ls] < mx[rs]) {
        mx[id] = mx[rs];
        cntmx[id] = cntmx[rs];
        secmx[id] = max(mx[ls], secmx[rs]);
    } else {
        mx[id] = mx[ls];
        cntmx[id] = cntmx[ls] + cntmx[rs];
        secmx[id] = max(secmx[ls], secmx[rs]);
    }
    if (mn[ls] < mn[rs]) {
        mn[id] = mn[ls];
        cntmn[id] = cntmn[ls];
        secmn[id] = min(secmn[ls], mn[rs]);
    } else if (mn[ls] > mn[rs]) {
        mn[id] = mn[rs];
        cntmn[id] = cntmn[rs];
        secmn[id] = min(mn[ls], secmn[rs]);
    } else {
        mn[id] = mn[ls];
        cntmn[id] = cntmn[ls] + cntmn[rs];
        secmn[id] = min(secmn[ls], secmn[rs]);
    }
    sum[id] = sum[ls] + sum[rs];
}
inline void update(int id, int v1, int v2, int v3) {
    if (mx[id] == secmn[id]) {
        sum[id] += v1 * cntmx[id] + v2 * cntmn[id];
        mx[id] += v1;
        mn[id] += v2;
        secmx[id] += v2;
        secmn[id] += v1;
        lz1[id] += v1;
        lz2[id] += v2;
    } else if (mx[id] == mn[id]) {
        if (v1) {
            sum[id] += v1 * cntmx[id];
            mx[id] += v1;
            mn[id] += v1;
            lz1[id] += v1;
            lz2[id] += v1;
        } else if (v2) {
            sum[id] += v2 * cntmx[id];
            mx[id] += v2;
            mn[id] += v2;
            lz1[id] += v2;
            lz2[id] += v2;
        } else {
            sum[id] += v3 * cntmx[id];
            mx[id] += v3;
            mn[id] += v3;
            lz1[id] += v3;
            lz2[id] += v3;
        }
    } else {
        sum[id] += v1 * cntmx[id] + v2 * cntmn[id] + v3 * (len[id] - cntmx[id] - cntmn[id]);
        mx[id] += v1;
        mn[id] += v2;
        secmx[id] += v3;
        secmn[id] += v3;
        lz1[id] += v1;
        lz2[id] += v2;
        lz3[id] += v3;
    }
}
inline void pushdown(int id) {
    int maxx = max(mx[ls], mx[rs]), minn = min(mn[ls], mn[rs]);
    if (mx[ls] == mn[ls]) update(ls, mx[ls] == maxx ? lz1[id] : 0, mn[ls] == minn ? lz2[id] : 0, lz3[id]);
    else update(ls, mx[ls] == maxx ? lz1[id] : lz3[id], mn[ls] == minn ? lz2[id] : lz3[id], lz3[id]);
    if (mx[rs] == mn[rs]) update(rs, mx[rs] == maxx ? lz1[id] : 0, mn[rs] == minn ? lz2[id] : 0, lz3[id]);
    else update(rs, mx[rs] == maxx ? lz1[id] : lz3[id], mn[rs] == minn ? lz2[id] : lz3[id], lz3[id]);
    lz1[id] = lz2[id] = lz3[id] = 0;
}
void Build(int id, int l, int r, int *a) {
    le[id] = l;
    ri[id] = r;
    mid[id] = (l + r) >> 1;
    len[id] = r - l + 1;
    if (l == r)  {
        mn[id] = mx[id] = sum[id] = a[l];
        cntmn[id] = cntmx[id] = 1;
        secmn[id] = INF;
        secmx[id] = -INF;
    } else {
        Build(ls, l, mid[id], a);
        Build(rs, mid[id] + 1, r, a);
        pushup(id);
    }
}
void modifyAdd(int id, int l, int r, int v) {
    if (le[id] >= l && ri[id] <= r) {
        update(id, v, v, v);
    } else {
        pushdown(id);
        if (l <= mid[id]) modifyAdd(ls, l, r, v);
        if (r > mid[id]) modifyAdd(rs, l, r, v);
        pushup(id);
    }
}
void modifyMin(int id, int l, int r, int v) {
    if (mx[id] <= v) return;
    if (secmx[id] < v && le[id] >= l && ri[id] <= r) {
        update(id, v - mx[id], 0, 0);
    } else {
        pushdown(id);
        if (l <= mid[id]) modifyMin(ls, l, r, v);
        if (r > mid[id]) modifyMin(rs, l, r, v);
        pushup(id);
    }
}
void modifyMax(int id, int l, int r, int v) {
    if (mn[id] >= v) return;
    if (secmn[id] > v && le[id] >= l && ri[id] <= r) {
        update(id, 0, v - mn[id], 0);
    } else {
        pushdown(id);
        if (l <= mid[id]) modifyMax(ls, l, r, v);
        if (r > mid[id]) modifyMax(rs, l, r, v);
        pushup(id);
    }
}
int querySum(int id, int l, int r) {
    if (le[id] >= l && ri[id] <= r) {
        return sum[id];
    } else {
        pushdown(id);
        int ans = 0;
        if (l <= mid[id]) ans += querySum(ls, l, r);
        if (r > mid[id]) ans += querySum(rs, l, r);
        return ans;
    }
}
int queryMin(int id, int l, int r) {
    if (le[id] >= l && ri[id] <= r) {
        return mn[id];
    } else {
        pushdown(id);
        int ans = INF;
        if (l <= mid[id]) ans = min(ans, queryMin(ls, l, r));
        if (r > mid[id]) ans = min(ans, queryMin(rs, l, r));
        return ans;
    }
}
int queryMax(int id, int l, int r) {
    if (le[id] >= l && ri[id] <= r) {
        return mx[id];
    } else {
        pushdown(id);
        int ans = -INF;
        if (l <= mid[id]) ans = max(ans, queryMax(ls, l, r));
        if (r > mid[id]) ans = max(ans, queryMax(rs, l, r));
        return ans;
    }
}
#undef ls
#undef rs

Luogu P4314 CPU 监控

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
#define ls (id << 1)
#define rs (id << 1 | 1)
int le[MAXnd + 10], ri[MAXnd + 10], mid[MAXnd + 10], len[MAXnd + 10];
int mx[MAXnd + 10], hismx[MAXnd + 10];
int lz1[MAXnd + 10], lz2[MAXnd + 10], lz3[MAXnd + 10], lz4[MAXnd + 10], lz5[MAXnd + 10];
/*
lz1: 末段增减值
lz2: 末段增减值的历史最大值
lz3: 首段增减值的历史最大值
lz4: (如果有)末端覆盖值
lz5: (如果有)中间段的最大值
*/
inline void pushup(int id) {
    mx[id] = max(mx[ls], mx[rs]);
    hismx[id] = max(hismx[ls], hismx[rs]);
}
inline void update(int id, int v1, int v2, int v3, int v4, int v5) {
    if (v4 == INF) {
        if (lz4[id] == INF) {
            hismx[id] = max(hismx[id], mx[id] + v3);
            mx[id] = mx[id] + v1;
            lz2[id] = lz3[id] = max(lz2[id], lz1[id] + v3);
            lz1[id] = lz1[id] + v1;
        } else {
            hismx[id] = max(hismx[id], mx[id] + v3);
            mx[id] = mx[id] + v1;
            lz2[id] = max(lz2[id], lz1[id] + v3);
            lz1[id] = lz1[id] + v1;
        }
    } else {
        if (lz4[id] == INF) {
            hismx[id] = max(max(max(hismx[id], mx[id] + v3), v5), v4 + v2);
            mx[id] = v4 + v1;
            lz3[id] = max(lz3[id], lz1[id] + v3);
            lz1[id] = v1;
            lz2[id] = v2;
            lz4[id] = v4;
            lz5[id] = v5;
        } else {
            hismx[id] = max(max(max(hismx[id], mx[id] + v3), v5), v4 + v2);
            mx[id] = v4 + v1;
            lz5[id] = max(max(max(lz5[id], v5), lz4[id] + lz2[id]), lz4[id] + lz1[id] + v3);
            lz1[id] = v1;
            lz2[id] = v2;
            lz4[id] = v4;
        }
    }
}
inline void pushdown(int id) {
    update(ls, lz1[id], lz2[id], lz3[id], lz4[id], lz5[id]);
    update(rs, lz1[id], lz2[id], lz3[id], lz4[id], lz5[id]);
    lz1[id] = lz2[id] = lz3[id] = 0;
    lz4[id] = INF;
    lz5[id] = -INF;
}
void Build(int id, int l, int r, int *a) {
    le[id] = l;
    ri[id] = r;
    mid[id] = (l + r) >> 1;
    len[id] = r - l + 1;
    lz4[id] = INF;
    lz5[id] = -INF;
    if (l == r) {
        mx[id] = hismx[id] = a[l];
    } else {
        Build(ls, l, mid[id], a);
        Build(rs, mid[id] + 1, r, a);
        pushup(id);
    }
}
void modifyAdd(int id, int l, int r, int v) {
    if (le[id] >= l && ri[id] <= r) {
        update(id, v, v, v, INF, -INF);
    } else {
        pushdown(id);
        if (l <= mid[id]) modifyAdd(ls, l, r, v);
        if (r > mid[id]) modifyAdd(rs, l, r, v);
        pushup(id);
    }
}
void modifyRep(int id, int l, int r, int v) {
    if (le[id] >= l && ri[id] <= r) {
        mx[id] = v;
        hismx[id] = max(hismx[id], v);
        if (lz4[id] != INF) lz5[id] = max(lz5[id], lz4[id] + lz2[id]);
        lz1[id] = lz2[id] = 0;
        lz4[id] = v;
    } else {
        pushdown(id);
        if (l <= mid[id]) modifyRep(ls, l, r, v);
        if (r > mid[id]) modifyRep(rs, l, r, v);
        pushup(id);
    }
}
int queryMax(int id, int l, int r) {
    if (le[id] >= l && ri[id] <= r) {
        return mx[id];
    } else {
        pushdown(id);
        int ans = -INF;
        if (l <= mid[id]) ans = max(ans, queryMax(ls, l, r));
        if (r > mid[id]) ans = max(ans, queryMax(rs, l, r));
        return ans;
    }
}
int queryHisMax(int id, int l, int r) {
    if (le[id] >= l && ri[id] <= r) {
        return hismx[id];
    } else {
        pushdown(id);
        int ans = -INF;
        if (l <= mid[id]) ans = max(ans, queryHisMax(ls, l, r));
        if (r > mid[id]) ans = max(ans, queryHisMax(rs, l, r));
        return ans;
    }
}
#undef ls
#undef rs