P3369 【模板】普通平衡树 题解
难度：⭐⭐⭐⭐⭐
知识点：平衡树
题目链接
序言：调了超久的一道题！向提高组冲击的第一步！treap！
1. 入手程序
模板题么，就没什么思路了，既然是练习treap，直接开整呗~
2. 编程思路
首先，Treap=Tree+Heap，Tree指的是二叉排序树，Heap则是指堆
它融合了二叉排序树的优点：操作方便、多样
同时使用堆结构，和随机值规避了二叉排序树容易退化成一条链的问题
剩下的看代码吧~
放心，注释多到爆炸
3. AC代码
/*
size[i] 以i为根的子树的节点数
v[i] i节点的权值
num[i] 由于可能有重复（上文讲的是没有重复的），所以，我们将权值一样的存在一个节点里面，num数组存储的是i节点存的个数
son[i][2] 存储i节点的儿子，注意，这里不是完全二叉树所以需要存储儿子，son[i][0]表示左儿子，son[i][1]表示右儿子。
rd[i] i节点的一个随机值
*/
#include<bits/stdc++.h>
using namespace std;
const int MAX=100500;
int n;
int size[MAX],num[MAX],v[MAX],son[MAX][2],rd[MAX];
int x,opt,r,sum;//x,opt与题干中同义，sum为节点个数
void gx(int g)//更新节点个数
{
size[g]=size[son[g][0]]+size[son[g][1]]+num[g];
//g的节点数=左右儿子节点数之和+g本身存有数量
}
void xz(int &g,int d)//旋转，以g为根，d=0左旋，反之右旋
{
//x^1时,如果x为偶数则为x+1，否则为x-1
//这里相当于1变0，0变1
int v1=son[g][d^1];//左旋时，v1为g的右儿子，反之为g的左儿子
son[g][d^1]=son[v1][d];
//左旋时，g的右儿子变成v1的左儿子,反之g的左儿子变成v1的右儿子
son[v1][d]=g;
//左旋时，v1的左儿子变成g,反之v1的右儿子变成g
gx(g);
gx(v1);
//更新父节点子节点个数
g=v1;//最后换根
}
void cr(int &g,int x)//插入，以g为根，插入x
{
if(!g)//空树
{
g=++sum;//节点总数加1
size[g]=num[g]=1;//于是有1个节点在树中了,当前节点有1个重复数字
v[g]=x;//值为x
rd[g]=rand();//生成随机值，拿来维护堆，防止退化成链
return;
}
if(v[g]==x)//已有该权值，那么直接个数加加即可
{
num[g]++;
size[g]++;
return;
}
//继续向下寻找
int v1=(x>v[g]);//左儿子或右二子
cr(son[g][v1],x);
if(rd[g]<rd[son[g][v1]])//这样转不破坏堆的性质
{
xz(g,v1^1);//旋转
//x^1时,如果x为偶数则为x+1，否则为x-1
//这里相当于1变0，0变1
}
gx(g);//更新父节点子节点个数
}
void sc(int &g,int x)//根为g，删除x
{
if(!g)//空节点，不可能有要删的这个点
{
return;
}
//如果x和v[g]不相等，直接转到相应子树解决问题
if(x<v[g])
{
sc(son[g][0],x);
}
else if(x>v[g])
{
sc(son[g][1],x);
}
else//就在这棵树
{
if(!son[g][0] && !son[g][1]) //木有在节点啦，x是叶子节点
{
num[g]--;
size[g]--;
//扣掉个数
if(num[g]==0)//如果没数了，删除节点
{
g=0;
}
}
else if(son[g][0] && !son[g][1])
{
xz(g,1);//转~
sc(son[g][1],x);
}
else if(!son[g][0] && son[g][1])
{
xz(g,0);//转~
sc(son[g][0],x);
}
else if(son[g][0] && son[g][1])//俩都有，转大的
{
int v1=(rd[son[g][0]]>rd[son[g][1]]);//按随机值排，完美避开强迫症~
xz(g,v1);//转~
sc(son[g][v1],x);
}
}
gx(g);
}
int pm(int &g,int x)//根为g,查询x的排名
{
if(!g)//空空如也~
{
return 0;
}
if(v[g]==x)//返回左子树个数+1
{
return size[son[g][0]]+1;
}
if(v[g]<x)//x在右子树，返回左子树个数+在右子树的排名
{
return size[son[g][0]]+num[g]+pm(son[g][1],x);
}
if(v[g]>x)//x在左子树，返回在左子树的排名
{
return pm(son[g][0],x);
}
}
int cx(int &g,int x)
{
if(g==0)//又是空空如也~
{
return 0;
}
if(size[son[g][0]]>=x)//左子树节点数>x，在左节点里找
{
return cx(son[g][0],x);
}
else if(size[son[g][0]]+num[g]<x)//左节点节点数<x，查右子树的第x-左子树节点个数-根储存个数
{
return cx(son[g][1],x-num[g]-size[son[g][0]]);
}
else//当前就是要找的
{
return v[g];
}
}
int qq(int g,int x)//根为g，求x的前驱
{
if(g==0)//还是空空如也~
{
return -2000000005;
}
else if(v[g]>=x)//在根或右子树，去左子树找
{
return qq(son[g][0],x);
}
else//在左子树，取根和右子树最大的那一个
{
return max(v[g],qq(son[g][1],x));
}
}
int hj(int g,int x)//根为g，求x的后继
{
if(g==0)//依旧空空如也~
{
return 2000000005;
}
if(v[g]<=x)//在根或左子树，去右子树找
{
return hj(son[g][1],x);
}
else//在左子树，取根或右子树最小的那一个
{
return min(v[g],hj(son[g][0],x));
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>opt>>x;
if(opt==1)//插入 x 数
{
cr(r,x);
}
else if(opt==2)//删除 x 数(若有多个相同的数，因只删除一个)
{
sc(r,x);
}
else if(opt==3)//查询 x 数的排名(排名定义为比当前数小的数的个数 +1 )
{
cout<<pm(r,x)<<endl;
}
else if(opt==4)//查询排名为 x 的数
{
cout<<cx(r,x)<<endl;
}
else if(opt==5)//求 x 的前驱(前驱定义为小于 x，且最大的数)
{
cout<<qq(r,x)<<endl;
}
else if(opt==6)//求 x 的后继(后继定义为大于 x，且最小的数)
{
cout<<hj(r,x)<<endl;
}
}
return 0;
}
