[模板]treap


treap模板

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
#include<bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;
const int maxn = 1e7 + 10;
int n,tot,root;
struct treap
{
int l,r,val,dat;//左子树编号,右子树编号,节点关键码,权值;
int size,cnt;//子树大小,副本个数(均包括自己);
}a[maxn];
//增加新节点
int New(int val)
{
a[++tot].val = val;
a[tot].dat = rand();//随机分配一个权值
a[tot].cnt = a[tot].size = 1;//副本和子树大小为1;
return tot;//返回当前节点的编号;
}
//重新计算子树大小;
void Update(int p){
a[p].size = a[a[p].l].size + a[a[p].r].size + a[p].cnt;
//子树大小等于左右子树大小加副本数;
}
//建树:
void build()
{
New(-INF),New(INF);//插入正无穷和负无穷
root = 1,a[1].r = 2;//根据BST的基础定义,左小,右大,根中间;
Update(root);
}
//查询x数的排名
int GetRankByVal(int p,int val)
{
if(p == 0)return 0;//如果没有了就返回0;
if(val == a[p].val)return a[a[p].l].size;
//如果查到了,就返回其左子树的大小
if(val < a[p].val)return GetRankByVal(a[p].l,val);
return GetRankByVal(a[p].r,val) + a[a[p].l].size + a[p].cnt;
}
int GetValByRank(int p,int rank)
{
if(p == 0)return INF;
//cout << rank << endl;
//cout << a[p].val << endl;
//cout << p << ": " << a[p].size << " l :"<< a[a[p].l].size << endl;
if(a[a[p].l].size >= rank)return GetValByRank(a[p].l,rank);
if(a[a[p].l].size + a[p].cnt >= rank)return a[p].val;
return GetValByRank(a[p].r,rank - a[a[p].l].size - a[p].cnt);
}
//右旋(压缩包??)
void zip(int &p){
int q = a[p].l;//将当前节点的左节点记录下来;
a[p].l = a[q].r,a[q].r = p,p = q;
//当前节点的左节点变为其原左节点的右节点,因为左子树的任何一棵子树都是比当前节点小的;当前节点的右节点不变;
//原左节点的左子树不变,右子树变为当前节点,即它原先的父节点;
//在将当前的节点变为原左节点,因为p是个引用,so调用的p会变为q,因为此时q为父节点了;
Update(a[p].r),Update(p);
}
//左旋
void zap(int &p)
{
int q = a[p].r;//将当前节点的右节点记录下来;
a[p].r = a[q].l , a[q].l = p , p = q;
//当前节点的右节点比当前节点及其左子树大,所以将当前节点变为其原节点的左子树,同时将原右节点的左子树变为当前节点的左子树
Update(a[p].l),Update(p);
}
void Insert(int &p,int val){
//如果没有该节点;
if(p == 0){
p = New(val);//注意p是引用!!!这很重要,p会涉及旋转,所以请读者好好理解;
return;
}
//如果有该节点;
if(val == a[p].val){
a[p].cnt++,Update(p);//副本加1;重新计算子树大小;
return;
}
//如果小了;
//根据定义,往左走;
if(val < a[p].val){
Insert(a[p].l,val);
if(a[p].dat < a[a[p].l].dat)zip(p);
//重点,如果加入的节点在左,为了使树更加平衡(因为此时左子树may大于右子树),我们需要将当前节点变为当前节点的左节点的右子树;这就是旋转操作;这是为了防止树退化成链的情况。
}
else {
Insert(a[p].r,val);
if(a[p].dat < a[a[p].r].dat)zap(p);//同理;
}
Update(p);//回溯时重新计算经过的节点的size;
}
//找前驱
int GetPre(int val)
{
int ans = 1;//a[1].val == -INF
int p = root;
while(p)
{
if(val == a[p].val){
if(a[p].l > 0){
p = a[p].l;
while(a[p].r > 0)p = a[p].r;
ans = p;
}
break;
}
if(a[p].val < val and a[p].val > a[ans].val)ans = p;
p = val < a[p].val ? a[p].l : a[p].r;
}
return a[ans].val;
}
//后继同理
int GetNext(int val)
{
int ans = 2;//a[2].val = INF;
int p = root;
while(p)
{
if(val == a[p].val)
{
if(a[p].r > 0)
{
p = a[p].r;
while(a[p].l > 0)p = a[p].l;
ans = p;
}
break;
}
if(a[p].val > val and a[p].val < a[ans].val)ans = p;
p = val < a[p].val ? a[p].l : a[p].r;
}
return a[ans].val;
}
//删除操作
void Remove(int &p,int val)
{
if(p == 0)return;
if(val == a[p].val)//查到了val;
{
if(a[p].cnt > 1){
a[p].cnt--,Update(p);
return;
}
if(a[p].l or a[p].r){//不是叶子节点,就将当前节点向下旋转,这是为了不让子树受到不必要的影响(可能删去后接上时不满足BST的基本结构);
if(!a[p].r or a[a[p].l].dat > a[a[p].r].dat)
//如果右子树不为空,或左子树的权值比右子树大;
zip(p),Remove(a[p].r,val);//右旋;
else zap(p),Remove(a[p].l,val);//反之,左旋;
Update(p);
}
else p = 0;
return;
}
val < a[p].val ? Remove(a[p].l,val) : Remove(a[p].r,val);
//同插入;
Update(p);//计算子树大小;
}
int main()
{
srand(time(NULL));
ios::sync_with_stdio(0);
build();
cin >> n;
int kmp = 2;
while(n--){
int opt,x;
cin >> opt >> x;
if(opt == 1)
{
kmp ++;
Insert(root,x);
}
if(opt == 2)Remove(root,x);
if(opt == 3)cout << GetRankByVal(root,x) << endl;
if(opt == 4)cout << GetValByRank(root,x+1) << endl;
if(opt == 5)cout << GetPre(x) << endl;
if(opt == 6)cout << GetNext(x) << endl;
// for(int i = 1 ; i <= kmp ; ++ i)
// cout << a[i].val << "," << a[i].l << "," << a[i].r << endl;
}
return 0;
}
//同时感谢海波大佬在我旁边给我的帮助。

可能我后面有些没有写注释了,恳请原谅,最近实在是太忙了。

感谢提供帮助的海波大佬($\color{skyblue}Na2S2O3$)