今天我刷题了吗
搜索文档…
树套树
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const int inf(INT_MAX);
7
const int maxn(2e5 + 10);
8
const int maxm(1e7 + 10);
9
int idx, w[maxn];
10
11
struct splayNode {
12
int val;
13
int cnt, siz;
14
int fa, ch[2];
15
} splay[maxm];
16
17
struct segNode {
18
int l, r, root;
19
} segTree[maxn];
20
21
template<typename T = int>
22
inline const T read()
23
{
24
T x = 0, f = 1;
25
char ch = getchar();
26
while (ch < '0' or ch > '9') {
27
if (ch == '-') f = -1;
28
ch = getchar();
29
}
30
while (ch >= '0' and ch <= '9') {
31
x = (x << 3) + (x << 1) + ch - '0';
32
ch = getchar();
33
}
34
return x * f;
35
}
36
37
template<typename T>
38
inline void write(T x, bool ln)
39
{
40
if (x < 0) {
41
putchar('-');
42
x = -x;
43
}
44
if (x > 9) write(x / 10, false);
45
putchar(x % 10 + '0');
46
if (ln) putchar(10);
47
}
48
49
inline int new_node(int val)
50
{
51
++idx;
52
splay[idx].val = val;
53
splay[idx].cnt = splay[idx].siz = 1;
54
return idx;
55
}
56
57
inline bool get_rel(int cur, int fa)
58
{
59
return splay[fa].ch[1] == cur;
60
}
61
62
inline void connect(int cur, int fa, bool rel)
63
{
64
splay[fa].ch[rel] = cur;
65
splay[cur].fa = fa;
66
}
67
68
inline void push_up(int cur)
69
{
70
splay[cur].siz = splay[splay[cur].ch[0]].siz + splay[splay[cur].ch[1]].siz + splay[cur].cnt;
71
}
72
73
inline void rotate(int cur)
74
{
75
int fa = splay[cur].fa;
76
int gf = splay[fa].fa;
77
bool rel = get_rel(cur, fa);
78
connect(splay[cur].ch[rel xor 1], fa, rel);
79
connect(cur, gf, get_rel(fa, gf));
80
connect(fa, cur, rel xor 1);
81
push_up(fa);
82
push_up(cur);
83
}
84
85
inline void splaying(int cur, int top, int& rt)
86
{
87
while (splay[cur].fa not_eq top) {
88
int fa = splay[cur].fa;
89
int gf = splay[fa].fa;
90
if (gf not_eq top) {
91
get_rel(cur, fa) xor get_rel(fa, gf) ? rotate(cur) : rotate(fa);
92
}
93
rotate(cur);
94
}
95
if (not top) rt = cur;
96
}
97
98
inline void insert(int val, int& rt)
99
{
100
int cur = rt, fa = 0;
101
while (cur and splay[cur].val not_eq val) {
102
fa = cur;
103
cur = splay[cur].ch[val > splay[cur].val];
104
}
105
if (cur) {
106
++splay[cur].cnt;
107
++splay[cur].siz;
108
} else {
109
cur = new_node(val);
110
connect(cur, fa, val > splay[fa].val);
111
}
112
splaying(cur, 0, rt);
113
}
114
115
inline void remove(int val, int& rt)
116
{
117
int cur = rt;
118
while (cur and splay[cur].val not_eq val) {
119
cur = splay[cur].ch[val > splay[cur].val];
120
}
121
splaying(cur, 0, rt);
122
if (splay[cur].cnt > 1) {
123
--splay[cur].cnt;
124
--splay[cur].siz;
125
} else if (splay[cur].ch[1]) {
126
int nxt = splay[cur].ch[1];
127
while (splay[nxt].ch[0]) {
128
nxt = splay[nxt].ch[0];
129
}
130
splaying(nxt, cur, rt);
131
connect(splay[cur].ch[0], nxt, false);
132
rt = nxt;
133
splay[rt].fa = splay[cur].ch[1] = 0;
134
push_up(rt);
135
} else {
136
rt = splay[cur].ch[0];
137
splay[rt].fa = splay[cur].ch[0] = 0;
138
push_up(rt);
139
}
140
}
141
142
inline int get_rank(int val, int& rt)
143
{
144
int cur = rt, rank = 0;
145
while (cur) {
146
if (val < splay[cur].val) {
147
cur = splay[cur].ch[0];
148
} else if (val > splay[cur].val) {
149
rank += splay[splay[cur].ch[0]].siz + splay[cur].cnt;
150
cur = splay[cur].ch[1];
151
} else {
152
rank += splay[splay[cur].ch[0]].siz;
153
splaying(cur, 0, rt);
154
break;
155
}
156
}
157
return rank;
158
}
159
160
inline int get_val(int rank, int& rt)
161
{
162
int cur = rt;
163
while (cur) {
164
if (splay[splay[cur].ch[0]].siz >= rank) {
165
cur = splay[cur].ch[0];
166
} else if (splay[splay[cur].ch[0]].siz + splay[cur].cnt >= rank) {
167
splaying(cur, 0, rt);
168
break;
169
} else {
170
rank -= splay[splay[cur].ch[0]].siz + splay[cur].cnt;
171
cur = splay[cur].ch[1];
172
}
173
}
174
return splay[cur].val;
175
}
176
177
inline int get_prev(int val, int& rt)
178
{
179
return get_val(get_rank(val, rt), rt);
180
}
181
182
inline int get_next(int val, int& rt)
183
{
184
return get_val(get_rank(val + 1, rt) + 1, rt);
185
}
186
187
inline int ls(int cur)
188
{
189
return cur << 1;
190
}
191
192
inline int rs(int cur)
193
{
194
return cur << 1 bitor 1;
195
}
196
197
void build(int cur, int l, int r)
198
{
199
segTree[cur].l = l;
200
segTree[cur].r = r;
201
segTree[cur].root = new_node(-inf);
202
insert(inf, segTree[cur].root);
203
for (int i = l; i <= r; ++i) {
204
insert(w[i], segTree[cur].root);
205
}
206
if (l == r) return;
207
int mid = (l + r) >> 1;
208
build(ls(cur), l, mid);
209
build(rs(cur), mid + 1, r);
210
}
211
212
inline int query_rank(int cur, int l, int r, int v)
213
{
214
if (segTree[cur].l == l and segTree[cur].r == r) {
215
return get_rank(v, segTree[cur].root) - 1;
216
}
217
int mid = (segTree[cur].l + segTree[cur].r) >> 1;
218
if (r <= mid) {
219
return query_rank(ls(cur), l, r, v);
220
}
221
if (l > mid) {
222
return query_rank(rs(cur), l, r, v);
223
}
224
return query_rank(ls(cur), l, mid, v) + query_rank(rs(cur), mid + 1, r, v);
225
}
226
227
inline int query_val(int l, int r, int k)
228
{
229
int low = 0, high = 1e8;
230
while (low < high) {
231
int mid = (low + high + 1) >> 1;
232
if (query_rank(1, l, r, mid) + 1 <= k) {
233
low = mid;
234
} else {
235
high = mid - 1;
236
}
237
}
238
return high;
239
}
240
241
inline void update(int cur, int p, int v)
242
{
243
remove(w[p], segTree[cur].root);
244
insert(v, segTree[cur].root);
245
if (segTree[cur].l == segTree[cur].r) return;
246
int mid = (segTree[cur].l + segTree[cur].r) >> 1;
247
if (p <= mid) {
248
update(ls(cur), p, v);
249
} else {
250
update(rs(cur), p, v);
251
}
252
}
253
254
inline int query_prev(int cur, int l, int r, int v)
255
{
256
if (segTree[cur].l == l and segTree[cur].r == r) {
257
return get_prev(v, segTree[cur].root);
258
}
259
int mid = (segTree[cur].l + segTree[cur].r) >> 1;
260
if (r <= mid) {
261
return query_prev(ls(cur), l, r, v);
262
}
263
if (l > mid) {
264
return query_prev(rs(cur), l, r, v);
265
}
266
return max(query_prev(ls(cur), l, mid, v), query_prev(rs(cur), mid + 1, r, v));
267
}
268
269
inline int query_next(int cur, int l, int r, int v)
270
{
271
if (segTree[cur].l == l and segTree[cur].r == r) {
272
return get_next(v, segTree[cur].root);
273
}
274
int mid = (segTree[cur].l + segTree[cur].r) >> 1;
275
if (r <= mid) {
276
return query_next(ls(cur), l, r, v);
277
}
278
if (l > mid) {
279
return query_next(rs(cur), l, r, v);
280
}
281
return min(query_next(ls(cur), l, mid, v), query_next(rs(cur), mid + 1, r, v));
282
}
283
284
int main()
285
{
286
#ifdef ONLINE_JUDGE
287
#else
288
freopen("input.txt", "r", stdin);
289
#endif
290
int n = read(), m = read();
291
for (int i = 1; i <= n; ++i) {
292
w[i] = read();
293
}
294
build(1, 1, n);
295
while (m--) {
296
int op = read();
297
if (op == 1) {
298
int l = read(), r = read(), k = read();
299
write(query_rank(1, l, r, k) + 1, true);
300
} else if (op == 2) {
301
int l = read(), r = read(), k = read();
302
write(query_val(l, r, k), true);
303
} else if (op == 3) {
304
int p = read(), k = read();
305
update(1, p, k);
306
w[p] = k;
307
} else if (op == 4) {
308
int l = read(), r = read(), k = read();
309
write(query_prev(1, l, r, k), true);
310
} else {
311
int l = read(), r = read(), k = read();
312
write(query_next(1, l, r, k), true);
313
}
314
}
315
return 0;
316
}
Copied!
最近更新 1yr ago
复制链接