splay

splay 的基本原理

一般情况下,splay每操作一个节点,需要将该节点旋转至树根
在旋转的时候维护树的平衡性

splay 旋转和 splay 函数
splay 的旋转,需要维护二叉树的中序遍历的一致性
splay-01
splay-02

splay 维护信息
splay-03

模版题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
const int maxn = 1e5 + 10;
int n, m;

namespace Splay {
class node {
public:
int son[2], pa;
int sz, tag, v;

node() = default;
void init(int _v, int _pa) {
v = _v, pa = _pa;
sz = 1;
}
};

int root = 0;
int idx = 0;
vector<node> t(maxn, node());

inline void pull(int p) {
t[p].sz = t[t[p].son[0]].sz + t[t[p].son[1]].sz + 1;
}

inline void push(int p) {
if (!t[p].tag) return;
swap(t[p].son[0], t[p].son[1]);
t[t[p].son[0]].tag ^= 1, t[t[p].son[1]].tag ^= 1;
t[p].tag = 0;
}
void rotate(int x) {
int y = t[x].pa, z = t[y].pa;
int k = t[y].son[1] == x;

t[z].son[t[z].son[1] == y] = x, t[x].pa = z;
t[y].son[k] = t[x].son[k^1], t[t[x].son[k^1]].pa = y;
t[x].son[k^1] = y, t[y].pa = x;
pull(y), pull(x);
}

void splay(int x, int k) {
while (t[x].pa != k) {
int y = t[x].pa, z = t[y].pa;
if (z != k) {
if ((t[z].son[1] == y) ^ (t[y].son[1] == x)) rotate(x);
else rotate(y);
}
rotate(x);
}
if (!k) root = x;
}

void insert(int val) {
int u = root, p = 0;
while (u) p = u, u = t[u].son[val > t[u].v];
u = ++idx;
if (p) t[p].son[val > t[p].v] = u;
t[u].init(val, p);

splay(u, 0);
}

int get_k(int k) {
int u = root;
while (u) {
push(u);
if (t[t[u].son[0]].sz >= k) u = t[u].son[0];
else if (t[t[u].son[0]].sz + 1 == k) return u;
else k -= t[t[u].son[0]].sz + 1, u = t[u].son[1];
}
return -1;
}

void print(int u) {
push(u);
if (t[u].son[0]) print(t[u].son[0]);
if (t[u].v >= 1 && t[u].v <= n) printf("%d ", t[u].v);
if (t[u].son[1]) print(t[u].son[1]);
}
}

using namespace Splay;

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &m);

for (int i = 0; i <= n+1; i++) insert(i);
while (m--) {
int li, ri;
scanf("%d%d", &li, &ri);
int l = get_k(li), r = get_k(ri+2);
splay(l, 0), splay(r, l);
t[t[r].son[0]].tag ^= 1;
}
print(root);
}

splay 维护信息

郁闷的出纳员

  • 操作中涉及到将所有员工的工资都增加,容易想到用一个全局变量Δ\Delta 来维护
    splay\text{splay} 中维护的值为xx,那么员工真实的工资数值为x+Δx + \Delta
  • 招员工和员工离职,就是splay\text{splay} 中常见的添加,删除操作
  • 比较难处理的是员工离职的情况,员工工资x+Δ<minx + \Delta < \min 最低工资标准会离职
    • 在 splay 两端加入两个哨兵,, +-\infty, \ +\infty,splay 执行删除区间操作
      待删区间的左端点就是L=L = -\infty,右端点是第一个满足tR.vminΔt_R.v \geqslant \min-\DeltaRR
      删除[L,R][L, R] 区间,将RR splay 到根,并且将LL splay 成RR 的儿子,删除RR 右子树即可
    • 找到minΔ\geqslant \min - \Delta 的最小数,实际上就是执行平衡二叉树的二分查找
      如果根节点uu 满足,uu 是备选答案,接着去uu 的左子树尝试找更小的
1

BST 找前驱和后继

splay 也是一种特殊的平衡二叉树,涉及找uu 的前驱和后继问题
这和一般的平衡二叉树找前驱后继大同小异

前驱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void get_pre(int val) {
int res = 0;
// t[res].dat = -inf

int u = root;
while (u) {
if (val == t[u].val) {
if (t[u].son[0]) {
u = t[u].son[0];
while (t[u].son[1]) u = t[u].son[1];
res = u;
}
break;
}
if (t[p].dat < val && t[p].dat > t[res].val) res = p;
p = t[p].son[val >= t[p].val];
}
return t[res].val;
}

后继

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void get_nxt(int val) {
int res = 2;
// t[2].dat = inf;

int u = root;
while (u) {
if (t[u].val == val) {
if (t[u].son[1]) {
u = t[u].son[1];
while (t[u].son[0]) u = t[u].son[0];
res = u;
}
break;
}
if (t[u].dat > val && t[u].dat < t[res].dat) res = u;
u = t[u].son[val >= t[u].dat];
}
return t[res].dat;
}

splay 启发式合并

永无乡

可以考虑用并查集维护连通性,同时完成启发式合并

  1. 一开始先建nn 棵 splay 树,对于连通的岛屿(a,b)(a, b)
    执行启发式合并,将较小的集合合并到较大的集合中,比如size(a)<size(b), ab\textbf{size}(a) < \textbf{size}(b), \ a \to b
  2. 合并aba \to b,需要dfs(root(a))\textbf{dfs}(\text{root}(a)),遍历aa 子树的每一个点uu
    并且依次将uu 插入bb 这棵 splay 中
  3. 查询第xx 棵 splay 的第kk 大树即可
1