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

本文主要是介绍【模板】普通平衡树（Treap/SBT）||Splay，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

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

输入格式：
第一行为 nn ，表示操作的个数,下面 nn 行每行有两个数 optopt 和 xx ， optopt 表示操作的序号( 1 \leq opt \leq 6 1≤opt≤6 )

输出格式：
对于操作 3,4,5,63,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 \leq 100000 n≤100000

2.每个数的数据范围： [-{10}^7, {10}^7][−10
7
,10
7
]

思路：就是平衡树
这个版本不错：https://blog.csdn.net/clove_unique/article/details/50630280

https://www.cnblogs.com/Mathics/p/3971220.html

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>#define N 1000005using namespace std;
typedef long long LL;int total;//整颗树的总节点数 
int root;//整棵树的根节点 int f[N];//f[i]表示i的父节点 int a[N][2];//平衡树，左右子节点,0是左儿子，1是右儿子 
int cnt[N];//cnt[i]表示当前节点关键字出现的次数
int size[N];//size[i]表示i这棵子数的大小，也就是以i为根节点，下面一共有多少个子节点
int key[N];//key[i]表示i的关键字（即节点i代表的那个数字） inline void clear(int x)//给当前节点清零 {a[x][1]=a[x][0]=cnt[x]=size[x]=f[x]=key[x]=0;} inline int get(int x)//得到改点是其父节点的左儿子还是右儿子,返还1就是右儿子，返还0就是左儿子，可自行模拟 {return a[f[x]][1]==x;} inline void updata(int x)//跟新当前sizede值（用于修改之后） {if(x){size[x]=cnt[x];if(a[x][0])size[x]+=size[a[x][0]];if(a[x][1])size[x]+=size[a[x][1]];}}inline void rotate(int x)//旋转{int old=f[x],older=f[old],which=get(x);//显而易见，即节点x的父节点 //这个也显而易见，即节点x父节点的父节点（也就是节点x的祖父节点） //这是判断x是其父节点的左儿子还是右儿子，也就是确定位置 a[old][which]=a[x][which^1];//x的父节点的x的那个位置指向x本身的儿子 f[a[old][which]]=old;//新晋升的儿子指向它现在的父亲,'即x的一个儿子指向x的父亲a[x][which^1]=old;f[old]=x;f[x]=older;//被篡位的x指向原来它父亲的父亲if(older)a[older][a[older][1]==old]=x; updata(old);updata(x);}inline void splay(int x){for(int i;(i=f[x]);rotate(x))if(f[i])rotate((get(x)==get(i))?i:x);root=x;     }inline void insert(int x)//插入操作 {if(root==0)//若是一科空树 {total++;a[total][0]=a[total][1]=f[total]=0;root=total;size[total]=cnt[total]=1;key[total]=x;return;}int now=root;int last=0;while (1){if(x==key[now]) //找到一个与插入相同的 {cnt[now]++;updata(now);updata(last);splay(now);break;}last=now;  now=a[now][key[now]<x];if(now==0)//已经找到底下了 {total++;a[total][0]=a[total][1]=0;f[total]=last;size[total]=cnt[total]=1;a[last][key[last]<x]=total;key[total]=x;updata(last);//没必要updata（自己）因为它自己就是新插入在最底下的 splay(total);//不用说了吧，维护整棵树的平衡 break;  }}} inline int find(int x)//查找排名 {int ans=0;int now=root;while(1){if(x<key[now])now=a[now][0];//若小于该节点，则往左边走 else{ans+=(a[now][0]?size[a[now][0]]:0);//往右走的话就加上左边节点的数目，因为小于嘛 if(x==key[now]){splay(now);return ans+1;   }//若正好找到就splay一下退出就行了，别忘了加一，当然也可以一开始就在ans定义时就赋值为一 ans+=cnt[now];now=a[now][1];} }} inline int find2(int x)//查找排名为x的点{int now=root;while(1){if(a[now][0]&&x<=size[a[now][0]])now=a[now][0];else {int temp=(a[now][0]?size[a[now][0]]:0)+cnt[now];if(x<=temp)return key[now];x-=temp;now=a[now][1];}}} inline int pre() //前驱 {int now=a[root][0];while(a[now][1])now=a[now][1];return now;}inline int next(){int now=a[root][1];while(a[now][0])now=a[now][0];return now;} inline void dele(int x)//删除{int whatever=find(x);//查找x的位置，且现在现在是根了 if(cnt[root]>1) {cnt[root]--;updata(root);return;}if(!a[root][0]&&!a[root][1]){clear(root);root=0;return;}if(!a[root][0]){int oldroot=root;root=a[root][1];f[root]=0;clear(oldroot);return;}elseif(!a[root][1]){int oldroot=root;root=a[root][0];f[root]=0;clear(oldroot);return;}  int leftbig=pre(),oldroot=root;splay(leftbig);a[root][1]=a[oldroot][1];f[a[oldroot][1]]=root;clear(oldroot);updata(root);} int main(){int n=0;scanf("%d",&n);for(int i=1;i<=n;i++){int s,x;scanf("%d%d",&s,&x);switch(s){case 1:insert(x);break;case 2:dele(x);break;case 3:printf("%d\n",find(x));break;case 4:printf("%d\n",find2(x));break;case 5:insert(x);printf("%d\n",key[pre()]);dele(x);break;case 6:insert(x);printf("%d\n",key[next()]);dele(x);break;}}}