【模板】普通平衡树

题目描述

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

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

输入格式

第一行为 $n$，表示操作的个数,下面 $n$ 行每行有两个数 $\text{opt}$ 和 $x$，$\text{opt}$ 表示操作的序号( $ 1 \leq \text{opt} \leq 6 $ )

输出格式

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

样例 #1

样例输入 #1

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
1
2
3
4
5
6
7
8
9
10
11

样例输出 #1

106465
84185
492737
1
2
3

提示

【数据范围】
对于 $100\%$ 的数据，$1\le n\le 10^5$，$|x|\le 10^7$

来源：Tyvj1728 原名：普通平衡树

在此鸣谢

#include
#define LL long long
#define PP pair <int, int>
using namespace std;
const int N = 1e5 + 10;
struct Treap {
	int l, r, val, pri, num, size;//左右子节点，值，优先级，重复个数，跟的子树大小 
} tree[N];
int T, cnt;
int root;
inline int read () {
	int s = 0, f = 1;
	char ch = getchar ();
	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = -1;
		ch = getchar ();
	}
	while (ch >= '0' && ch <= '9') {
		s = (s << 1) + (s << 3) + (ch ^ '0');
		ch = getchar ();
	}
	return s * f;
}
void write (int x) {
    if (x < 0) {
    	putchar ('-');
		x = -x;
	}
    if (x > 9) 
		write (x / 10);
    putchar (x % 10 + '0');
}
inline int New (int val) {//生成新节点 
	tree[ ++ cnt].val = val;//点权 
	tree[cnt].pri = rand ();//给一个随机数作为优先级 
	tree[cnt].num = tree[cnt].size = 1;//子树大小和重复个数均为1 
	tree[cnt].l = tree[cnt].r = 0;//没有左右节点 
	return cnt;
}
inline void Update (int p) {//更新子树大小
	tree[p].size = tree[tree[p].l].size + tree[tree[p].r].size + tree[p].num;//当前子树的大小为左子树的大小加右子树大小叫重复的个数 
}
inline void zig (int &p) {//右旋 
	int q = tree[p].l;
	tree[p].l = tree[q].r;
	tree[q].r = p;
	tree[q].size = tree[p].size;
	Update (p);
	p = q;
}
inline void zag (int &p) {//左旋 
	int q = tree[p].r;
	tree[p].r = tree[q].l;
	tree[q].l = p;
	tree[q].size = tree[p].size;
	Update (p);
	p = q;
}
void Insert (int &p, int val) {//在p的子树中插入val 
	if (!p) {//如果没有，则新建一个 
		p = New (val);
		return;
	}
	tree[p].size ++ ;
	if (val == tree[p].val) {
		tree[p].num ++ ;
		return;	
	}
	if (val < tree[p].val) {
		Insert (tree[p].l, val);
		if (tree[p].pri < tree[tree[p].l].pri) zig (p);
	}
	if (val > tree[p].val) {
		Insert (tree[p].r, val);
		if (tree[p].pri < tree[tree[p].r].pri) zag (p);
	}
}
void Delete (int &p, int val) {//在p的子树中删除val
	if (!p) return;
	tree[p].size -- ;
	if (val == tree[p].val) {
		if (tree[p].num > 1) {
			tree[p].num -- ;
			return;
		}
		if (!tree[p].l || !tree[p].r) 
			p = tree[p].l + tree[p].r;
		else if (tree[tree[p].l].pri > tree[tree[p].r].pri) {
			zig (p);
			Delete (tree[p].r, val);
		}
		else {
			zag (p);
			Delete (tree[p].l, val);
		}
		return;
	} 
	if (val < tree[p].val) Delete (tree[p].l, val);
	if (val > tree[p].val) Delete (tree[p].r, val);
}
inline int Getpre (int val) {//找前驱
	int p = root;
	int res = 0;
	while (p) {
		if (tree[p].val < val) {
			res = tree[p].val;
			p = tree[p].r;
		}
		else p = tree[p].l;
	} 
	return res;
}
inline int Getnext (int val) {//找后继
	int p = root;
	int res = 0;
	while (p) {
		if (tree[p].val > val) {
			res = tree[p].val;
			p = tree[p].l;
		}
		else p = tree[p].r;
	} 
	return res;
}
int getRanking (int p, int val) {//根据val查找排名
	if (!p) return 0;
	if (tree[p].val == val) return tree[tree[p].l].size + 1;
	if (val < tree[p].val) return getRanking (tree[p].l, val);
	if (val > tree[p].val) return getRanking (tree[p].r, val) + tree[tree[p].l].size + tree[p].num;
}
int UseRankingfindval (int p, int rank) {//根据排名rank查找val
	if (!p) return 0;
	if (tree[tree[p].l].size >= rank) return UseRankingfindval (tree[p].l, rank);
	if (tree[tree[p].l].size + tree[p].num >= rank) return tree[p].val;
	return UseRankingfindval (tree[p].r, rank - tree[tree[p].l].size - tree[p].num);
}
int main () {
	T = read ();
	register int op, x;
	while (T -- ) {
		op = read (), x = read ();
		if (op == 1) Insert (root, x);
		if (op == 2) Delete (root, x);
		if (op == 3) write (getRanking (root, x)), puts ("");
		if (op == 4) write (UseRankingfindval (root, x)), puts ("");
		if (op == 5) write (Getpre (x)), puts ("");
		if (op == 6) write (Getnext (x)), puts ("");
	}
	return 0;
}
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