0X?F 前言
（真的轻喷，语言不要太过激进，想喷的别在评论区喷，私信喷我。）
感谢 AgOH 大佬用视频教会了我 \text{Splay}，所以可能很多地方跟 AgOH 写的一样（虽然码风基本一样）。
写的可能不好，轻喷。如果旋转看不懂可以看这里：Link。
0XFF 什么是 \text{Splay}？
## 0X1F 粗讲 $\text{Splay}
- 每次操作总要把节点**弄**到根节点，然后操作。
至于“弄”的意思，就看下面了。
## 0X2F 旋转
这是 $\text{Splay}$ 最重要的操作，也是必须要背下来的。
旋转分为两种：
- 单旋
- 双旋
单旋又分两种：
- 左旋（$zag$）
- 右旋（$zig$）
双旋也分为两种：
- 同构调整
- 异构调整
其实很简单，接着往下看吧：
### 0X2F - 1 左旋（$zag$）
记住一句口诀：左旋拎右左挂右（本口诀选自 AgOH 大佬的视频）。
看看下面的图就知道了：
可以看出，旋转其实就是相当于在中序遍历不变的情况下换了一种树的结构。
代码：
```cpp
void zag(int &node){
int r = spl[node].r; //好好理解一下
spl[node].r = spl[r].l;
spl[r].l = node;
node = r;
update(spl[node].l); //这里是更新节点子树内大小
update(node);
}
```
### 0X2F - 2 右旋（$zig$）
还有一句口诀：右旋拎左右挂左（还是选自 AgOH 大佬）。
还是一样的图：
应该很简单：
```cpp
void zig(int &node){
int l = spl[node].l;
spl[node].l = spl[l].r;
spl[l].r = node;
node = l;
update(spl[node].r);
update(node);
}
```
### 0X2F - 3 同构调整
分两种情况讨论。
第一种：
第二种：
我们的目标是把 $3$ 号节点旋转到最顶上，那么该怎么操作呢？
第一种，对 $1$ 进行 $zig$，再对 $2$ 进行 $zig$，就可以了！
第二种，对 $1$ 进行 $zag$，再对 $2$ 进行 $zag$，就可以了！
~~是不是很简单。~~
### 0X2F - 4 异构调整
也分两种情况讨论。
第一种：
第二种：
目标还是一样。
第一种，对 $2$ 进行 $zag$，再对 $1$ 进行 $zig$，就可以了！
第二种，对 $2$ 进行 $zig$，再对 $1$ 进行 $zag$，就可以了！
~~是不是也很简单~~
以上的四种旋转都是基本功，务必要记好。
## 0X3F $\text{Splay}$ 的定义与基本操作
$\text{Splay}$ 定义如下：
```cpp
struct Node{
int ch[2];
int fa, val, size; //fa 表示父亲，val 表示值，size 表示子树大小
}spl[N];
```
这里的左右儿子之所以从 $l, r$ 变成了 $ch_{0/1}$，是因为后面的简化版代码做准备，$ch_0$ 表示左儿子，$ch_1$ 表示右儿子。
还有就是更新子树大小，这个也很容易：
```cpp
void update(int node){
spl[node].size = spl[spl[node].ch[0]].size + spl[spl[node].ch[1]].size + 1;
}
```
还有初始化节点信息：
```cpp
void newnode(int &node, int fa, int val){
spl[node = ++cnt].val = val;
spl[cnt].fa = fa;
spl[cnt].size = 1;
}
```
这里因为没有返回值所以要用引用。
## 0X4F $\text{Splay}$ 的重要操作
一共有 $4$ 个：
- $ident
0X4F - 1 ident
确定 x 是父亲的哪个儿子。
代码：
bool ident(int x, int fa){
return spl[fa].ch[1] == x; //左儿子 0，右儿子 1
}
0X4F - 2 connect
建立父子关系。
代码：
void connect(int x, int fa, int k){ //x 是 fa 的 ch[k]
spl[fa].ch[k] = x;
spl[x].fa = fa;
}
这个也很简单，但在后面很重要。
0X4F - 3 rotate
我们发现 zag 和 zig 写起来忒长了吧，还要分类，谁愿意去写啊！ 于是，我们来写简化版，能自动适应左右旋转。
我们发现其实左旋和右旋就是一个异或的关系，所以左右旋转都可以根据儿子的左右关系来确定左右旋转，而左右旋转一共要更改 3 个父子关系，所以，简单的代码来了：
void rotate(int x){
int fa = spl[x].fa, ffa = spl[fa].fa, k = ident(x, fa);
connect(spl[x].ch[k ^ 1], fa, k);
connect(x, ffa, ident(fa, ffa));
connect(fa, x, k ^ 1);
update(fa);
update(x);
}
这里可以自己动手画画图，由于版面原因不再过多阐述。
0X4F - 4 splaying
我们可以对于双旋找规律，我们知道了下面两个规律（并不是按照双旋的普通旋转定律来的）：
- 无论是哪种旋转（包括四种旋转），总是要旋转 $x$。
- 如果父亲的 $ident$ 和父亲的父亲的 $ident$ 相同，旋转 $x$，否则，旋转父亲。
所以，来看看简单的代码吧：
```cpp
void splaying(int x, int top){ //为什么需要用 top 的儿子，因为我们要判断最后一步是否是左右旋转
if(!top){
root = x;
}
for(; spl[x].fa != top; ){
int fa = spl[x].fa, ffa = spl[fa].fa;
if(ffa != top){ //如果是双旋
ident(fa, ffa) ^ ident(x, fa) ? rotate(x) : rotate(fa);
}
rotate(x); //反正最后都要旋 x
}
}
```
显然代码很短。
## 0X5F 一些不那么重要的操作
注意：$\text{Splay}$ 不对重复值节点进行操作是没有问题的。
### 0X5F - 1 插入（$\text{insert}$）
显然跟二叉搜索树无异，只不过需要把节点伸展到根节点。
代码：
```cpp
void insert(int &node, int val, int fa){
if(!node){
newnode(node, fa, val);
splaying(node, 0); //0 表示伸展到根节点
}
else if(val < spl[node].val){
insert(spl[node].ch[0], val, node);
}
else{
insert(spl[node].ch[1], val, node);
}
}
```
### 0X5F - 2 删除（$\text{del}$）
首先找到要删除的节点，伸展到根节点，分以下情况讨论：
- 如果当前节点无后继，也就是右子树为空，那么直接把根节点变成根节点的左儿子即可。
- 如果有后继，让后继伸展到根节点的右儿子那里，然后将后继的左儿子指向根节点的左儿子，再把 $root$ 更为后继即可。
很简单吧，代码来喽：
```cpp
void delnode(int x){ //删除节点
splaying(x, 0);
if(spl[x].ch[1]){
int p = spl[x].ch[1];
while(spl[p].ch[0]){ //找到后继
p = spl[p].ch[0];
}
splaying(p, x); //伸展上去
connect(spl[x].ch[0], p, 0); //建立关系
root = p;
spl[p].fa = 0; //清空
update(root);
}
else{
root = spl[x].ch[0];
spl[root].fa = 0;
}
}
void del(int &node, int val){ //寻找节点，这里引用不引用无所谓
if(val == spl[node].val){
delnode(node);
}
else if(val < spl[node].val){
del(spl[node].ch[0], val);
}
else{
del(spl[node].ch[1], val);
}
}
```
按照思路打就对了。
### 0X5F - 3 查询数的排名（$\text{rank}$）
这个很简单，但是一定一定找到节点后要伸展，不然会 T 的很惨。
代码：
```cpp
int _rank(int val){
int node = root, rk = 1, pre = 0;
while(node){
if(val <= spl[node].val){
pre = node;
node = spl[node].ch[0];
}
else{
rk += spl[spl[node].ch[0]].size + 1;
node = spl[node].ch[1];
}
}
if(pre){ //并不是没有
splaying(pre, 0);
}
return rk;
}
```
### 0X5F - 4 查询排名的数（$\text{query}$）
这个也很简单，前驱后继都是用这个完成的：
```cpp
int query(int rk){ //真 简单
int node = root;
while(node){
if(spl[spl[node].ch[0]].size + 1 == rk){
splaying(node, 0);
break;
}
else if(spl[spl[node].ch[0]].size >= rk){
node = spl[node].ch[0];
}
else{
rk -= spl[spl[node].ch[0]].size + 1;
node = spl[node].ch[1];
}
}
return spl[node].val;
}
```
## 0X6F 代码
板题为普通平衡树，代码：
```cpp
#include<bits/stdc++.h>
#define endl '\n';
using namespace std;
const int N = 1e5 + 5;
int n;
struct Node{
int ch[2];
int fa, val, size;
}spl[N];
int cnt, root;
void update(int node){
spl[node].size = spl[spl[node].ch[0]].size + spl[spl[node].ch[1]].size + 1;
}
bool ident(int x, int fa){
return spl[fa].ch[1] == x;
}
void connect(int x, int fa, int k){
spl[fa].ch[k] = x;
spl[x].fa = fa;
}
void rotate(int x){
int fa = spl[x].fa, ffa = spl[fa].fa, k = ident(x, fa);
connect(spl[x].ch[k ^ 1], fa, k);
connect(x, ffa, ident(fa, ffa));
connect(fa, x, k ^ 1);
update(fa);
update(x);
}
void splaying(int x, int top){
if(!top){
root = x;
}
for(; spl[x].fa != top; ){
int fa = spl[x].fa, ffa = spl[fa].fa;
if(ffa != top){
ident(fa, ffa) ^ ident(x, fa) ? rotate(x) : rotate(fa);
}
rotate(x);
}
}
void newnode(int &node, int fa, int val){
spl[node = ++cnt].val = val;
spl[cnt].fa = fa;
spl[cnt].size = 1;
}
void delnode(int x){
splaying(x, 0);
if(spl[x].ch[1]){
int p = spl[x].ch[1];
while(spl[p].ch[0]){
p = spl[p].ch[0];
}
splaying(p, x);
connect(spl[x].ch[0], p, 0);
root = p;
spl[p].fa = 0;
update(root);
}
else{
root = spl[x].ch[0];
spl[root].fa = 0;
}
}
void insert(int &node, int val, int fa){
if(!node){
newnode(node, fa, val);
splaying(node, 0);
}
else if(val < spl[node].val){
insert(spl[node].ch[0], val, node);
}
else{
insert(spl[node].ch[1], val, node);
}
}
void del(int &node, int val){
if(val == spl[node].val){
delnode(node);
}
else if(val < spl[node].val){
del(spl[node].ch[0], val);
}
else{
del(spl[node].ch[1], val);
}
}
int _rank(int val){
int node = root, rk = 1, pre = 0;
while(node){
if(val <= spl[node].val){
pre = node;
node = spl[node].ch[0];
}
else{
rk += spl[spl[node].ch[0]].size + 1;
node = spl[node].ch[1];
}
}
if(pre){
splaying(pre, 0);
}
return rk;
}
int query(int rk){
int node = root;
while(node){
if(spl[spl[node].ch[0]].size + 1 == rk){
splaying(node, 0);
break;
}
else if(spl[spl[node].ch[0]].size >= rk){
node = spl[node].ch[0];
}
else{
rk -= spl[spl[node].ch[0]].size + 1;
node = spl[node].ch[1];
}
}
return spl[node].val;
}
void Solve(){
cin >> n;
while(n--){
int op;
cin >> op;
if(op == 1){
int x;
cin >> x;
insert(root, x, 0);
}
else if(op == 2){
int x;
cin >> x;
del(root, x);
}
else if(op == 3){
int x;
cin >> x;
cout << _rank(x) << endl;
}
else if(op == 4){
int x;
cin >> x;
cout << query(x) << endl;
}
else if(op == 5){
int x;
cin >> x;
cout << query(_rank(x) - 1) << endl;
}
else{
int x;
cin >> x;
cout << query(_rank(x + 1)) << endl;
}
}
}
signed main(){
Solve();
return 0;
}
```
由于前面有注释，这里就不给了。
## 0X7F 时间复杂度证明
Tarjan 的伟大不在于发明了 $\text{Splay}$，而是证明出了其复杂度，至于复杂度证明可以看：[证明 $\text{Splay}$ 复杂度](https://www.cnblogs.com/klauralee/p/10926342.html)。
## 0X8F 为何不能可持久化
并不是因为旋转，请品一品以下 lxl 的对话：
## 0X8F 最后的感谢
感谢 AgOH 大佬让我学会了 $\text{Splay}$！！！
AgOH 大佬视频：[点这里](https://www.bilibili.com/video/BV1wt411u7xL?p=1&vd_source=4da59a98a285f9ad0628aed4d8dd86ee)。