今天我刷题了吗
搜索文档…
伸展树
Splay
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const int maxn(1e5 + 10);
7
int idx, root;
8
9
struct node {
10
int val;
11
int siz, cnt;
12
int fa, ch[2];
13
} tree[maxn];
14
15
template<typename T = int>
16
inline const T read()
17
{
18
T x = 0, f = 1;
19
char ch = getchar();
20
while (ch < '0' || ch > '9') {
21
if (ch == '-') f = -1;
22
ch = getchar();
23
}
24
while (ch >= '0' && ch <= '9') {
25
x = (x << 3) + (x << 1) + ch - '0';
26
ch = getchar();
27
}
28
return x * f;
29
}
30
31
template<typename T>
32
inline void write(T x, bool ln)
33
{
34
if (x < 0) {
35
putchar('-');
36
x = -x;
37
}
38
if (x > 9) write(x / 10, false);
39
putchar(x % 10 + '0');
40
if (ln) putchar(10);
41
}
42
43
inline int new_node(int val)
44
{
45
++idx;
46
tree[idx].val = val;
47
tree[idx].siz = tree[idx].cnt = 1;
48
return idx;
49
}
50
51
inline bool get_rel(int cur, int fa)
52
{
53
return tree[fa].ch[1] == cur;
54
}
55
56
inline void connect(int cur, int fa, int rel)
57
{
58
tree[fa].ch[rel] = cur;
59
tree[cur].fa = fa;
60
}
61
62
inline void push_up(int cur)
63
{
64
tree[cur].siz = tree[tree[cur].ch[0]].siz + tree[tree[cur].ch[1]].siz + tree[cur].cnt;
65
}
66
67
inline void rotate(int cur)
68
{
69
int fa = tree[cur].fa;
70
int gf = tree[fa].fa;
71
bool rel = get_rel(cur, fa);
72
connect(tree[cur].ch[rel ^ 1], fa, rel);
73
connect(cur, gf, get_rel(fa, gf));
74
connect(fa, cur, rel ^ 1);
75
push_up(fa);
76
push_up(cur);
77
}
78
79
inline void splaying(int cur, int top)
80
{
81
while (tree[cur].fa not_eq top) {
82
int fa = tree[cur].fa;
83
int gf = tree[fa].fa;
84
if (gf not_eq top) {
85
get_rel(cur, fa) ^ get_rel(fa, gf) ? rotate(cur) : rotate(fa);
86
}
87
rotate(cur);
88
}
89
if (not top) {
90
root = cur;
91
}
92
}
93
94
inline void insert(int val)
95
{
96
int cur = root, fa = 0;
97
while (cur and tree[cur].val not_eq val) {
98
fa = cur;
99
cur = tree[cur].ch[val > tree[cur].val];
100
}
101
if (cur) {
102
++tree[cur].cnt;
103
++tree[cur].siz;
104
} else {
105
cur = new_node(val);
106
connect(cur, fa, val > tree[fa].val);
107
}
108
splaying(cur, 0);
109
}
110
111
inline void remove(int val)
112
{
113
int cur = root, fa = 0;
114
while (tree[cur].val not_eq val) {
115
fa = cur;
116
cur = tree[cur].ch[val > tree[cur].val];
117
}
118
splaying(cur, 0);
119
if (tree[cur].cnt > 1) {
120
--tree[cur].cnt;
121
--tree[cur].siz;
122
} else if (tree[cur].ch[1]) {
123
int nxt = tree[cur].ch[1];
124
while (tree[nxt].ch[0]) {
125
nxt = tree[nxt].ch[0];
126
}
127
splaying(nxt, cur);
128
connect(tree[cur].ch[0], nxt, 0);
129
root = nxt;
130
tree[root].fa = 0;
131
push_up(root);
132
} else {
133
root = tree[cur].ch[0];
134
tree[root].fa = 0;
135
}
136
}
137
138
inline int get_rank(int val)
139
{
140
int cur = root, rank = 1;
141
while (cur) {
142
if (tree[cur].val == val) {
143
rank += tree[tree[cur].ch[0]].siz;
144
splaying(cur, 0);
145
break;
146
} else if (val < tree[cur].val) {
147
cur = tree[cur].ch[0];
148
} else {
149
rank += tree[tree[cur].ch[0]].siz + tree[cur].cnt;
150
cur = tree[cur].ch[1];
151
}
152
}
153
return rank;
154
}
155
156
inline int get_val(int rank)
157
{
158
int cur = root;
159
while (cur) {
160
int size_l = tree[tree[cur].ch[0]].siz;
161
if (size_l + 1 <= rank and rank <= size_l + tree[cur].cnt) {
162
splaying(cur, 0);
163
break;
164
} else if (size_l >= rank) {
165
cur = tree[cur].ch[0];
166
} else {
167
rank -= size_l + tree[cur].cnt;
168
cur = tree[cur].ch[1];
169
}
170
}
171
return tree[cur].val;
172
}
173
174
inline int get_prev(int val)
175
{
176
return get_val(get_rank(val) - 1);
177
}
178
179
inline int get_next(int val)
180
{
181
return get_val(get_rank(val + 1));
182
}
183
184
int main()
185
{
186
#ifdef ONLINE_JUDGE
187
#else
188
freopen("input.txt", "r", stdin);
189
#endif
190
int n = read();
191
while (n--) {
192
int op = read(), x = read();
193
if (op == 1) {
194
insert(x);
195
} else if (op == 2) {
196
remove(x);
197
} else if (op == 3) {
198
write(get_rank(x), true);
199
} else if (op == 4) {
200
write(get_val(x), true);
201
} else if (op == 5) {
202
write(get_prev(x), true);
203
} else {
204
write(get_next(x), true);
205
}
206
}
207
return 0;
208
}
Copied!
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const int maxn(1e5 + 10);
7
int idx, root;
8
9
struct node {
10
int val, siz;
11
int fa, ch[2];
12
bool rev;
13
} tree[maxn];
14
15
template<typename T = int>
16
inline const T read()
17
{
18
T x = 0, f = 1;
19
char ch = getchar();
20
while (ch < '0' || ch > '9') {
21
if (ch == '-') f = -1;
22
ch = getchar();
23
}
24
while (ch >= '0' && ch <= '9') {
25
x = (x << 3) + (x << 1) + ch - '0';
26
ch = getchar();
27
}
28
return x * f;
29
}
30
31
template<typename T>
32
inline void write(T x, char c)
33
{
34
if (x < 0) {
35
putchar('-');
36
x = -x;
37
}
38
if (x > 9) write(x / 10, false);
39
putchar(x % 10 + '0');
40
if (c) putchar(c);
41
}
42
43
inline int new_node(int val)
44
{
45
++idx;
46
tree[idx].val = val;
47
tree[idx].siz = 1;
48
return idx;
49
}
50
51
inline void push_up(int cur)
52
{
53
tree[cur].siz = tree[tree[cur].ch[0]].siz + tree[tree[cur].ch[1]].siz + 1;
54
}
55
56
inline void push_down(int cur)
57
{
58
if (tree[cur].rev) {
59
swap(tree[cur].ch[0], tree[cur].ch[1]);
60
tree[tree[cur].ch[0]].rev ^= 1;
61
tree[tree[cur].ch[1]].rev ^= 1;
62
tree[cur].rev = false;
63
}
64
}
65
66
inline int get_rel(int cur, int fa)
67
{
68
return tree[fa].ch[1] == cur;
69
}
70
71
inline void connect(int cur, int fa, bool rel)
72
{
73
tree[fa].ch[rel] = cur;
74
tree[cur].fa = fa;
75
}
76
77
inline void rotate(int cur)
78
{
79
int fa = tree[cur].fa;
80
int gf = tree[fa].fa;
81
bool rel = get_rel(cur, fa);
82
connect(tree[cur].ch[rel ^ 1], fa, rel);
83
connect(cur, gf, get_rel(fa, gf));
84
connect(fa, cur, rel ^ 1);
85
push_up(fa);
86
push_up(cur);
87
}
88
89
inline void splaying(int cur, int top)
90
{
91
while (tree[cur].fa not_eq top) {
92
int fa = tree[cur].fa;
93
int gf = tree[fa].fa;
94
if (gf not_eq top) {
95
get_rel(cur, fa) ^ get_rel(fa, gf) ? rotate(cur) : rotate(fa);
96
}
97
rotate(cur);
98
}
99
if (not top) {
100
root = cur;
101
}
102
}
103
104
inline void insert(int val)
105
{
106
int cur = root, fa = 0;
107
while (cur) {
108
fa = cur;
109
cur = tree[cur].ch[val > tree[cur].val];
110
}
111
cur = new_node(val);
112
connect(cur, fa, val > tree[fa].val);
113
splaying(cur, 0);
114
}
115
116
inline int get_id(int pos)
117
{
118
int cur = root;
119
while (cur) {
120
push_down(cur);
121
if (tree[tree[cur].ch[0]].siz >= pos) {
122
cur = tree[cur].ch[0];
123
} else if (tree[tree[cur].ch[0]].siz + 1 == pos) {
124
return cur;
125
} else {
126
pos -= tree[tree[cur].ch[0]].siz + 1;
127
cur = tree[cur].ch[1];
128
}
129
}
130
return cur;
131
}
132
133
inline void reverse(int l, int r)
134
{
135
int x = get_id(l - 1);
136
int y = get_id(r + 1);
137
splaying(x, 0);
138
splaying(y, x);
139
tree[tree[y].ch[0]].rev ^= 1;
140
}
141
142
void dfs(int cur, int n)
143
{
144
if (not cur) return;
145
push_down(cur);
146
dfs(tree[cur].ch[0], n);
147
if (tree[cur].val >= 1 and tree[cur].val <= n) {
148
write(tree[cur].val, ' ');
149
}
150
dfs(tree[cur].ch[1], n);
151
}
152
153
int main()
154
{
155
#ifdef ONLINE_JUDGE
156
#else
157
freopen("input.txt", "r", stdin);
158
#endif
159
int n = read(), m = read();
160
for (int i = 0; i <= n + 1; ++i) {
161
insert(i);
162
}
163
while (m--) {
164
int l = read() + 1, r = read() + 1;
165
reverse(l, r);
166
}
167
dfs(root, n);
168
return 0;
169
}
Copied!
最近更新 1yr ago
复制链接