本文「线段树套线段树」板块为新内容，「线段树套平衡树」板块为旧内容

线段树套线段树

注意事项：

  1. 代码中的函数和变量有的带后缀 b，有的带后缀 a，如 modifya。带后缀 b 的代表 big，表示较大的一层，也就是外层，这与分块的变量的后缀相同。但是内层用的后缀不是 s，而是 a，这是因为后缀 s 会导致歧义，比如变量 r 带后缀 s 会变成 rs，而 rs 本来就是变量名。

  2. 需要注意内层线段树开的数组大小，是 MAXm * MAXcovn * MAXlaya，其中 m 表示操作数，n 表示外层线段树所在区间的大小，a 表示内层线段树所在区间的大小，而 cov 表示线段树区间操作中被完全覆盖且祖先没有被完全覆盖的节点数量，maxcovn=(⌈log⁡n⌉−1)×2\text{maxcov}n=(\lceil\log n\rceil-1)\times 2。

代码：

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
const int MAXnda = MAXm * MAXcovn * MAXlaya;
int cntnd, ls[MAXnda + 10], rs[MAXnda + 10];
int sum[MAXnda + 10];
inline void pushup(int id) {
    sum[id] = sum[ls[id]] + sum[rs[id]];
}
void modifya(int &id, int p, int v, int le, int ri) {
    if (id == 0) id = ++cntnd;
    if (le == ri) {
        sum[id] += v;
    } else {
        int mid = (le + ri) >> 1;
        if (p <= mid) modifya(ls[id], p, v, le, mid);
        else modifya(rs[id], p, v, mid + 1, ri);
        pushup(id);
    }
}
int querya(int id, int l, int r, int le, int ri) {
    if (id == 0) return 0;
    if (le >= l && ri <= r) {
        return sum[id];
    } else {
        int mid = (le + ri) >> 1, ans = 0;
        if (l <= mid) ans += querya(ls[id], l, r, le, mid);
        if (r > mid) ans += querya(rs[id], l, r, mid + 1, ri);
        return ans;
    }
}

#define ls (id << 1)
#define rs (id << 1 | 1)
const int MAXndb = MAXn * 4;
int le[MAXndb + 10], ri[MAXndb + 10], mid[MAXndb + 10];
int root[MAXndb + 10];
void buildb(int id, int *a, int l, int r) {
    le[id] = l;
    ri[id] = r;
    mid[id] = (l + r) >> 1;
    for (int i = le[id]; i <= ri[id]; ++i) {
        modifya(root[id], a[i], 1, 0, MAXa);
    }
    if (le[id] != ri[id]) {
        buildb(ls, a, le[id], mid[id]);
        buildb(rs, a, mid[id] + 1, ri[id]);
    }
}
void modifyb(int id, int pb, int pa, int v) {
    modifya(root[id], pa, v, 0, MAXa);
    if (le[id] != ri[id]) {
        if (pb <= mid[id]) modifyb(ls, pb, pa, v);
        else modifyb(rs, pb, pa, v);
    }
}
int queryb(int id, int lb, int rb, int la, int ra) {
    if (le[id] >= lb && ri[id] <= rb) {
        return querya(root[id], la, ra, 0, MAXa);
    } else {
        int ans = 0;
        if (lb <= mid[id]) ans += queryb(ls, lb, rb, la, ra);
        if (rb > mid[id]) ans += queryb(rs, lb, rb, la, ra);
        return ans;
    }
}
#undef ls
#undef rs

Luogu P3380 【模板】二逼平衡树（树套树）

代码：

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
#include<bits/stdc++.h>
using namespace std;
const int MAXn = 5e4;
const int MAXcovn = 30;
const int MAXm = 5e4;
const int MAXa = 1e8;
const int MAXlaya = 28;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;

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...);
}

const int MAXnda = MAXm * MAXcovn * MAXlaya;
int cntnd, ls[MAXnda + 10], rs[MAXnda + 10];
int sum[MAXnda + 10];
inline void pushup(int id) {
    sum[id] = sum[ls[id]] + sum[rs[id]];
}
void modifya(int &id, int p, int v, int le, int ri) {
    if (id == 0) id = ++cntnd;
    if (le == ri) {
        sum[id] += v;
    } else {
        int mid = (le + ri) >> 1;
        if (p <= mid) modifya(ls[id], p, v, le, mid);
        else modifya(rs[id], p, v, mid + 1, ri);
        pushup(id);
    }
}
int querya(int id, int l, int r, int le, int ri) {
    if (id == 0) return 0;
    if (le >= l && ri <= r) {
        return sum[id];
    } else {
        int mid = (le + ri) >> 1, ans = 0;
        if (l <= mid) ans += querya(ls[id], l, r, le, mid);
        if (r > mid) ans += querya(rs[id], l, r, mid + 1, ri);
        return ans;
    }
}

#define ls (id << 1)
#define rs (id << 1 | 1)
const int MAXndb = MAXn * 4;
int le[MAXndb + 10], ri[MAXndb + 10], mid[MAXndb + 10];
int root[MAXndb + 10];
void buildb(int id, int *a, int l, int r) {
    le[id] = l;
    ri[id] = r;
    mid[id] = (l + r) >> 1;
    for (int i = le[id]; i <= ri[id]; ++i) {
        modifya(root[id], a[i], 1, 0, MAXa);
    }
    if (le[id] != ri[id]) {
        buildb(ls, a, le[id], mid[id]);
        buildb(rs, a, mid[id] + 1, ri[id]);
    }
}
void modifyb(int id, int pb, int pa, int v) {
    modifya(root[id], pa, v, 0, MAXa);
    if (le[id] != ri[id]) {
        if (pb <= mid[id]) modifyb(ls, pb, pa, v);
        else modifyb(rs, pb, pa, v);
    }
}
int queryb(int id, int lb, int rb, int la, int ra) {
    if (le[id] >= lb && ri[id] <= rb) {
        return querya(root[id], la, ra, 0, MAXa);
    } else {
        int ans = 0;
        if (lb <= mid[id]) ans += queryb(ls, lb, rb, la, ra);
        if (rb > mid[id]) ans += queryb(rs, lb, rb, la, ra);
        return ans;
    }
}
int cntidx, idx[MAXcovn + 10];
void findidx(int id, int lb, int rb) {
    if (le[id] >= lb && ri[id] <= rb) {
        idx[++cntidx] = root[id];
    } else {
        if (lb <= mid[id]) findidx(ls, lb, rb);
        if (rb > mid[id]) findidx(rs, lb, rb);
    }
}
#undef ls
#undef rs

int Valtorank(int l, int r, int v) {
    if (v == 0) return 1;
    else return 1 + queryb(1, l, r, 0, v - 1);
}
int Ranktoval(int l, int r, int rk) {
    if (rk == 0) return -2147483647;
    cntidx = 0; findidx(1, l, r);
    int sumall = 0;
    for (int i = 1; i <= cntidx; ++i) {
        sumall += sum[idx[i]];
    }
    if (rk > sumall) return 2147483647;
    int lea = 0, ria = MAXa, mida;
    while (lea != ria) {
        mida = (lea + ria) >> 1;
        int sumls = 0;
        for (int i = 1; i <= cntidx; ++i) {
            sumls += sum[ls[idx[i]]];
        }
        if (rk <= sumls) {
            for (int i = 1; i <= cntidx; ++i) {
                idx[i] = ls[idx[i]];
            }
            ria = mida;
        } else {
            rk -= sumls;
            for (int i = 1; i <= cntidx; ++i) {
                idx[i] = rs[idx[i]];
            }
            lea = mida + 1;
        }
    }
    return lea;
}
int Precval(int l, int r, int v) {
    return Ranktoval(l, r, Valtorank(l, r, v) - 1);
}
int Nexval(int l, int r, int v) {
    return Ranktoval(l, r, Valtorank(l, r, v + 1));
}

int n, m;
int a[MAXn + 10];
signed main() {
    read(n, m);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
    }
    buildb(1, a, 1, n);
    for (int i = 1, opt, x, l, r, p; i <= m; ++i) {
        read(opt);
        if (opt == 1) {
            read(l, r, x);
            printf("%d\n", Valtorank(l, r, x));
        } else if (opt == 2) {
            read(l, r, x);
            printf("%d\n", Ranktoval(l, r, x));
        } else if (opt == 3) {
            read(p, x);
            modifyb(1, p, a[p], -1);
            a[p] = x;
            modifyb(1, p, a[p], 1);
        } else if (opt == 4) {
            read(l, r, x);
            printf("%d\n", Precval(l, r, x));
        } else {
            read(l, r, x);
            printf("%d\n", Nexval(l, r, x));
        }
    }
    return 0;
}

线段树套平衡树

Luogu P3380 【模板】二逼平衡树（树套树）

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
#include<bits/stdc++.h>
using namespace std;
const int MAXn = 5e4;
const int MAXm = 5e4;
const int MAXlogn = 16;
const int MAXnd1 = MAXn * 4;
const int MAXnd2 = MAXnd1 * 3 + MAXn * MAXlogn + MAXm * MAXlogn;
const int INF = 0x3f3f3f3f;

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...);
}

int idxinf, idxninf;
int cntnd, son[MAXnd2 + 10][2], fa[MAXnd2 + 10], siz[MAXnd2 + 10], cnt[MAXnd2 + 10], val[MAXnd2 + 10];
inline void pushup(int cur) {
    siz[cur] = cnt[cur] + siz[son[cur][0]] + siz[son[cur][1]];
}
inline int side(int cur) {
    return cur == son[fa[cur]][1];
}
inline void rotate(int cur) {
    int y = fa[cur], z = fa[y], sidecur = side(cur), s = son[cur][sidecur ^ 1];
    if (z) {son[z][side(y)] = cur;} fa[cur] = z;
    son[y][sidecur] = s; if (s) {fa[s] = y;}
    son[cur][sidecur ^ 1] = y; fa[y] = cur;
    pushup(y); pushup(cur);
}
inline void splay(int &root, int cur, int goal = 0) {
    int y, z;
    while (fa[cur] != goal) {
        y = fa[cur], z = fa[y];
        if (z != goal) {
            if (side(cur) == side(y)) rotate(y);
            else rotate(cur);
        }
        rotate(cur);
    }
    if (!goal) root = cur;
}
inline int V2R(int &root, int v) {
    int ans = 0, cur = root;
    while (true) {
        if (val[cur] < v) {
            ans += siz[son[cur][0]] + cnt[cur];
            if (son[cur][1]) cur = son[cur][1];
            else break;
        } else if (val[cur] == v) {
            ans += siz[son[cur][0]];
            break;
        } else {
            if (son[cur][0]) cur = son[cur][0];
            else break;
        }
    }
    splay(root, cur);
    return ans - 1;
}
inline int PI(int &root, int v) {
    int ans = idxninf, cur = root;
    while (true) {
        if (val[cur] >= v) {
            if (son[cur][0]) cur = son[cur][0];
            else break;
        } else {
            ans = val[ans] > val[cur] ? ans : cur;
            if (son[cur][1]) cur = son[cur][1];
            else break;
        }
    }
    splay(root, cur);
    return ans;
}
inline int NI(int &root, int v) {
    int ans = idxinf, cur = root;
    while (true) {
        if (val[cur] <= v) {
            if (son[cur][1]) cur = son[cur][1];
            else break;
        } else {
            ans = val[ans] < val[cur] ? ans : cur;
            if (son[cur][0]) cur = son[cur][0];
            else break;
        }
    }
    splay(root, cur);
    return ans;
}
inline void I(int &root, int v) {
    int cur = root, f = 0;
    while (cur && v != val[cur]) {
        f = cur;
        cur = son[cur][v > val[cur]];
    }
    if (cur) {
        ++cnt[cur];
    } else {
        cur = ++cntnd;
        cnt[cur] = 1;
        val[cur] = v;
        fa[cur] = f;
        if (f) son[f][v > val[f]] = cur;
    }
    splay(root, cur);
}
inline void D(int &root, int v) {
    int pre = PI(root, v), nex = NI(root, v);
    splay(root, pre); splay(root, nex, pre);
    int del = son[nex][0];
    if (del) {
        --cnt[del];
        if (cnt[del]) {
            splay(root, del);
        } else {
            son[nex][0] = 0;
        }
    }
}

#define ls (id << 1)
#define rs (id << 1 | 1)
int le[MAXnd1 + 10], ri[MAXnd1 + 10], root[MAXnd1 + 10];
void BuildUseArr(int id, int l, int r, int *a) {
    le[id] = l; ri[id] = r;
    I(root[id], INF);
    I(root[id], -INF);
    for (int i = l; i <= r; ++i) I(root[id], a[i]);
    if (l == r) {
        ;
    } else {
        int mid = (l + r) >> 1;
        BuildUseArr(ls, l, mid, a);
        BuildUseArr(rs, mid + 1, r, a);
    }
}
void Insert(int id, int p, int a) {
    I(root[id], a);
    if (le[id] == ri[id]) {
        ;
    } else {
        int mid = (le[id] + ri[id]) >> 1;
        if (p <= mid) Insert(ls, p, a);
        else Insert(rs, p, a);
    }
}
void Delete(int id, int p, int a) {
    D(root[id], a);
    if (le[id] == ri[id]) {
        ;
    } else {
        int mid = (le[id] + ri[id]) >> 1;
        if (p <= mid) Delete(ls, p, a);
        else Delete(rs, p, a);
    }
}
int ValtoRank(int id, int l, int r, int v) {
    if (le[id] >= l && ri[id] <= r) {
        return V2R(root[id], v);
    } else {
        int mid = (le[id] + ri[id]) >> 1, ans = 0;
        if (l <= mid) ans += ValtoRank(ls, l, r, v);
        if (r > mid) ans += ValtoRank(rs, l, r, v);
        return ans;
    }
}
int RanktoVal(int l, int r, int rk) {
    --rk;
    int L = -INF + 1, R = INF - 1, M;
    while (L < R) {
        M = (L + R + 1) >> 1;
        if (ValtoRank(1, l, r, M) <= rk) {
            L = M;
        } else {
            R = M - 1;
        }
    }
    return L;
}
int Pre(int id, int l, int r, int v) {
    if (le[id] >= l && ri[id] <= r) {
        return val[PI(root[id], v)];
    } else {
        int mid = (le[id] + ri[id]) >> 1, ans = -INF;
        if (l <= mid) ans = max(ans, Pre(ls, l, r, v));
        if (r > mid) ans = max(ans, Pre(rs, l, r, v));
        return ans;
    }
}
int Nex(int id, int l, int r, int v) {
    if (le[id] >= l && ri[id] <= r) {
        return val[NI(root[id], v)];
    } else {
        int mid = (le[id] + ri[id]) >> 1, ans = INF;
        if (l <= mid) ans = min(ans, Nex(ls, l, r, v));
        if (r > mid) ans = min(ans, Nex(rs, l, r, v));
        return ans;
    }
}
#undef ls
#undef rs

int n, m, a[MAXn + 10];
signed main() {
    val[idxinf = ++cntnd] = INF;
    val[idxninf = ++cntnd] = -INF;
    read(n, m);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
    }
    BuildUseArr(1, 1, n, a);
    for (int i = 1, opt, l, r, p, k, tmp; i <= m; ++i) {
        read(opt);
        if (opt == 1) {
            read(l, r, k);
            printf("%d\n", ValtoRank(1, l, r, k) + 1);
        } else if (opt == 2) {
            read(l, r, k);
            printf("%d\n", RanktoVal(l, r, k));
        } else if (opt == 3) {
            read(p, k);
            Delete(1, p, a[p]);
            a[p] = k;
            Insert(1, p, k);
        } else if (opt == 4)  {
            read(l, r, k);
            tmp = Pre(1, l, r, k);
            if (tmp == -INF) puts("-2147483647");
            else printf("%d\n", tmp);
        } else if (opt == 5) {
            read(l, r, k);
            tmp = Nex(1, l, r, k);
            if (tmp == INF) puts("2147483647");
            else printf("%d\n", tmp);
        }
    }
    return 0;
}