【洛谷P3369】【模板】普通平衡树题解
题目链接
题意：
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
输入格式：
第一行为n，表示操作的个数。下面n行每行有两个整数opt和x，opt表示操作的序号
输出格式：
对于操作3,4,5,6每行输出一个数，表示对应答案
样例输入：
样例输出：
时空限制：
每个测试点1s，128MB
数据范围：
n≤105
|x|≤107
1≤opt≤6
题解：
首先来讲讲什么是Treap……
Treap的中文名叫树堆（Tree+Heap），同时拥有权值和优先级；对于权值来说，它是一棵二叉搜索树（BST）；对于优先级来说，它是一个堆。它可以被当作平衡树来用。
我们希望平衡树的高度尽量小，因为只有这样才能使每次操作的均摊时间复杂度趋于O(logn)。为了避免极端数据使平衡树退化为链，导致时间复杂度退化为O(n)，我们可以想到用优先级来维护Treap的形态使它的高度尽量趋于平衡，因为当每个节点的权值和优先级确定时，Treap的形态是唯一确定的。我们把每个节点的优先级用随机数rand()来赋值，这样Treap就趋于平衡了。
详细代码如下（指针实现）：
#include<cstdio>
#include<ctime>
#include<cstdlib>
struct node{
node*ch[];//指向左(ch[0])右(ch[1])子节点的指针
int v;//权值
int r;//优先级
int cnt;//该节点数的个数（数可以重复）
int size;//以该节点为根的子树中数的个数
node(int vv){//新建节点的构造函数
ch[]=ch[]=NULL;//两指针初始化为空指针
v=vv;//权值初始化
r=rand();//优先级用随机数初始化
cnt=size=;//只含一个数
}
};
node*super;//指向整棵Treap的大根的指针
int n,ans;
inline void maintain(node*p){//维护该节点的附加信息
p->size=p->cnt;
if(p->ch[]!=NULL)p->size+=p->ch[]->size;
if(p->ch[]!=NULL)p->size+=p->ch[]->size;
}
inline void rot(node*&p,int lr){//旋转操作(lr==0:左旋,lr==1:右旋)
node*k=p->ch[lr^];
p->ch[lr^]=k->ch[lr];
k->ch[lr]=p;
p=k;
}
void ins(node*&p,int val){//插入操作：在以p为根的子树中插入一个val数
if(p==NULL){//空节点直接建新点
p=new node(val);
}else if(val==p->v){//找到了已经存在的节点
p->cnt++;
p->size++;
}else if(val<p->v){
ins(p->ch[],val);//在左子节点中插入
if(p->ch[]->r<p->r){//维护优先级（小根堆）
rot(p,);
maintain(p->ch[]);
}
maintain(p);
}else{
ins(p->ch[],val);//在右子节点中插入
if(p->ch[]->r<p->r){
rot(p,);
maintain(p->ch[]);
}
maintain(p);
}
}
void del(node*&p,int val){//删除操作：在以p为根的子树中删除一个val数
if(val<p->v){
del(p->ch[],val);
maintain(p);
}else if(val>p->v){
del(p->ch[],val);
maintain(p);
}else{
if(p->cnt>){//该节点包含多个数，直接减即可
p->cnt--;
p->size--;
}else{//删除该节点
if(p->ch[]!=NULL){
if(p->ch[]!=NULL){//该节点有左右子节点
int lr=p->ch[]->r<p->ch[]->r?:;//选优先级小的子节点为根（小根堆）
rot(p,lr^);//旋转
del(p->ch[lr^],val);//递归向下删除
maintain(p);//递归返回向上维护
}else{//无右子节点
node*pp=p;
p=p->ch[];
delete pp;
}
}else{//无左子节点
if(p->ch[]!=NULL){
node*pp=p;
p=p->ch[];
delete pp;
}else{//都无
delete p;
p=NULL;
}
}
}
}
}
int qrank(node*p,int val){//当前以p为根的子树中小于val的数的个数+1
int ssl=p->ch[]==NULL?:p->ch[]->size;//该子树中小于val的数的个数
if(val==p->v)return ssl+;
else if(val<p->v){
if(p->ch[]!=NULL)return qrank(p->ch[],val);
else return ;
}else{
if(p->ch[]!=NULL)return ssl+p->cnt+qrank(p->ch[],val);
else return p->size+;
}
}
int qval(node*p,int rank){//在当前子树中查找排名为rank的数
int ssl=p->ch[]==NULL?:p->ch[]->size;
if(rank<=ssl)return qval(p->ch[],rank);
else if(rank<=ssl+p->cnt)return p->v;
else return qval(p->ch[],rank-ssl-p->cnt);
}
void pred(node*p,int val){//在当前子树中查找val的前驱
if(val<=p->v){
if(p->ch[]!=NULL)pred(p->ch[],val);
}else{
ans=p->v;//ans为暂定的答案，当ans无法再修改时，ans为最终答案
if(p->ch[]!=NULL)pred(p->ch[],val);
}
}
void succ(node*p,int val){
if(val>=p->v){
if(p->ch[]!=NULL)succ(p->ch[],val);
}else{
ans=p->v;
if(p->ch[]!=NULL)succ(p->ch[],val);
}
}
int main(){
srand(time());//初始化随机数种子
scanf("%d",&n);
while(n--){
int opt,x;
scanf("%d%d",&opt,&x);
switch(opt){
case :{
ins(super,x);
break;
}
case :{
del(super,x);
break;
}
case :{
printf("%d\n",qrank(super,x));
break;
}
case :{
printf("%d\n",qval(super,x));
break;
}
case :{
pred(super,x);
printf("%d\n",ans);
break;
}
case :{
succ(super,x);
printf("%d\n",ans);
break;
}
}
}
return ;
}