【bzoj3224】普通平衡树

描述 Description

您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作

  1. 插入x数
  2. 删除x数(若有多个相同的数,因只删除一个)
  3. 查询x数的排名(若有多个相同的数,因输出最小的排名)
  4. 查询排名为x的数
  5. 求x的前驱(前驱定义为小于x,且最大的数)
  6. 求x的后继(后继定义为大于x,且最小的数)

输入格式 Input Format

第一行为n,表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号(1<=opt<=6)

输出格式 Output Format

对于操作3,4,5,6每行输出一个数,表示对应答案

样例输入 Sample Input

8
1 10
1 20
1 30
3 20
4 2
2 10
5 25
6 -1

样例输出 Sample Output

2

20

20

20

注释 Hint

n<=100000 所有数字均在-10^7到10^7内

Code

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
#include<bits/stdc++.h>
#define ll long long
#define reg register int
#define cl(x) memset(x, 0, sizeof(x))
#define lc(x) tree[x].son[0]
#define rc(x) tree[x].son[1]
#define father(x) tree[x].fa

struct splay{
int v;
int siz, wit;
int fa, son[2];
}tree[100010];
int n;
int root = 0;
int len = 0;

void dfs(int pos) {
if (pos) {
printf("%d %d\n", pos, tree[pos].v);
dfs(lc(pos));
dfs(rc(pos));
}
}

int read() {
int k = 0, f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
k = k * 10 + ch - '0';
ch = getchar();
}
return k * f;
}

inline bool relation(int pos) {
return pos == rc(tree[pos].fa);
}

inline void maintain(int pos) {
tree[pos].siz = tree[lc(pos)].siz + tree[rc(pos)].siz + tree[pos].wit;
}

inline void ins(int x, int y, int z) {
tree[x].son[z] = y;
tree[y].fa = x;
}

inline void rotate(int pos) {
int f = father(pos);
bool flag = relation(pos);
ins(father(f), pos, relation(f));
ins(f, tree[pos].son[flag^1], flag);
ins(pos, f, flag^1);
maintain(f);
maintain(pos);
if (!father(pos)) root = pos;
}

void splay(int pos, int tar = 0) {
while (tree[pos].fa != tar) {
if (tree[father(pos)].fa != tar) {
if (relation(pos) == relation(father(pos))) rotate(father(pos));
else rotate(pos);
}
rotate(pos);
}
}

int pre(int v) {
int pos = root, ans = 0;
while (pos) {
if (tree[pos].v >= v) pos = lc(pos);
else {
ans = pos;
pos = rc(pos);
}
}
splay(ans);
return root;
}

int succ(int v) {
int ans = 0, pos = root;
while (pos) {
if (tree[pos].v <= v) pos = rc(pos);
else {
ans = pos;
pos = lc(pos);
}
}
splay(ans);
return root;
}

int find(int v) {
int pos = root;
while (pos && tree[pos].v != v) {
if (v < tree[pos].v) pos = lc(pos);
else pos = rc(pos);
}
if (pos) {
splay(pos);
//return root;
}
return root;
}

void del(int v) {
int pos = find(v);
if (tree[pos].wit > 1) {
--tree[pos].siz;
--tree[pos].wit;
return;
}
int y = succ(v);
int x = pre(v);
splay(y, x);
//lc(y) = 0;
tree[y].son[0] = 0;
--tree[y].siz;
--tree[x].siz;
//dfs(root);
}

int insert(int v) {
int pos = root, lt = 0;
while (pos && tree[pos].v != v) {
++tree[pos].siz;
lt = pos;
if (v < tree[pos].v) pos = lc(pos);
else pos = rc(pos);
}
if (pos) {
++tree[pos].siz;
++tree[pos].wit;
}
else {
pos = ++len;
tree[pos].v = v;
tree[pos].siz = tree[pos].wit = 1;
lc(pos) = rc(pos) = 0;
father(pos) = lt;
tree[lt].son[v > tree[lt].v] = pos;
}
splay(pos);
return root;
}

int rank(int v) {
int pos = find(v);
if (!pos) {
pos = insert(v);
int ans = tree[lc(pos)].siz;
del(v);
return ans;
}
return tree[lc(pos)].siz;
}

int kth(int k) {
int pos = root;
int sz = tree[lc(pos)].siz;
while (k < sz || k >= sz + tree[pos].wit) {
if (k < sz) pos = lc(pos);
else {
k -= sz + tree[pos].wit;
pos = rc(pos);
}
sz = tree[lc(pos)].siz;
}
splay(pos);
return tree[pos].v;
}

void put(int x) {
if (!x) {putchar('0'); putchar('\n');}
if (x < 0) {putchar('-'); x = -x;}
char ch[15];
int top = 0;
while (x) {ch[++top] = x % 10 + '0'; x /= 10;}
while (top) putchar(ch[top--]);
putchar('\n');
}

int main() {
n = read();
insert(0x7fffffff);
root = 1;
insert(0x80000000);
for (reg i = 1; i <= n; ++i) {
//dfs(root);
int o = read(), v = read();
if (o == 1) insert(v);
else if (o == 2) del(v);
else if (o == 3) put(rank(v));
else if (o == 4) put(kth(v));
else if (o == 5) put(tree[pre(v)].v);
else if (o == 6) put(tree[succ(v)].v);
}
return 0;
}