皆さん、こんにちは。上一篇文章，我们讲了Splay如何实现。这一篇我们来让我们的伸展树短一点。
上一篇Splay讲解的链接：リンク。
首先还是变量的定义，在这里呢，我把一些小函数也用Define来实现了。
1).变量定义和小函数。
#include<cstdio>
using namespace std;
using namespace std;
const int MAXN=1e5+5;
const int INF=1<<30;
struct Floor{ int Val,Fa,Size,Recy,Ch[2];}T[MAXN];//定义伸展树的结构体。
int N,Opt,X,NodeNum,TSize;//一些基础变量。
//定义根为零结点的右儿子。
#define Root RS(0)
//用Define来表示各各变量。
#define Val(X) T[X].Val
#define LS(X) T[X].Ch[0]
#define RS(X) T[X].Ch[1]
#define Fa(X) T[X].Fa
#define Recy(X) T[X].Recy
#define Size(X) T[X].Size
//更新函数
#define Update(X) Size(X)=Size(LS(X))+Size(RS(X))+Recy(X)
//关系函数
#define Ident(X) (RS(Fa(X))==X)
//连接函数
#define Connect(X,Y,Son) T[Fa(X)=Y].Ch[Son]=X
2).旋转函数
void Rotate(int X){
int YSon=Ident(X),Y=Fa(X),RSon=Ident(Y),R=Fa(Y),XSon=YSon^1,B=T[X].Ch[XSon];//记录位置和关系。
Connect(B,Y,YSon);Connect(X,R,RSon);Connect(Y,X,XSon);//旋转三板斧。
Update(Y);Update(X);//更新。
}
3).伸展函数
void Splay(int From,int To){
To=Fa(To);
while(Fa(From)!=To){
int Up=Fa(From);
if(Fa(Up)!=To) Ident(From)^Ident(To) ? Rotate(From):Rotate(Up);//判断是“之”字形还是“一”字型。
Rotate(From);
}
}
4).查找函数
int Find(int Value){
int Now=Root;
while(Now){
if(Value==Val(Now)){ Splay(Now,Root);return Now;}
Now=T[Now].Ch[Value>Val(Now)];//判断Now向左还是向右。
}
return 0;
}
5).创造结点
void CreNode(int Value,int Father){
NodeNum++;
Val(NodeNum)=Value;
Fa(NodeNum)=Father;
Size(NodeNum)=Recy(NodeNum)=1;
}
6).创造结点
int Insert(int Value){
if(!TSize){
TSize++;
Root=NodeNum+1;
CreNode(Value,0);
return NodeNum;
}
TSize++;
int Now=Root;
while(Now){
Size(Now)++;
if(Val(Now)==Value){ Recy(Now)++;return Now;}
int Next=Value<T[Now].Val ? 0:1;
if(!T[Now].Ch[Next]){
T[Now].Ch[Next]=NodeNum+1;
CreNode(Value,Now);
return NodeNum;
}
Now=T[Now].Ch[Next];
}
return 0;
}
7).创造结点
void Push(int Value){ int AddNode=Insert(Value);Splay(AddNode,Root);}
8).删除结点
void Destroy(int X){ Val(X)=Fa(X)=Size(X)=Recy(X)=LS(X)=RS(X)=0;}
9).删除结点
void Pop(int Value){
int KillNode=Find(Value);
if(!KillNode) return;
TSize--;
if(Recy(KillNode)>1){ Recy(KillNode)--;Size(KillNode)--;return;}
else if(!LS(KillNode)){ Root=RS(KillNode);Fa(Root)=0;}
else{
int LMAX=LS(KillNode);
while(RS(LMAX)) LMAX=RS(LMAX);
int R=RS(KillNode);
Splay(LMAX,LS(KillNode));
Connect(R,LMAX,1);Connect(LMAX,0,1);
Update(LMAX);
}
Destroy(KillNode);
}
10).查找值为X的排名
int Rank(int Value){
int Now=Root,Ans=1;
while(Now){
if(Value==Val(Now)){
Ans+=Size(LS(Now));
Splay(Now,Root);
return Ans;
}else{
Ans=Ans+(Value>Val(Now))*(Size(LS(Now))+Recy(Now));
Now=T[Now].Ch[Value>Val(Now)];
}
}
return 0;
}
11).查找第X小的数
int Atrank(int X){
if(X>TSize) return 0;
int Now=Root;
while(Now){
if(Size(LS(Now))<X && X<=Size(Now)-Size(RS(Now))){
Splay(Now,Root);
return Val(Now);
}else if(X<=Size(LS(Now))) Now=LS(Now);
else{
X=X-(Size(Now)-Size(RS(Now)));
Now=RS(Now);
}
}
return 0;
}
12).查找值为X的前驱
int Lower(int Value){
int Now=Root,Ans=-INF;
while(Now){
if(Value>Val(Now) && Val(Now)>Ans) Ans=Val(Now);
Now=T[Now].Ch[Value>Val(Now)];
}
return Ans;
}
13).查找值为X的后继
int Upper(int Value){
int Now=Root,Ans=INF;
while(Now){
if(Value<Val(Now) && Val(Now)<Ans) Ans=Val(Now);
Now=T[Now].Ch[Value>=Val(Now)];
}
return Ans;
}
14).主函数
int main(){
scanf("%d",&N);
while(N--){
scanf("%d%d",&Opt,&X);
if(Opt==1) Push(X);
else if(Opt==2) Pop(X);
else if(Opt==3) printf("%d\n",Rank(X));
else if(Opt==4) printf("%d\n",Atrank(X));
else if(Opt==5) printf("%d\n",Lower(X));
else printf("%d\n",Upper(X));
}
return 0;
}
再悄悄说一声，把上面所有的代码拼起来也可以AC平衡树模板题。