首页 > 代码库 > Tyvj 1728 普通平衡树
Tyvj 1728 普通平衡树
Submit: 13242 Solved: 5675
[Submit][Status][Discuss]
Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
Input
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)
Output
对于操作3,4,5,6每行输出一个数，表示对应答案
Sample Input
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
106465
84185
492737
84185
492737
HINT
1.n的数据范围：n<=100000
2.每个数的数据范围：[-2e9,2e9]
Source
平衡树
思路
splay
事实上，哨兵还是挺有用的，减轻逻辑负担；
由于是模板题：
t节点数值，f节点父亲编号，sz以节点为根的子树尺寸，am节点中数的个数，s节点的左右子编号；
rot()单旋；
splay()伸展（这里没有用双旋，因为脑模单旋和双旋操作量和结果一样，实测双旋也并不比单旋快）；
ins()添加数；
find1()把要查找的节点旋到树根；
find2()查找序号对应节点；
find3()查找前驱；
find4()查找后继；
del()删除数；
del():减少root节点的am值或是删除root节点；
case1:减少root节点的sz和am值并退出；
case2:
将root的右子树接到root的左子树中的最右子上，同时更新从root的左子树到左子树树中最右子的路径上的节点的sz值；
调整嫁接处的值，root改为原root的左子；
将原root的左子树的最右子旋到根的位置；
代码实现
1 #include<cstdio> 2 const int maxn=3e5; 3 int n,ope,val; 4 int rt,hd; 5 int t[maxn],f[maxn],sz[maxn],am[maxn],s[maxn][2]; 6 void rot(int x){ 7 int y=f[x],z=f[y],l,r; 8 l=s[y][0]==x?0:1,r=l^1; 9 if(y==rt) rt=x;10 else{11 if(s[z][0]==y) s[z][0]=x;12 else s[z][1]=x;13 }14 f[x]=z,f[y]=x,f[s[x][r]]=y;15 s[y][l]=s[x][r],s[x][r]=y;16 sz[y]=sz[s[y][0]]+sz[s[y][1]]+am[y];17 sz[x]=sz[s[x][0]]+sz[s[x][1]]+am[x];18 }19 void splay(int x){while(x!=rt) rot(x);}20 void ins(int k,int x,int fa){21 if(!rt){rt=++hd,t[rt]=x,sz[rt]=1,am[rt]++;return;}22 while(k) fa=k,++sz[k],k=s[k][x>t[k]];23 k=s[fa][x>t[fa]]=++hd;24 t[k]=x,sz[k]=1,f[k]=fa,am[k]++;25 splay(k);26 }27 void find1(int k,int x){28 if(!k) return;29 while(s[k][x>t[k]]&&t[k]!=x) k=s[k][x>t[k]];30 splay(k);31 }32 int find2(int k,int x){33 if(x<=sz[s[k][0]]) return find2(s[k][0],x);34 if(x==sz[s[k][0]]+1) return t[k];35 return find2(s[k][1],x-sz[s[k][0]]-1);36 }37 int find3(int k,int x,int sum){38 if(!k) return sum;39 if(x>t[k]) return find3(s[k][1],x,t[k]);40 else return find3(s[k][0],x,sum);41 }42 int find4(int k,int x,int sum){43 if(!k) return sum;44 if(x<t[k]) return find4(s[k][0],x,t[k]);45 else return find4(s[k][1],x,sum);46 }47 void del(int k,int x){48 if(am[k]>1){am[k]--,sz[k]--;return;}49 x=s[k][1];50 while(s[x][0]) x=s[x][0],sz[x]+=sz[s[k][0]];51 f[s[k][0]]=x,s[x][0]=s[k][0],rt=s[k][1];52 f[rt]=0;53 splay(x);54 }55 int main(){56 freopen("phs.in","r",stdin);57 freopen("phs.out","w",stdout);58 ins(rt,-2e9-10,0),ins(rt,2e9+10,0);59 scanf("%d",&n);60 for(int i=1;i<=n;i++){61 scanf("%d%d",&ope,&val);62 if(ope==1) ins(rt,val,0);63 if(ope==2) find1(rt,val),del(rt,0);64 if(ope==3) find1(rt,val),printf("%d\n",sz[s[rt][0]]);65 if(ope==4) printf("%d\n",find2(rt,val+1));66 if(ope==5) printf("%d\n",find3(rt,val,0));67 if(ope==6) printf("%d\n",find4(rt,val,0));68 }69 return 0;70 }
Tyvj 1728 普通平衡树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。