S p l a y Splay Splay 的性质
S p l a y Splay Splay ,比 T r e a p Treap Treap 更加灵活,更有拓展性的平衡树。
S p l a y Splay Splay 是以每一次插入,询问都将节点旋转到根的 B S T BST BST 。
g e t - s i z e get\text{-} size get-size 操作
计算以 x x x 为根的子树的大小。
inline void get_size(int x)
{
splay[x].size = splay[lson(x)].size + splay[rson(x)].size + splay[x].cnt;
}
r o t a t e rotate rotate 旋转操作
将 x x x 旋转到 父节点 y y y 的位置。
inline void rotate(int x)
{
int y=splay[x].p;
int z=splay[y].p;
int yson=(lson(y)==x?0:1);//x是y的那个儿子
int zson=(lson(z)==y?0:1);//z同理
//将x与z之间建立关系
splay[z].son[zson]=x;
splay[x].p=z;
//将y与x的yson^1节点建立关系
splay[y].son[yson]=splay[x].son[yson^1];
splay[splay[x].son[yson^1]].p=y;
//将y与x节点建立关系
splay[x].son[yson^1]=y;
splay[y].p=x;
//重新计算子树x与y的大小
get_size(y);
get_size(x);
}
S p l a y Splay Splay 核心操作
将 x x x 旋转到 T O TO TO 的儿子处。
rotate((lson(z)==y and lson(y)==x)?y:x); \text{rotate((lson(z)==y and lson(y)==x)?y:x);} rotate((lson(z)==y and lson(y)==x)?y:x); 的原因是 如果只旋转 x x x 就会使树的高度不变,如下图:
所以我们可以在 x , y , z x,y,z x,y,z 在同一侧时先旋转 y y y 后旋转 x x x 。
注意特判 z z z 为目标节点的情况。
inline void splay_to(int x,int TO)
{
while(splay[x].p!=TO)
{
int y=splay[x].p;
int z=splay[y].p;
if(z!=TO)
rotate((lson(z)==y&&lson(y)==x)?y:x);
rotate(x);
}
if(TO==0)root=x;
}
i n s e r t insert insert 插入操作
首先找到 x x x 得插入位置。
若存在值为 x x x 的节点则 s p l a y [ n o w ] c n t + + splay \text{[} now \text{]} _cnt ++ splay[now]cnt++
否则新建节点并记录新节点的各项的值与父亲节点的儿子节点指向。
最后将节点旋转到根。
inline void splay_insert(int x)
{
int now=root,father=0;
while(now!=0&&splay[now].k!=x)
{
father=now;
now=splay[now].son[splay[now].k<x];
}
if(now)
{
splay[now].cnt++;
}
else
{
now=++tot;
if(father)
splay[father].son[splay[father].k<x]=now;
splay[now].p=father;
splay[now].k=x;
splay[now].son[0]=splay[now].son[1]=0;
splay[now].size=splay[now].cnt=1;
}
splay_to(now,0);
}
s p l a y - f i n d - m o v e splay \text{-} find \text{-} move splay-find-move
意义:将值为 x x x 的节点移动到根。
将值为 x x x 的节点移动到根后左子树都是小于 x x x 的节点(包含 − i n f -inf −inf),那么值为 x x x 的节点的排名就是根的左子树的大小。
值为 x x x 的节点可能不存在所以要特判根节点的值时否小于 x x x。
即 r a n k ( x ) = s p l a y [ s p l a y [ r o o t ] . s o n [ 0 ] ] . s i z e + ( s p l a y [ r o o t ] . k < x ? s p l a y [ r o o t ] . c n t : 0 ) ; rank(x)=splay[splay[root].son[0]].size+(splay[root].k<x?splay[root].cnt:0); rank(x)=splay[splay[root].son[0]].size+(splay[root].k<x?splay[root].cnt:0);
inline void splay_find_move_find_rank(int x)
{
int now=root;
if(root==0)return;
while(splay[now].son[splay[now].k<x]!=0&&splay[now].k!=x)
{
now=splay[now].son[splay[now].k<x];
}
splay_to(now,0);
}
前驱和后继
将值为 x x x 的节点移动到根,那么根的左子树的最大值就是 x x x 的前驱,后继同理。
因为值为 x x x 的节点可能不存在所以要特判:
if(splay[now].k<x&&op==0||splay[now].k>x&&op==1)
return now;
返回的是前驱或后继的节点编号。
inline int find_pre_nxt(int x,int op)//op==0是前驱,op==1是后继
{
splay_find_move_find_rank(x);
int now=root;
if(splay[now].k<x&&op==0||splay[now].k>x&&op==1)
return now;
now=splay[now].son[op];
while(splay[now].son[op^1]!=0)
{
now=splay[now].son[op^1];
}
return now;
}
S p l a y − d e l e t e Splay - delete Splay−delete
将值为 x x x 的节点的前驱移动到根,后继移动到前驱的右儿子处。
若值为 x x x 的节点的 c n t > 1 cnt>1 cnt>1 则 s p a l y [ x ] . c n t − − spaly \text[x] .cnt-- spaly[x].cnt−− ,并移动到根节点。
若为 x x x 的节点的 c n t = 1 cnt=1 cnt=1 则删除 n o w now now 与 n x t nxt nxt 的联系即可。
最后重新计算以 n x t , p r e nxt,pre nxt,pre 为根的子树的大小即可。
值为 x x x 的节点一定是后继的左儿子。
若此时值为 x x x 的节点的左子树不为空则值为 x x x 的节点的左节点的值大于前驱并小于 x x x 。
那么值为 x x x 的节点的左节点为前驱与前驱在跟节点处矛盾,故为 x x x 的节点的左子树为空。
右子树同理。
所以值为 x x x 的节点的左右子树为空。
inline void splay_delete(int x)
{
int pre=find_pre_nxt(x,0);
int nxt=find_pre_nxt(x,1);
splay_to(pre,0);
splay_to(nxt,pre);
int now=splay[nxt].son[0];
if(splay[now].cnt>1)
{
splay[now].cnt--;
splay_to(now,0);
}
else
{
splay[nxt].son[0]=0;
}
get_size(nxt);
get_size(pre);
}
s p l a y − f i n d − n u m b e r splay - find -number splay−find−number
查找排名为 x x x 的节点的值,递归求解,最后将节点移动到根节点。
inline int find_number(int now,int k)
{
if(k<=splay[lson(now)].size)
return find_number(splay[now].son[0],k);
else
if(k>splay[lson(now)].size+splay[now].cnt)
return find_number(rson(now),k-splay[lson(now)].size-splay[now].cnt);
else
{
int dd=splay[now].k;
splay_to(now,0);
return dd;
}
}
总代码(P6136)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f3f3f3f
namespace Splays
{
#define lson(x) splay[x].son[0]
#define rson(x) splay[x].son[1]
const int N=2e6+1;
struct Spaly
{
int k,p,son[2],size,cnt;
}splay[N];
int tot,root,n,m,ans,last;
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-')f=-f;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
inline void write(int x)
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
}
inline void get_size(int x)
{
splay[x].size = splay[lson(x)].size + splay[rson(x)].size + splay[x].cnt;
}
inline void rotate(int x)
{
int y=splay[x].p;
int z=splay[y].p;
int yson=(lson(y)==x?0:1);
int zson=(lson(z)==y?0:1);
splay[z].son[zson]=x;
splay[x].p=z;
splay[y].son[yson]=splay[x].son[yson^1];
splay[splay[x].son[yson^1]].p=y;
splay[x].son[yson^1]=y;
splay[y].p=x;
get_size(y);
get_size(x);
}
inline void splay_to(int x,int TO)
{
while(splay[x].p!=TO)
{
int y=splay[x].p;
int z=splay[y].p;
if(z!=TO)
rotate((lson(z)==y&&lson(y)==x)?y:x);
rotate(x);
}
if(TO==0)root=x;
}
inline void splay_insert(int x)
{
int now=root,father=0;
while(now!=0&&splay[now].k!=x)
{
father=now;
now=splay[now].son[splay[now].k<x];
}
if(now)
{
splay[now].cnt++;
}
else
{
now=++tot;
if(father)
splay[father].son[splay[father].k<x]=now;
splay[now].p=father;
splay[now].k=x;
splay[now].son[0]=splay[now].son[1]=0;
splay[now].size=splay[now].cnt=1;
}
splay_to(now,0);
}
inline void splay_find_move_find_rank(int x)
{
int now=root;
if(root==0)return;
while(splay[now].son[splay[now].k<x]!=0&&splay[now].k!=x)
{
now=splay[now].son[splay[now].k<x];
}
splay_to(now,0);
}
inline int find_pre_nxt(int x,int op)
{
splay_find_move_find_rank(x);
int now=root;
if(splay[now].k<x&&op==0||splay[now].k>x&&op==1)
return now;
now=splay[now].son[op];
while(splay[now].son[op^1]!=0)
{
now=splay[now].son[op^1];
}
return now;
}
inline void splay_delete(int x)
{
int pre=find_pre_nxt(x,0);
int nxt=find_pre_nxt(x,1);
splay_to(pre,0);
splay_to(nxt,pre);
int now=splay[nxt].son[0];
if(splay[now].cnt>1)
{
splay[now].cnt--;
splay_to(now,0);
}
else
{
splay[nxt].son[0]=0;
}
get_size(nxt);
get_size(pre);
}
inline int find_number(int now,int k)
{
if(k<=splay[lson(now)].size)
return find_number(splay[now].son[0],k);
else
if(k>splay[lson(now)].size+splay[now].cnt)
return find_number(rson(now),k-splay[lson(now)].size-splay[now].cnt);
else
{
int dd=splay[now].k;
splay_to(now,0);
return dd;
}
}
void main()
{
splay_insert(-inf);
splay_insert(inf);
n=read();
m=read();
int op,x;
for(int i=1; i<=n; i++)
{
x=read();
splay_insert(x);
}
for(int i=1; i<=m; i++)
{
op=read();
x=read();
x^=last;
if(op==1)splay_insert(x);
if(op==2)splay_delete(x);
if(op==3)
{
splay_find_move_find_rank(x);
last=splay[splay[root].son[0]].size+(splay[root].k<x?splay[root].cnt:0);
}
if(op==4)
{
last=find_number(root,1+x);
}
if(op==5)
{
last=splay[find_pre_nxt(x,0)].k;
}
if(op==6)
{
last=splay[find_pre_nxt(x,1)].k;
}
if(op!=1&&op!=2)
{
ans^=last;
}
}
write(ans);
return;
}
}
signed main()
{
Splays::main();
}