题目描述
您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:
插入数值 x。
删除数值 x(若有多个相同的数,应只删除一个)。
查询数值 x 的排名(若有多个相同的数,应输出最小的排名)。
查询排名为 x 的数值。
求数值 x 的前驱(前驱定义为小于 x 的最大的数)。
求数值 x 的后继(后继定义为大于 x 的最小的数)。
注意: 数据保证查询的结果一定存在。
输入格式
第一行为 n,表示操作的个数。
接下来 n 行每行有两个数 opt 和 x,opt 表示操作的序号(1≤opt≤6)。
输出格式
对于操作 3,4,5,6 每行输出一个数,表示对应答案。
数据范围
1≤n≤100000,所有数均在 −107 到 107 内。
样例
输入样例:
8
1 10
1 20
1 30
3 20
4 2
2 10
5 25
6 -1
输出样例:
2
20
20
20
似乎splay的题解严重短缺,于是我来一篇。
Splay,她写起来方便;
Splay,她也灵活多变。
Splay,她比Treap美,她富有深意;
Splay,她默默无闻地创造了(毒瘤)LCT的奇迹。
如果您还不会BST及其基本操作……好吧,人生还是可以很快乐的
可以说,splay相比BST,只多了splay和rotate两个函数
算法思路:
大家都知道不改变树的中序遍历并调整树高使树变得平衡的方法之一就是旋转。
但是如果随便瞎转是不能维持平衡的,splay的旋转方法是:每操作一个节点,就把它splay到根节点
为什么这样能保证复杂度,证明比较复杂,有兴趣的读者,个人推荐 https://www.cnblogs.com/Mr-Spade/p/9715203.html
说了半天,到底怎吗splay到根呀,别急,先来看两张丑图
图1-1:右旋y,可以发现中序遍历不变
解释:把y向右转,由x取代y原先的位置,将x的右子树置为y的左子树,将y置为x的右子树
图1-2:左旋y,可以发现中序遍历不变
解释:把y向左转,由x取代y原先的位置,将x的左子树置为y的右子树,将y置为x的左子树
可以发现,上面两种情况其实是对称的
在rotate函数中,可以智能地根据左右儿子关系判断该左旋还是右旋
还有两张更丑的图:
图2-1:左旋x,原理基本和上面相同,不在赘述
图2-2:右旋x,不在赘述
以上就是x,y,z三点所有可能的关系情况(1,2,3,4是辅助用的,在实际情况中可能是没有的,但并无影响)
相信通过上面的几张图,大家已经对旋转由了比较清晰的认识
于是我们亮出splay的核心操作:
如果x,y,z成直线(图1-1,图1-2)则先转y,再转x(左旋还是右旋rotate会判断)
如果x,y,z成折线(图2-1,图2-2)则先转x,再转x(左旋还是右旋rotate会判断)
自己在纸上模拟一下,会发现,每操作一次,x就会被转到原先z的位置(即向上走两格)
于是,便有了:
好写的splay:
void splay(int x,int p)
{
while(tr[x].p!=p)
{
int y=tr[x].p,z=tr[y].p;
if(z!=p)
{
if((tr[y].son[1]==x)^(tr[z].son[1]==y))rotate(x);
else rotate(y);
}
rotate(x);
}
if(!p)root=x;
}
其功能就是把x转到p下方,特别地,若p==0,则把x转到根
毒瘤的rotate:
void rotate(int x)
{
int y=tr[x].p,z=tr[y].p;
int k=(tr[y].son[1]==x);
tr[z].son[tr[z].son[1]==y]=x,tr[x].p=z;
tr[y].son[k]=tr[x].son[k^1],tr[tr[x].son[k^1]].p=y;
tr[x].son[k^1]=y,tr[y].p=x;
pushup(y),pushup(x);
}
这个函数比较难,建议多在纸上模拟几遍。
注意:
本题数据已加强(逃),不管在什么操作后(包括查询),都要把被操作点转到根,不然#11会TLE
删除:
差点把这么重要的函数忘了。
Splay的删除有些不一样,不管是删除单点还是区间,都可以:
1.求出节点(区间右端点)的前驱,节点(区间左端点)的后继。
2.把前驱转到根,把后继转到前驱下面。
3.删除后继的左子树。
C++ 代码
#include<cstdio>
using namespace std;
const int N=1e6+5;
const int INF=2e9;
struct splay_tree{
int p,son[2],v,cnt,size;
void init(int _v,int _p)
{
v=_v,p=_p;
size=1,cnt=1;
}
}tr[N];
int root,idx,tag;
void pushup(int x)
{
tr[x].size=tr[tr[x].son[0]].size+tr[tr[x].son[1]].size+tr[x].cnt;
}
void rotate(int x)
{
int y=tr[x].p,z=tr[y].p;
int k=(tr[y].son[1]==x);
tr[z].son[tr[z].son[1]==y]=x,tr[x].p=z;
tr[y].son[k]=tr[x].son[k^1],tr[tr[x].son[k^1]].p=y;
tr[x].son[k^1]=y,tr[y].p=x;
pushup(y),pushup(x);
}
void splay(int x,int p)
{
while(tr[x].p!=p)
{
int y=tr[x].p,z=tr[y].p;
if(z!=p)
{
if((tr[y].son[1]==x)^(tr[z].son[1]==y))rotate(x);
else rotate(y);
}
rotate(x);
}
if(!p)root=x;
}
void Insert(int x)
{
int u=root,p=0;
while(u)
{
if(tr[u].v==x)
{
tr[u].cnt++;
pushup(u);
splay(u,0);
goto next_;
}
p=u,u=tr[u].son[x>tr[u].v];
}
u=++idx;
if(p)tr[p].son[x>tr[p].v]=u;
tr[u].init(x,p);
splay(u,0);
next_:;
}
void Remove(int x)
{
int u=root,p=0;
int k;
while(u)
{
if(tr[u].v==x)break;
p=u,u=tr[u].son[x>tr[u].v];
k=(x>tr[p].v);
}
if(!u)return;
else if(tr[u].cnt==1)
{
if(!tr[u].son[0]&&!tr[u].son[1])tr[p].son[k]=0,tr[u].p=0,pushup(p),splay(p,0);
else if(!tr[u].son[1])tr[p].son[k]=tr[u].son[0],tr[tr[u].son[0]].p=p,tr[u].p=0,pushup(p),splay(p,0);
else if(!tr[u].son[0])tr[p].son[k]=tr[u].son[1],tr[tr[u].son[1]].p=p,tr[u].p=0,pushup(p),splay(p,0);
else
{
int l=tr[u].son[0],r=tr[u].son[1];
while(tr[l].son[1])l=tr[l].son[1];
while(tr[r].son[0])r=tr[r].son[0];
splay(l,0),splay(r,root);
tr[r].son[0]=0,tr[tr[r].son[0]].p=0,pushup(r),pushup(root);
}
}
else tr[u].cnt--,pushup(u),splay(u,0);
}
int get_rank(int p,int x)
{
if(p==0)return -1;
else if(x==tr[p].v)
{
tag=p;
return tr[tr[p].son[0]].size+1;
}
else if(x<tr[p].v)return get_rank(tr[p].son[0],x);
else return get_rank(tr[p].son[1],x)+tr[tr[p].son[0]].size+tr[p].cnt;
}
int find_rank(int p,int x)
{
if(p==0)return INF;
if(tr[tr[p].son[0]].size>=x)return find_rank(tr[p].son[0],x);
if(tr[tr[p].son[0]].size+tr[p].cnt>=x)
{
tag=p;
return tr[p].v;
}
return find_rank(tr[p].son[1],x-tr[tr[p].son[0]].size-tr[p].cnt);
}
int get_pre(int x)
{
int ans=1;
int u=root,p=0;
while(u)
{
if(tr[u].v==x)break;
p=u,u=tr[u].son[x>tr[u].v];
if(tr[p].v<x&&tr[p].v>tr[ans].v)ans=p;
}
if(!u||!tr[u].son[0])return tr[ans].v;
u=tr[u].son[0];
while(tr[u].son[1])u=tr[u].son[1];
return tr[u].v;
}
int get_next(int x)
{
int ans=2;
int u=root,p=0;
while(u)
{
if(tr[u].v==x)break;
p=u,u=tr[u].son[x>tr[u].v];
if(tr[p].v>x&&tr[p].v<tr[ans].v)ans=p;
}
if(!u||!tr[u].son[1])return tr[ans].v;
u=tr[u].son[1];
while(tr[u].son[0])u=tr[u].son[0];
return tr[u].v;
}
int main()
{
Insert(-INF),Insert(INF);
int n;
scanf("%d",&n);
while(n--)
{
int op,x;
scanf("%d%d",&op,&x);
if(op==1)Insert(x);
if(op==2)Remove(x);
if(op==3)printf("%d\n",get_rank(root,x)-1),splay(tag,0);
if(op==4)printf("%d\n",find_rank(root,x+1)),splay(tag,0);
if(op==5)printf("%d\n",get_pre(x));
if(op==6)printf("%d\n",get_next(x));
}
return 0;
}
注:这份代码是我第一份平衡树代码,当时代码能力比较弱,代码中有些地方的pushup可能是多余的(当然rotate里边的是绝对要的),希望没有应为这个影响读者阅读。
这道题用splay必须要记录cnt吗
Tag啥意思呀
记录查询到的节点的编号,在查询完后把它splay到根。如果在递归的时候就splay的话会把父子关系弄坏导致出错
牛,tql 大佬 我想问一下你是自己想的 cnt 和 tag 吗 这码力真的太强了 orz
cnt 是李煜东书中介绍的一种技巧哦,tag 自己想的。其实如果不使用递归的话,用不着 tag 的,只是个人更喜欢递归。
还有 goto next_; 这句是什么意思啊?
goto 是转向语句,在执行完 goto next_ ; 一行后直接跳转到 next_ : ;一行。作用就是如果找到一个已经在 splay中的点,且其权值正好为要插入的 x ,那么在增加 cnt[x] 并splay(u) 后,应该直接结束 Insert 函数并返回。但如果在 while 循环中直接 return 似乎会有问题,具体什么原因我也不太清楚,毕竟本人学 C++ 语言时学得比较仓促,如果有大佬知道的望指出。由于不能直接 return 于是我就用了 goto 语句。
致歉:有误,重新提交发现直接 return 不会有问题,当时出错可能是别的问题
感谢dalao讲解
%%% dalao tql