首页 > > 程序设计 > C/C++ >

P3369 【模板】普通平衡树（Treap/SBT）

2018-06-17 22:10:33来源：未知阅读 ()

题目描述

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

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1：

输出样例#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 }