今天我刷题了吗
搜索文档…
无旋树堆
fhq Treap
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(0x3f3f3f3f);
7
const int maxn(1e5 + 10);
8
int idx, root;
9
int x, y, z;
10
11
struct node {
12
int l, r;
13
int key, val;
14
int siz;
15
} tree[maxn];
16
17
template<typename T = int>
18
inline const T read()
19
{
20
T x = 0, f = 1;
21
char ch = getchar();
22
while (ch < '0' || ch > '9') {
23
if (ch == '-') f = -1;
24
ch = getchar();
25
}
26
while (ch >= '0' && ch <= '9') {
27
x = (x << 3) + (x << 1) + ch - '0';
28
ch = getchar();
29
}
30
return x * f;
31
}
32
33
template<typename T>
34
inline void write(T x, bool ln)
35
{
36
if (x < 0) {
37
putchar('-');
38
x = -x;
39
}
40
if (x > 9) write(x / 10, false);
41
putchar(x % 10 + '0');
42
if (ln) putchar(10);
43
}
44
45
inline int new_node(int key)
46
{
47
++idx;
48
tree[idx].key = key;
49
tree[idx].val = rand();
50
tree[idx].siz = 1;
51
return idx;
52
}
53
54
inline void push_up(int cur)
55
{
56
tree[cur].siz = tree[tree[cur].l].siz + tree[tree[cur].r].siz + 1;
57
}
58
59
inline void split(int cur, int key, int& x, int& y)
60
{
61
if (not cur) {
62
x = y = 0;
63
} else if (tree[cur].key <= key) {
64
x = cur;
65
split(tree[cur].r, key, tree[cur].r, y);
66
push_up(cur);
67
} else {
68
y = cur;
69
split(tree[cur].l, key, x, tree[cur].l);
70
push_up(cur);
71
}
72
}
73
74
inline int merge(int x, int y)
75
{
76
if (not x or not y) {
77
return x + y;
78
}
79
if (tree[x].val > tree[y].val) {
80
tree[x].r = merge(tree[x].r, y);
81
push_up(x);
82
return x;
83
}
84
tree[y].l = merge(x, tree[y].l);
85
push_up(y);
86
return y;
87
}
88
89
inline void insert(int key)
90
{
91
split(root, key, x, y);
92
root = merge(merge(x, new_node(key)), y);
93
}
94
95
inline void remove(int key)
96
{
97
split(root, key, x, z);
98
split(x, key - 1, x, y);
99
y = merge(tree[y].l, tree[y].r);
100
root = merge(merge(x, y), z);
101
}
102
103
inline int get_rank(int key)
104
{
105
split(root, key - 1, x, y);
106
int res = tree[x].siz + 1;
107
root = merge(x, y);
108
return res;
109
}
110
111
inline int get_key(int cur, int rank)
112
{
113
if (rank == tree[tree[cur].l].siz + 1) {
114
return tree[cur].key;
115
}
116
if (rank <= tree[tree[cur].l].siz) {
117
return get_key(tree[cur].l, rank);
118
}
119
return get_key(tree[cur].r, rank - tree[tree[cur].l].siz - 1);
120
}
121
122
inline int get_prev(int key)
123
{
124
split(root, key - 1, x, y);
125
int cur = x;
126
while (tree[cur].r) {
127
cur = tree[cur].r;
128
}
129
int res = tree[cur].key;
130
root = merge(x, y);
131
return res;
132
}
133
134
inline int get_next(int key)
135
{
136
split(root, key, x, y);
137
int cur = y;
138
while (tree[cur].l) {
139
cur = tree[cur].l;
140
}
141
int res = tree[cur].key;
142
root = merge(x, y);
143
return res;
144
}
145
146
int main()
147
{
148
#ifdef ONLINE_JUDGE
149
#else
150
freopen("input.txt", "r", stdin);
151
#endif
152
int n = read();
153
while (n--) {
154
int op = read(), x = read();
155
if (op == 1) {
156
insert(x);
157
} else if (op == 2) {
158
remove(x);
159
} else if (op == 3) {
160
write(get_rank(x), true);
161
} else if (op == 4) {
162
write(get_key(root, x), true);
163
} else if (op == 5) {
164
write(get_prev(x), true);
165
} else {
166
write(get_next(x), true);
167
}
168
}
169
return 0;
170
}
Copied!
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const double pi(acos(-1));
7
const int inf(0x3f3f3f3f);
8
const int maxn(1e5 + 10);
9
int idx, root;
10
11
struct node {
12
int l, r;
13
int key, val;
14
int siz;
15
bool rev;
16
} tree[maxn];
17
18
template<typename T = int>
19
inline const T read()
20
{
21
T x = 0, f = 1;
22
char ch = getchar();
23
while (ch < '0' || ch > '9') {
24
if (ch == '-') f = -1;
25
ch = getchar();
26
}
27
while (ch >= '0' && ch <= '9') {
28
x = (x << 3) + (x << 1) + ch - '0';
29
ch = getchar();
30
}
31
return x * f;
32
}
33
34
template<typename T>
35
inline void write(T x, char c)
36
{
37
if (x < 0) {
38
putchar('-');
39
x = -x;
40
}
41
if (x > 9) write(x / 10, false);
42
putchar(x % 10 + '0');
43
if (c) putchar(c);
44
}
45
46
inline int new_node(int key)
47
{
48
++idx;
49
tree[idx].key = key;
50
tree[idx].val = rand();
51
tree[idx].siz = 1;
52
return idx;
53
}
54
55
inline void push_up(int cur)
56
{
57
tree[cur].siz = tree[tree[cur].l].siz + tree[tree[cur].r].siz + 1;
58
}
59
60
inline void push_down(int cur)
61
{
62
if (tree[cur].rev) {
63
swap(tree[cur].l, tree[cur].r);
64
tree[tree[cur].l].rev ^= 1;
65
tree[tree[cur].r].rev ^= 1;
66
tree[cur].rev = false;
67
}
68
}
69
70
inline void split(int cur, int siz, int& x, int& y)
71
{
72
if (not cur) {
73
x = y = 0;
74
} else {
75
push_down(cur);
76
if (siz > tree[tree[cur].l].siz) {
77
x = cur;
78
split(tree[cur].r, siz - tree[tree[cur].l].siz - 1, tree[cur].r, y);
79
} else {
80
y = cur;
81
split(tree[cur].l, siz, x, tree[cur].l);
82
}
83
push_up(cur);
84
}
85
}
86
87
inline int merge(int x, int y)
88
{
89
if (not x or not y) {
90
return x + y;
91
}
92
if (tree[x].val < tree[y].val) {
93
push_down(x);
94
tree[x].r = merge(tree[x].r, y);
95
push_up(x);
96
return x;
97
}
98
push_down(y);
99
tree[y].l = merge(x, tree[y].l);
100
push_up(y);
101
return y;
102
}
103
104
inline void reverse(int l, int r)
105
{
106
int x, y, z;
107
split(root, l - 1, x, y);
108
split(y, r - l + 1, y, z);
109
tree[y].rev ^= 1;
110
root = merge(merge(x, y), z);
111
}
112
113
void dfs(int cur)
114
{
115
if (not cur) return;
116
push_down(cur);
117
dfs(tree[cur].l);
118
write(tree[cur].key, ' ');
119
dfs(tree[cur].r);
120
}
121
122
int main()
123
{
124
#ifdef ONLINE_JUDGE
125
#else
126
freopen("input.txt", "r", stdin);
127
#endif
128
int n = read(), m = read();
129
for (int i = 1; i <= n; ++i) {
130
root = merge(root, new_node(i));
131
}
132
while (m--) {
133
int l = read(), r = read();
134
reverse(l, r);
135
}
136
dfs(root);
137
return 0;
138
}
Copied!
最近更新 1yr ago
复制链接