CloudySky

纵使世界万般残酷

总有温暖值得守护

左偏树 学习笔记

注：由于这东西既满足树的性质，又满足堆的性质，所以可能两个概念的名词都会使用。

左偏树，是一种可并堆。可以实现两个堆的 O(logn)O(logn) 合并。（本文以大根堆为例）

形态上来讲是一颗二叉树。

性质上定义一个点的 disdis 值为当前点距离最近的叶子结点的距离，根据它的名字就可以知道，左儿子的 disdis 值应该大于右儿子。同时作为一个堆，他应该满足父节点权值大于子节点的性质。

写法上有点像 FHQFHQ 和并查集的结合体，因为要进行合并操作和路径压缩。（可能我技能加点顺序不太对？）

具体实现：

可并堆要维护的信息：

  • ls,rsls, rs 分别表示一个点的左儿子和右儿子。

  • fafa 表示一个点所在堆的堆顶。

    也就是说，一个点的 ls,rsls, rs 一定是它的直接儿子，而他的 fafa 不一定是它的父亲。

  • disdis 值含义如上文。

  • valval 表示一个点的权值。

要实现的操作：

  • buildbuild 操作，将一个独立的值建成一个堆，并进行一些初始化操作。

  • mergemerge 合并两个点所在的堆。其实就是 FHQFHQ 合并操作的阉割版。

    默认两个堆中较大的根节点为当前新堆的根节点，然后递归合并右子树和另一个堆。检查左右子树 disdis 值进行交换来满足左偏性质。

    注意将左右子树的 fafa 值设为新的根节点，以及更新当前根节点的 disdis 值。

  • toptop 取出当前点的堆顶节点，同时进行路径压缩

  • poppop 弹出当前点的堆顶节点。

    直接将堆顶节点的左右儿子的 fafa 值设为自身，将左右子树合并，再将之前根节点的左右儿子设为 0。

    同时，由于进行过路径压缩操作，所以要将之前的堆顶的 fafa 值设为合并后的新堆的根节点。这样既满足了从堆中删除了堆顶，也不会使子树节点迷失。

总结：注意更新 fafa，同时，该更新左右儿子的时候得更新，否则后面可能会引起冲突。

代码实现：

  • 维护的信息
1
2
3
4
5
6
7
8
9
10
// 左偏树 学习笔记
// 要维护的信息具体实现
struct heap {
  int ls, rs, val, dis, fa;
  #define ls(x) T[x].ls
  #define rs(x) T[x].rs
  #define v(x) T[x].val
  #define d(x) T[x].dis
  #define f(x) T[x].fa
} T[Maxn];
  • buildbuild 操作：
1
2
3
4
5
6
7
8
// 左偏树 学习笔记
// build 操作具体实现
int build (int x) {
  int p = ++tot;
  v(p) = x, d(p) = 0, f(p) = p;
  ls(p) = rs(p) = 0;
  return p;
}

有的题要求按照编号进行操作，也可以改成这样：

1
2
3
4
5
6
7
// 左偏树 学习笔记
// build 操作具体实现
int build (int x, int p) {
  v(p) = x, d(p) = 0, f(p) = p;
  ls(p) = rs(p) = 0;
  return p;
}
  • mergemerge 操作：

递归部分代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 左偏树 学习笔记
// merge 操作递归部分的具体实现
int merge (int x, int y) {
  if (!x || !y) return x | y;
  if (v(x) < v(y)) swap (x, y);
  rs(x) = merge (rs(x), y);
  if (d(ls(x)) < d(rs(x)))
    swap (ls(x), rs(x));
  // 后面的两个更新一定不能忘，不更新 dis 会 TLE，不更新 fa 会 WA
  d(x) = d(rs(x)) + 1;
  f(ls(x)) = f(rs(x)) = x;
  return x;
}

非递归部分代码实现：

1
2
3
4
5
6
7
8
9
// 左偏树 学习笔记
// merge 操作非递归部分的具体实现
int m (int x, int y) {
  if (!x || !y || v(x) == -1 || v(y) == -1)
    return x | y;
  int fx = top(x), fy = top(y);
  if (fx == fy) return fx;
  return merge (fx, fy);
}
  • toptop 操作：
1
2
3
4
5
// 左偏树 学习笔记
// top 操作的具体实现
int top (int x) {
  return x == f(x) ? x : f(x) = top (f(x));
}
  • poppop 操作：
1
2
3
4
5
6
7
8
9
10
11
12
// 左偏树 学习笔记
// pop 操作的具体实现
int pop (int x) {
  if (v(x) == -1) return;
  v(x) = -1;
  int fx = top (x);
  f(rs(fx)) = rs(fx);
  f(ls(fx)) = ls(fx);
  int root = m (ls(fx), rs(fx));
  ls(fx) = rs(fx) = 0;
  return root;
}

P1456 Monkey King

代码实现： 
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
// 左偏树 学习笔记
// 模板左偏树 || Monkey King
// Code By CloudySky
#include <bits/stdc++.h>
namespace IO // namespace IO
using namespace IO;
const int Maxn = 1e5 + 10;
using namespace std;

struct heap {
  int ls, rs, val, dis, fa;
  #define ls(x) T[x].ls
  #define rs(x) T[x].rs
  #define v(x) T[x].val
  #define d(x) T[x].dis
  #define f(x) T[x].fa
} T[Maxn];
int tot;

int merge (int x, int y) {
  if (!x || !y) return x | y;
  if (v(x) < v(y)) swap (x, y);
  rs(x) = merge (rs(x), y);
  if (d(ls(x)) < d(rs(x)))
    swap (ls(x), rs(x));
  d(x) = d(rs(x)) + 1;
  f(ls(x)) = f(rs(x)) = x;
  return x;
}

int build (int x) {
  int p = ++tot;
  v(p) = x, d(p) = 0, f(p) = p;
  ls(p) = rs(p) = 0;
  return p;
}

int top (int x) {
  return x == f(x) ? x : f(x) = top (f(x));
}

int m (int x, int y) {
  if (!x || !y) return x | y;
  int fx = top(x), fy = top(y);
  if (fx == fy) return fx;
  int root = merge (fx, fy);
  f(fx) = f(fy) = root; return root;
}

int pop (int x) {
  int fx = top (x);
  f(rs(fx)) = rs(fx);
  f(ls(fx)) = ls(fx);
  int root = m (ls(fx), rs(fx));
  ls(fx) = rs(fx) = 0;
  return root;
}

signed main() {
  v(0) = -1e9;
  int n;
  while (cin >> n) {
  tot = 0;
  for (int i = 1; i <= n; ++i)
    build (read ());
  int k = read ();
  for (int i = 1; i <= k; ++i) {
    int x = read (), y = read ();
    if (top (x) == top (y))
      print (-1);
    else {
      int r1 = top (x), r2 = top(y);
      v(r1) >>= 1, v(r2) >>= 1;
      int r3 = pop (r1), r4 = pop (r2);
      print (v(m ((r3 ? m (r1, r3) : r1), (r4 ? m (r2, r4) : r2))));
    }
  }
  }
  return 0;
}

本文作者：CloudySky
写作时间： 2022-01-28
最后更新时间： 2022-01-28
遵循协议： BY-NC-SA

Top