P3369 【模板】普通平衡树（Treap/SBT）
P3369 【模板】普通平衡树（Treap/SBT）
attack
发布于 2018-04-12 11:52:46
发布于 2018-04-12 11:52:46
题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
- 插入x数
- 删除x数(若有多个相同的数，因只删除一个)
- 查询x数的排名(若有多个相同的数，因输出最小的排名)
- 查询排名为x的数
- 求x的前驱(前驱定义为小于x，且最大的数)
- 求x的后继(后继定义为大于x，且最小的数)
输入输出格式
输入格式：
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)
输出格式：
对于操作3,4,5,6每行输出一个数，表示对应答案
输入输出样例
输入样例#1：
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598输出样例#1：
106465
84185
492737说明
时空限制：1000ms,128M
1.n的数据范围：n<=100000
2.每个数的数据范围：[-1e7,1e7]
来源：Tyvj1728 原名：普通平衡树
在此鸣谢
我的天，，splay这种东西直接要人命，，
思路比KMP好想，代码比DP简单。
但是调试。。。。。。
呵呵，，，，，
至于怎么做：
https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P3369
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 using namespace std;
6 const int MAXN=100005;
7 const int maxn=0x7fffffff;
8 void read(int &n)
9 {
10 char c='+';int x=0;bool flag=0;
11 while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
12 while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}
13 flag==1?n=-x:n=x;
14 }
15 struct SPLAY
16 {
17 #define root e[0].ch[1]
18 struct node
19 {
20 int v;// 节点的权值
21 int fa;
22 int ch[2];
23 int sum;// 当前节点的子树的元素
24 int recy;// 当前节点重复的次数
25 };
26 node e[MAXN];
27 int tot,points;
28 SPLAY()
29 {
30 tot=0;points=0;
31 }
32 void update(int pos)// 上传标记
33 {
34 e[pos].sum=e[e[pos].ch[0]].sum+e[e[pos].ch[1]].sum+e[pos].recy;
35 }
36 int identify(int x)//找到编号为x的节点是他的父亲的左孩子节点还是右孩子节点
37 {
38 return e[e[x].fa].ch[0]==x?0:1;
39 }
40 int connect(int son,int father,int how)// 把编号为son的节点连接到编号为father的节点的how孩子
41 {
42 e[son].fa=father;
43 e[father].ch[how]=son;
44 }
45 void rotate(int x)//双旋
46 {
47 int y=e[x].fa;
48 int R=e[y].fa;
49 int Rson=identify(y);
50 int yson=identify(x);
51 int B=e[x].ch[yson^1];
52 connect(B,y,yson);
53 connect(y,x,(yson^1));
54 connect(x,R,Rson);
55 update(y);update(x);
56 }
57 void Splay(int pos,int to)// 把编号为pos的节点旋转到编号为to的节点
58 {
59 to=e[to].fa;
60 while(e[pos].fa!=to)
61 {
62 int up=e[pos].fa;
63 if(e[up].fa==to) rotate(pos);
64 else if(identify(up)==identify(pos))
65 {
66 rotate(up);
67 rotate(pos);
68 }
69 else
70 {
71 rotate(pos);
72 rotate(pos);
73 }
74 }
75 }
76
77 int crepoint(int v,int father)// 新建一个节点
78 {
79 tot++;
80 e[tot].fa=father;
81 e[tot].recy=e[tot].sum=1;
82 e[tot].v=v;
83 return tot;
84 }
85 void destroy(int x)// 直接摧毁一个节点
86 {
87 e[x].ch[0]=e[x].ch[1]=e[x].fa=e[x].recy=e[x].sum=e[x].v=0;
88 if(x==tot) tot--;
89 }
90 int find(int v)// 找到 权值为v的点所在的位置
91 {
92 int now=root;
93 while(1)
94 {
95 if(e[now].v==v)
96 {
97 Splay(now,root);
98 return now;
99 }
100 int nxt=v<e[now].v?0:1;
101 if(!e[now].ch[nxt])return 0;
102 now=e[now].ch[nxt];
103 }
104 }
105 int build(int v)// 新开一个节点
106 {
107 points++;
108 if(tot==0)
109 {
110 root=1;
111 crepoint(v,0);
112 }
113 else
114 {
115 int now=root;
116 while(1)
117 {
118 e[now].sum++;// 经过的路径上的点的子树的元素一定会++
119 if(e[now].v==v)
120 {
121 e[now].recy++;
122 return now;
123 }
124 int nxt=v<e[now].v?0:1;
125 if(!e[now].ch[nxt])
126 {
127 crepoint(v,now);
128 e[now].ch[nxt]=tot;
129 return tot;
130 }
131 now=e[now].ch[nxt];
132 }
133 }
134 return 0;//what....
135 }
136 int push(int v)// 新开一个节点并旋转到根
137 {
138 int p=build(v);
139 Splay(p,root);
140 }
141 void pop(int v)// 删除节点，并调整树的结构
142 {
143 int deal=find(v);
144 if(!deal) return ;
145 points--;
146 if(e[deal].recy>1)
147 {
148 e[deal].recy--;
149 e[deal].sum--;
150 return;
151 }
152 if(!e[deal].ch[0])
153 {
154 root=e[deal].ch[1];
155 e[root].fa=0;
156 }
157 else
158 {
159 int le=e[deal].ch[0];
160 while(e[le].ch[1])
161 le=e[le].ch[1];
162
163 Splay(le,e[deal].ch[0]);
164
165 int ri=e[deal].ch[1];
166 connect(ri,le,1);
167 connect(le,0,1);
168 update(le);
169 }
170 destroy(deal);
171 }
172 int rank(int v)// 查询值为v的数的排名
173 {
174 int ans=0,now=root;
175 while(1)
176 {
177 if(e[now].v==v)
178 return ans+e[e[now].ch[0]].sum+1;
179 if(now==0)return 0;
180 if(v<e[now].v) now=e[now].ch[0];
181 else
182 {
183 ans+=e[e[now].ch[0]].sum+e[now].recy;
184 now=e[now].ch[1];
185 }
186
187 }
188 if(now) Splay(now,root);
189 return 0;
190 }
191 int arank(int x)//查询排名为x的数是什么
192 {
193 if(x>points) return -maxn;
194 int now=root;
195 while(1)
196 {
197 int used=e[now].sum-e[e[now].ch[1]].sum;
198 if(x>e[e[now].ch[0]].sum&&x<=used)break;
199 if(x<used)
200 now=e[now].ch[0];
201 else
202 {
203 x=x-used;
204 now=e[now].ch[1];
205 }
206 }
207 Splay(now,root);
208 return e[now].v;
209 }
210 int lower(int v)// 小于v的最大值
211 {
212 int now=root;
213 int ans=-maxn;
214 while(now)
215 {
216 if(e[now].v<v&&e[now].v>ans) ans=e[now].v;
217 if(v>e[now].v) now=e[now].ch[1];
218 else now=e[now].ch[0];
219 }
220 return ans;
221 }
222 int upper(int v)
223 {
224 int now=root;
225 int ans=maxn;
226 while(now)
227 {
228 if(e[now].v>v&&e[now].v<ans) ans=e[now].v;
229 if(v<e[now].v) now=e[now].ch[0];
230 else now=e[now].ch[1];
231 }
232 return ans;
233 }
234 };
235 SPLAY s;
236 int main()
237 {
238
239 int n;
240 read(n);
241 for(int i=1;i<=n;i++)
242 {
243 int opt,x;
244 read(opt);read(x);
245 if(opt==1)
246 s.push(x);
247 else if(opt==2)
248 s.pop(x);
249 else if(opt==3)
250 printf("%d\n",s.rank(x));
251 else if(opt==4)
252 printf("%d\n",s.arank(x));
253 else if(opt==5)
254 printf("%d\n",s.lower(x));
255 else if(opt==6)
256 printf("%d\n",s.upper(x));
257 }
258 return 0;
259 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-07-28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录