今天真是有紀(jì)念意義啊……
以前試著捉了N遍的cashier今天竟然AC了，本沙茶終于掌握了平衡樹！！！
【Splay Tree及其實(shí)現(xiàn)】
<1>結(jié)點(diǎn)記錄的信息：
一般情況下Splay Tree是用線性存儲(chǔ)器（結(jié)構(gòu)數(shù)組）來(lái)存儲(chǔ)的，可以避免在Linux下的指針異常問(wèn)題。
這樣對(duì)于某個(gè)結(jié)點(diǎn)，至少要記錄以下的域：值（又叫關(guān)鍵字）、左子結(jié)點(diǎn)的下標(biāo)、右子結(jié)點(diǎn)的下標(biāo)、父結(jié)點(diǎn)下標(biāo)、子樹大小（就是以這個(gè)結(jié)點(diǎn)為根的子樹中結(jié)點(diǎn)的總數(shù)）以及左右標(biāo)志（為一個(gè)bool值，表示該結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子結(jié)點(diǎn)還是右子結(jié)點(diǎn)），所要記錄的其它域根據(jù)題目要求而定。另外還有一個(gè)域：重復(fù)次數(shù)mul，就是整棵樹中與這個(gè)結(jié)點(diǎn)值相同的結(jié)點(diǎn)總數(shù)（關(guān)于這個(gè)域的作用將在下一篇里面總結(jié)）。
struct node {
int v, c[2], p, sz, mul;
bool d;
} T[MAXN];
以上v為值、c[0]和c[1]表示左右子結(jié)點(diǎn)下標(biāo)、p表示父結(jié)點(diǎn)下標(biāo)、sz表示子樹大小、mul表示重復(fù)次數(shù)、d表示左右標(biāo)志。
另外，為了防止越界，將T[0]預(yù)留出來(lái)作為哨兵結(jié)點(diǎn)。在樹中，根結(jié)點(diǎn)的p值和葉結(jié)點(diǎn)的c值均為0。這個(gè)T[0]的sz值必須是0，其余的域無(wú)意義。
<2>旋轉(zhuǎn)操作和伸展操作：
右旋（ZIG）：如果某個(gè)非根結(jié)點(diǎn)X是其父結(jié)點(diǎn)Y的左子結(jié)點(diǎn)，則可以通過(guò)右旋操作將X旋轉(zhuǎn)到Y(jié)的位置，即：先將Y的左子結(jié)點(diǎn)設(shè)為X的右子結(jié)點(diǎn)，再將X的右子結(jié)點(diǎn)設(shè)為Y；
左旋（ZAG）：如果某個(gè)非根結(jié)點(diǎn)X是其父結(jié)點(diǎn)Y的右子結(jié)點(diǎn)，則可以通過(guò)左旋操作將X旋轉(zhuǎn)到Y(jié)的位置，即：先將Y的右子結(jié)點(diǎn)設(shè)為X的左子結(jié)點(diǎn)，再將X的左子結(jié)點(diǎn)設(shè)為Y；
ZIG和ZAG操作可以合并，稱為rot，代碼如下：
void rot(int x)
{
int y = T[x].p, d = T[x].d;
if (y == root) {root = x; T[root].p = 0;} else sc(T[y].p, x, T[y].d);
sc(y, T[x].c[!d], d); sc(x, y, !d); upd(y);
}
其中的sc是set child的縮寫，sc(_p, _c, _d)表示將T[_p]的_d子結(jié)點(diǎn)（0：左；1：右。下同）置為_c，代碼如下（_c也可以是0，表示刪除T[_p]對(duì)應(yīng)的子結(jié)點(diǎn)）：
void sc(int _p, int _c, bool _d)
{
T[_p].c[_d] = _c; T[_c].p = _p; T[_c].d = _d;
}
其中的upd是update的縮寫，upd(x)表示當(dāng)x的子結(jié)點(diǎn)改變時(shí)，更新x的一些可維護(hù)域（這里只有sz值，有的題目比如NOI2005 sequence里面有其它的可維護(hù)域）：
void upd(int x)
{
T[x].sz = T[T[x].c[0]].sz + T[T[x].c[1]].sz + T[x].mul;
}
然后就是Splay Tree的核心操作——伸展操作(Splay)：
Splay(x, r)表示將x伸展到r的子結(jié)點(diǎn)處，若r=0，則表示伸展到根（因?yàn)楦母附Y(jié)點(diǎn)為T[0]）。過(guò)程如下：
（1）設(shè)x的父結(jié)點(diǎn)為p。若p的父結(jié)點(diǎn)即是r，則rot(x)；
（2）若p的父結(jié)點(diǎn)不是r且T[x].d=T[p].d，則先rot(p)再rot(x)；
（3）若p的父結(jié)點(diǎn)不是r且T[x].d!=T[p].d，則兩次rot(x)；
（4）重復(fù)以上過(guò)程直到x的父結(jié)點(diǎn)為r；
void splay(int x, int r)
{
int p; while ((p = T[x].p) != r) if (T[p].p == r) rot(x); else if (T[x].d == T[p].d) {rot(p); rot(x);} else {rot(x); rot(x);} upd(x);
}
這里有一個(gè)問(wèn)題：為什么在旋轉(zhuǎn)操作中只更新y不更新x，而在伸展操作的最后則要更新x？這個(gè)在JZP神犇的論文中有解釋：因?yàn)樵谛D(zhuǎn)過(guò)程中，x的子結(jié)點(diǎn)一直在改變，故過(guò)早地跟新x沒有意義。
<3>查找操作：
下面開始進(jìn)入正式操作了。
首先是查找。find(x)表示在樹中找值為x的結(jié)點(diǎn)，若找到返回其下標(biāo)，若找不到返回0。這個(gè)應(yīng)該是很容易實(shí)現(xiàn)的。
int find(int x)
{
int i = x, v0; while (i) {v0 = T[i].v; if (v0 == x) break; else i = T[i].c[v0 > x];} return i;
}
<4>插入操作：
ins(_v)表示在樹中插入一個(gè)值為_v的結(jié)點(diǎn)。由于樹是否為空的問(wèn)題以及mul的引入，插入操作有三種可能結(jié)果：
（1）樹為空（根結(jié)點(diǎn)為0）：此時(shí)將插入一個(gè)新的結(jié)點(diǎn)，值為_v，初始sz、mul值均為1，并將其作為根結(jié)點(diǎn)；
（2）樹非空且值為_v的結(jié)點(diǎn)在樹中不存在：此時(shí)將插入一個(gè)新的結(jié)點(diǎn)，值為_v，初始sz、mul值均為1；
（3）樹非空且值為_v的結(jié)點(diǎn)在樹中已存在：此時(shí)會(huì)將樹中這個(gè)值為_v的結(jié)點(diǎn)的mul值加1；
void ins(int _v)
{
if (!root) {T[++n].v = _v; T[n].c[0] = T[n].c[1] = T[n].p = 0; T[n].sz = T[n].mul = 1; root = n; return;}
int i = root, j;
while (1) {
T[i].sz++;
if (T[i].v == _v) {T[i].mul++; splay(i, 0); return;}
j = T[i].c[_v > T[i].v];
if (!j) break; else i = j;
}
T[++n].v = _v; T[n].c[0] = T[n].c[1] = 0; T[n].sz = T[n].mul = 1; sc(i, n, _v > T[i].v); splay(n, 0);
}
<5>刪除操作：
del(x)表示將下標(biāo)為x的結(jié)點(diǎn)刪除。
除了一般的二叉查找樹的刪除方法外，Splay Tree還有一種刪除方式：先找到x的前趨P和x的后繼S（具體操作見<6>），并將P伸展到根，S伸展到P的右子結(jié)點(diǎn)處，這樣S的左子樹中只有一個(gè)結(jié)點(diǎn)，就是x，然后再將S的左子結(jié)點(diǎn)置為0即可。需要注意的是幾種特殊情況：
（1）x無(wú)前趨或無(wú)后繼：此時(shí)將x伸展到根后，x只有一棵子樹，直接將根結(jié)點(diǎn)設(shè)為x的那個(gè)子結(jié)點(diǎn)即可；
（2）x既無(wú)前趨也無(wú)后繼：此時(shí)x就是樹中的唯一一個(gè)結(jié)點(diǎn)，將根結(jié)點(diǎn)設(shè)為0即可；
（3）T[x].mul>1，直接將T[x].mul值減1（與插入類似）；
void del(int x)
{
if (T[x].mul > 1) T[x].mul--; else {
splay(x, 0);
int y = succ(), y2 = pred();
if (!y) {root = T[x].c[0]; T[root].p = 0;} else if (!y2) {root = T[x].c[1]; T[root].p = 0;} else {
splay(y2, 0); splay(y, root);
T[x].p = 0; T[y].c[T[x].d] = 0; upd(y); upd(root);
}
}
}
<6>找前趨和后繼：
pred(x)和succ(x)：分別求出x的前趨和后繼（x的前趨表示樹中值小于x的最大的結(jié)點(diǎn)；x的后繼表示樹中值大于x的最小的結(jié)點(diǎn)），并返回它們的下標(biāo)，若不存在返回0。
先將x伸展到根，然后x的左子結(jié)點(diǎn)的右鏈上的最后一個(gè)結(jié)點(diǎn)就是x的前趨，x的右子結(jié)點(diǎn)的左鏈上的最后一個(gè)結(jié)點(diǎn)就是x的后繼。
int pred()
{
int i = T[root].c[0], j;
if (!i) return 0;
while (j = T[i].c[1]) i = j;
return i;
}
int succ()
{
int i = T[root].c[1], j;
if (!i) return 0;
while (j = T[i].c[0]) i = j;
return i;
}
注意，這里的pred和succ是求根結(jié)點(diǎn)的前趨和后繼，因此在調(diào)用pred或succ前必須保證結(jié)點(diǎn)x已經(jīng)被伸展到了根的位置。
前趨和后繼還有另一種定義方式：x的前趨表示樹中值不大于x的最大的結(jié)點(diǎn)，x的后繼表示樹中值不小于x的最小的結(jié)點(diǎn)，此時(shí)只需在pred和succ函數(shù)的開頭分別加入if (T[root].mul > 1) return root;即可。
<7>找第K小以及找指定結(jié)點(diǎn)是第幾小：
找第K小以及找指定結(jié)點(diǎn)是第幾小的操作是平衡樹的特有操作。Splay Tree找第K小的操作與其它平衡樹相同。
int Find_Kth(int K)
{
int i = root, s0, m0;
while (1) {
s0 = T[T[i].c[0]].sz; m0 = T[i].mul;
if (K <= s0) i = T[i].c[0]; else if (K <= s0 + m0) return T[i].v; else {K -= s0 + m0; i = T[i].c[1];}
}
}
而Splay Tree找指定結(jié)點(diǎn)是第幾小的操作則是特有的：將這個(gè)結(jié)點(diǎn)伸展到根，則其(左子樹大小+1)即為結(jié)果。
int rank(int x)
{
splay(x, 0); return T[T[x].c[0]].sz + 1;
}
【例題】
NOI2004 cashier：
本題中涉及到一個(gè)進(jìn)階操作：刪除值在某一區(qū)間內(nèi)的所有結(jié)點(diǎn)。這一操作會(huì)在下一篇里總結(jié)。
#include <iostream>
#include <stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
const int MAXN = 100001, INF = ~0U >> 2;
struct node {
int v, c[2], p, sz, mul;
bool d;
} T[MAXN];
int n = 0, root, res, tot = 0;
void upd(int x)
{
T[x].sz = T[T[x].c[0]].sz + T[T[x].c[1]].sz + T[x].mul;
}
void sc(int _p, int _c, bool _d)
{
T[_p].c[_d] = _c; T[_c].p = _p; T[_c].d = _d;
}
void rot(int x)
{
int y = T[x].p, d = T[x].d;
if (y == root) {root = x; T[root].p = 0;} else sc(T[y].p, x, T[y].d);
sc(y, T[x].c[!d], d); sc(x, y, !d); upd(y); upd(x);
}
void splay(int x, int r)
{
int i = x, p, p0;
while ((p0 = T[i].p) != r) {
p = T[p0].p;
if (p == r) rot(i); else if (T[i].d == T[p0].d) {rot(p0); rot(i);} else {rot(i); rot(i);}
}
}
void ins(int _v)
{
if (!root) {T[++n].v = _v; T[n].c[0] = T[n].c[1] = T[n].p = 0; T[n].sz = T[n].mul = 1; root = n; return;}
int i = root, j;
while (1) {
T[i].sz++;
if (T[i].v == _v) {T[i].mul++; splay(i, 0); return;}
j = T[i].c[_v > T[i].v];
if (!j) break; else i = j;
}
T[++n].v = _v; T[n].c[0] = T[n].c[1] = 0; T[n].sz = T[n].mul = 1; sc(i, n, _v > T[i].v); splay(n, 0);
}
void del(int lmt)
{
if (!root) return;
int i = root, _min = INF, b = 0, v0;
while (i) {
v0 = T[i].v;
if (v0 == lmt) {b = i; break;}
if (v0 < lmt) i = T[i].c[1]; else {if (v0 < _min) {_min = v0; b = i;} i = T[i].c[0];}
}
if (!b) {tot += T[root].sz; root = 0;} else {splay(b, 0); tot += T[T[root].c[0]].sz; T[T[root].c[0]].p = 0; T[root].c[0] = 0; upd(root);}
}
int Find_Kth(int K)
{
int i = root, s0, m0;
while (1) {
s0 = T[T[i].c[0]].sz; m0 = T[i].mul;
if (K <= s0) i = T[i].c[0]; else if (K <= s0 + m0) return T[i].v; else {K -= s0 + m0; i = T[i].c[1];}
}
}
int main()
{
freopen("cashier.in", "r", stdin);
freopen("cashier.out", "w", stdout);
int m, minv, delt = 0, x;
char ch;
scanf("%d%d%*c", &m, &minv);
re(i, m) {
scanf("%c%d%*c", &ch, &x);
switch(ch) {
case 'I': {if (x >= minv) ins(x - delt); break;}
case 'A': {delt += x; break;}
case 'S': {delt -= x; del(minv - delt); break;}
case 'F': if (T[root].sz - x + 1 <= 0) printf("%d\n", -1); else printf("%d\n", Find_Kth(T[root].sz - x + 1) + delt);
}
}
printf("%d\n", tot);
fclose(stdin); fclose(stdout);
return 0;
}
【相關(guān)論文】
（1）
The Magical Splay（2）
運(yùn)用伸展樹解決數(shù)列維護(hù)問(wèn)題【感謝】
CLJ 神犇
GYZ 神犇
Jollwish 神犇
以及網(wǎng)上提供cashier標(biāo)程的
etc.