前言
想了想还是写吧。
前置芝士
旋转和 BST。
正文
现发表一下个人的看法，splay 其实就是一种优雅的暴力的 BST，通过把一个节点不断旋转到根来维护其 BST 的性质。
旋转
因为你更改或插入时要更改从本节点到根节点路径上所有点的大小，所以就需要用到旋转了，也就是把本节点旋转到根。
具体的，对于一个节点，如果其性质和他的父亲的性质相同，就旋转他的父亲，反之旋转他自己，最后旋转他自己。
重复以上步骤直到根节点即可。
对于一个节点的性质为其属于其父亲的左子树或右子树。
int get(int x) { return x==ch[fa[x]][1]; }
void rotate(int x) {
int y=fa[x];
int z=fa[y],tmp=get(x);
ch[y][tmp]=ch[x][tmp^1];
if (ch[x][tmp^1]) fa[ch[x][tmp^1]]=y;
ch[x][tmp^1]=y;
fa[y]=x;
fa[x]=z;
if (z) ch[z][y==ch[z][1]]=x;
upd(y);
upd(x);
}
void splay(int x) {
for (int i=fa[x];i=fa[x],i;rotate(x))
if (fa[i]) rotate(get(x)==get(i)?i:x);
rt=x;
}
插入
没什么好说的，对于当前节点如果插入值比它大，往右子树搜，反之往左子树搜，再分几种情况：
-
根节点为空，建一个新节点作为根节点。
-
树中存在这个数，搜到此节点，更新，然后旋转到根。
-
树中不存在这个数，一直搜到叶子节点，建立一个属于他自己的新节点，更新，旋转到根。
void ins(int x) {
if (!rt) {
rt=++cnt;
val[cnt]=x;
num[cnt]++;
upd(rt);
return;
}
int y=rt,f=0;
while (1) {
if (x==val[y]) {
num[y]++;
upd(y);
upd(f);
splay(y);
break;
}
f=y;
y=ch[y][x>val[y]];
if (!y) {
val[++cnt]=x;
num[cnt]++;
fa[cnt]=f;
ch[f][val[cnt]>val[f]]=cnt;
upd(cnt);
upd(f);
splay(cnt);
break;
}
}
}
查询排名
首先不保证它在树中，所以要先插入，最后删掉即可。
在树中搜索，同样的，对于当前节点如果插入值比它小，往左子树搜，反之让答案加上左子树的大小，如果当前节点的值是我们所求的，就返回答案+1并旋转到根，否则再加上当前节点的个数并往右子树搜。
int rk(int x) {
int res=0,y=rt;
while (1) {
if (x<val[y]) {
y=ch[y][0];
} else {
res+=siz[ch[y][0]];
if (x==val[y]) {
splay(y);
return res+1;
}
res+=num[y];
y=ch[y][1];
}
}
}
查询给定名次的值
在树中搜索，同样的，如果当前节点的左子树大小大于等于排名，往左子树搜，反之让排名减去左子树的大小和当前节点的个数，如果排名此时小于等于 \(0\)，就返回当前节点并旋转到根，否则往右子树搜。
int kth(int x) {
int y=rt;
while (1) {
if (ch[y][0] and x<=siz[ch[y][0]]) {
y=ch[y][0];
} else {
x-=(siz[ch[y][0]]+num[y]);
if (x<=0) {
splay(y);
return val[y];
}
y=ch[y][1];
}
}
}
前驱和后继
搜前驱就去找其左子树中的最大值，后继就是找其右子树中的最小值。
int pre(int x) {
int y=ch[x][0];
if (!y) return y;
while (ch[y][1]) y=ch[y][1];
splay(y);
return y;
}
int nxt(int x) {
int y=ch[x][1];
if (!y) return y;
while (ch[y][0]) y=ch[y][0];
splay(y);
return y;
}
删除
分五种情况：
-
当前节点个数大于 \(1\)，个数减一，更新，旋转到根。
-
左右子树皆为空（即为根节点），删除本节点，
rt=0。 -
左子树有，右子树没有，删除本节点，
rt=t[rt].ch[0]。 -
左子树没有，右子树有，删除本节点，
rt=t[rt].ch[1]。 -
左右子树皆有，找到本节点的前驱，把前驱的右子树改为本节点的右子树，本节点的右子树的父亲改为前驱，删除本节点并更新。
void clear(int x) {siz[x]=ch[x][0]=ch[x][1]=fa[x]=num[x]=val[x]=0;}
void del(int x) {
rk(x);
if (num[rt]>1) {
num[rt]--;
upd(rt);
} else if (!ch[rt][1] and !ch[rt][0]){
clear(rt);
rt=0;
} else if (!ch[rt][1] and ch[rt][0]) {
int tmp=rt;
rt=ch[rt][0];
fa[rt]=0;
clear(tmp);
} else if (ch[rt][1] and !ch[rt][0]) {
int tmp=rt;
rt=ch[rt][1];
fa[rt]=0;
clear(tmp);
} else {
int tmp=rt,x=pre(rt);
fa[ch[tmp][1]]=x;
ch[x][1]=ch[tmp][1];
clear(tmp);
upd(rt);
}
}
更新
没啥好说的。
void upd(int x) { siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+num[x]; }
习题
P3369 【模板】普通平衡树
把板子贴上去即可
P3391 【模板】文艺平衡树
就是把 splay 当区间树用，再加上一个 \(lazytag\)，对于每一个区间 \([l,r]\)，把 \(l-1\) 旋转到根，再把 \(r+1\) 旋转到根的右子树，再对 \(r+1\) 的左子树打上 \(lazytag\) 即可。
旋转部分代码：
void splay(int x,int k) {
for (int f=t[x].fa;f=t[x].fa,f!=k;rotate(x))
if (t[f].fa!=k) rotate(get(x)==get(f)?f:x);
if (!k) rt=x;
}
P2596 [ZJOI2006]书架
把初始时每本书上面书的本数作为初始权值插入，并定义 \(loc_i\) 为第 \(i\) 本书在树中的编号。
-
对于操作
Top，把本节点旋转到根，找到前驱，将右子树接到前驱的右子树出，更新旋转到根。 -
对于操作
Bottom，同上。 -
对于操作
Insert，因为 \(t \in \{-1,0,1\}\)，所以当 \(t\) 为 \(0\) 时，直接continue，那么当 \(t=-1\) 时，找到前驱，交换权值和 \(loc\)，否则反之。 -
对于操作
Ask，将 \(s\) 旋转到根，输出左子树大小。 -
对于操作
Query，就是求排名。
#include <iostream>
#include <string>
#include <cstdio>
#define INF 100000
using namespace std;
int n,m;
namespace Splay {
struct Node {
int val,num,siz,fa,ch[2];
}t[1000001];
int rt,cnt,loc[1000001];
void upd(int x) { t[x].siz=t[t[x].ch[0]].siz+t[t[x].ch[1]].siz+t[x].num; }
int get(int x) { return x==t[t[x].fa].ch[1]; }
void rotate(int x) {
int y=t[x].fa,z=t[y].fa,tmp=get(x);
t[y].ch[tmp]=t[x].ch[tmp^1];
if (t[x].ch[tmp^1]) t[t[x].ch[tmp^1]].fa=y;
t[x].ch[tmp^1]=y;
t[y].fa=x;
t[x].fa=z;
if (z) t[z].ch[y==t[z].ch[1]]=x;
upd(y);
upd(x);
}
void splay(int x,int goal) {
for (int f=t[x].fa;f=t[x].fa,f!=goal;rotate(x))
if (t[f].fa!=goal) rotate(get(f)==get(x)?f:x);
loc[t[x].val]=x;
if (!goal) rt=x;
}
int find_max() {
int y=t[rt].ch[1];
if (!y) return rt;
while (t[y].ch[1]) y=t[y].ch[1];
splay(y,0);
return y;
}
int find_min() {
int y=t[rt].ch[0];
if (!y) return rt;
while (t[y].ch[0]) y=t[y].ch[0];
splay(y,0);
return y;
}
int rk(int x) {
splay(x,0);
return t[t[x].ch[0]].siz;
}
int kth(int x) {
int y=rt;
while (1) {
if (x<=t[t[y].ch[0]].siz) y=t[y].ch[0];
else {
x-=t[y].num+t[t[y].ch[0]].siz;
if (x<=0) {
splay(y,0);
return y;
}
y=t[y].ch[1];
}
}
}
int pre(int x,int k) {
int y=t[x].ch[k];
if (!y) return y;
while (t[y].ch[k^1]) y=t[y].ch[k^1];
splay(y,0);
return y;
}
void ins(int x) {
if (!rt) {
t[rt=++cnt].val=x;
t[cnt].num++;
loc[x]=cnt;
upd(cnt);
return;
}
find_max();
t[++cnt].val=x;
t[cnt].num++;
t[cnt].fa=rt;
loc[x]=cnt;
t[rt].ch[1]=cnt;
upd(cnt);
upd(rt);
splay(cnt,0);
}
}
using namespace Splay;
void work(int x) {
if (!x) return;
work(t[x].ch[0]);
printf("%d ",t[x].val);
work(t[x].ch[1]);
}
void work1(int x) {
if (!x) return;
work1(t[x].ch[0]);
printf("%d %d ",loc[t[x].val],x);
work1(t[x].ch[1]);
}
int main() {
scanf("%d%d",&n,&m);
for (int i=1,x;i<=n;i++) {
scanf("%d",&x);
ins(x);
}
string s;
for (int i=1,x,tt;i<=m;i++) {
cin>>s;
scanf("%d",&x);
if (s=="Top") {
splay(loc[x],0);
if (!t[rt].ch[0]) continue;
if (!t[rt].ch[1]) {
t[rt].ch[1]=t[rt].ch[0];
t[rt].ch[0]=0;
continue;
}
int y=t[rt].ch[1];
while (t[y].ch[0]) y=t[y].ch[0];
t[y].ch[0]=t[rt].ch[0];
if (t[y].ch[0]) t[t[y].ch[0]].fa=y;
t[rt].ch[0]=0;
upd(y);
splay(t[y].ch[0],0);
} else if (s=="Bottom") {
splay(loc[x],0);
if (!t[rt].ch[1]) continue;
if (!t[rt].ch[0]) {
t[rt].ch[0]=t[rt].ch[1];
t[rt].ch[1]=0;
continue;
}
int y=t[rt].ch[0];
while (t[y].ch[1]) y=t[y].ch[1];
t[y].ch[1]=t[rt].ch[1];
if (t[y].ch[1]) t[t[y].ch[1]].fa=y;
t[rt].ch[1]=0;
upd(y);
splay(t[y].ch[1],0);
} else if (s=="Insert") {
splay(loc[x],0);
scanf("%d",&tt);
if (!tt) continue;
int t1=pre(loc[x],(tt==-1?0:1));
if (!t1) continue;
swap(t[loc[x]].val,t[rt].val);
swap(loc[x],loc[t[loc[x]].val]);
} else if (s=="Ask") {
printf("%d\n",rk(loc[x]));
} else if (s=="Query") {
printf("%d\n",t[kth(x)].val);
}
// work(rt);
// printf("\n");
}
return 0;
}