平衡树学习笔记
Visits: 770
其实是学过的，然后，就忘了……
本文介绍 Splay/Link Cut Tree/FHQ Treap 三种平衡树相关的数据结构。
Splay
Splay 是一种二叉查找树，它通过不断将某个节点旋转到根节点，使得整棵树仍然满足二叉查找树的性质，并且保持平衡而不至于退化为链。
变量信息
| $rt$ | $tot$ | $f_p$ | $ch_{p,0/1}$ | $a_p$ | $c_p$ | $s_p$ |
|---|---|---|---|---|---|---|
| 根节点 | 节点个数 | 父节点 | 左/右儿子 | 节点权值 | 权值次数 | 子树大小 |
struct Splay {
int rt, tot, f[N], ch[N][2], a[N], c[N], s[N];
#define lc ch[p][0]
#define rc ch[p][1]
};
维护操作
$\operatorname{upd}(p)$
更新 $s_p$。
#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + c[p]
$\operatorname{get}(p)$
判断 $p$ 是 $f_p$ 的左儿子还是右儿子。
#define get(p) (p == ch[f[p]][1])
$\operatorname{clr}(p)$
销毁 $p$。
#define clr(p) f[p] = ch[p][0] = ch[p][1] = a[p] = c[p] = s[p] = 0
$\operatorname{rot}(p)$
将 $p$ 旋转上移一个位置。
inline void rot(int p) {
int x = f[p], y = f[x], u = get(p), v = get(x);
f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
if ((f[p] = y)) ch[y][v] = p;
}
$\operatorname{splay}(p, g)$
这是 splay 中最重要的操作。
将 $p$ 旋转为 $g$ 的儿子（若 $g$ 为 $0$ 则旋转为根）。
inline void splay(int p, int g = 0) {
for (int x = f[p]; (x = f[p]) != g; rot(p))
if (f[x] != g) rot(get(p) == get(x) ? x : p);
if (!g) rt = p;
}
访问操作
$\operatorname{ins}(k)$
插入 $k$。
inline void ins(int k) {
if (!rt) return a[rt=++tot] = k, c[tot] = s[tot] = 1, void();
int x = rt, y = 0;
while (1) {
if (a[x] == k) return ++c[x], ++s[x], upd(y), splay(x);
y = x, x = ch[x][a[x]<k];
if (!x) {
a[++tot] = k, c[tot] = s[tot] = 1;
f[tot] = y, ch[y][a[y]<k] = tot, upd(y);
return splay(tot);
}
}
}
$\operatorname{rnk}(k)$
查询 $k$ 的排名（$<k$ 的数的个数 $+1$）。
inline int rnk(int k) {
int p = rt, x = 0;
while (1)
if (k < a[p]) {
if (!lc) return splay(p), x + 1;
p = lc;
} else {
x += s[lc];
if (k == a[p]) return splay(p), x + 1;
x += c[p];
if (!rc) return splay(p), x + 1;
p = rc;
}
}
$\operatorname{kth}(k)$
查询排名为 $k$ 的数。
inline int kth(int k) {
int p = rt;
while (1)
if (k <= s[lc]) p = lc;
else {
k -= s[lc];
if (k <= c[p]) return splay(p), a[p];
k -= c[p], p = rc;
}
}
$\operatorname{pre}(k)$
查询 $k$ 的前驱（$<k$ 的最大的数）。
inline int pre(int k) {
return kth(rnk(k) - 1);
}
$\operatorname{nxt}(k)$
查询 $k$ 的后继（$>k$ 的最小的数）。
inline int nxt(int k) {
return kth(rnk(k + 1));
}
$\operatorname{del}(k)$
删除 $k$（如果没有则跳过）。
inline void del(int k) {
rnk(k);
if (k != a[rt]) return;
if (c[rt] > 1) return --c[rt], --s[rt], void();
int p = rt;
if (!lc && !rc) return rt = 0, clr(p), void();
if (!lc || !rc) return f[rt=lc+rc] = 0, clr(p), void();
return pre(k), f[rc] = rt, ch[rt][1] = rc, clr(p), --s[rt], void();
}
【模板】P3369 【模板】普通平衡树
const int N = 1e5 + 7;
struct Splay {
int rt, tot, f[N], ch[N][2], a[N], c[N], s[N];
#define lc ch[p][0]
#define rc ch[p][1]
#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + c[p]
#define get(p) (p == ch[f[p]][1])
#define clr(p) f[p] = ch[p][0] = ch[p][1] = a[p] = c[p] = s[p] = 0
inline void rot(int p) {
int x = f[p], y = f[x], u = get(p), v = get(x);
f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
if ((f[p] = y)) ch[y][v] = p;
}
inline void splay(int p, int g = 0) {
for (int x = f[p]; (x = f[p]) != g; rot(p))
if (f[x] != g) rot(get(p) == get(x) ? x : p);
if (!g) rt = p;
}
inline void ins(int k) {
if (!rt) return a[rt=++tot] = k, c[tot] = s[tot] = 1, void();
int x = rt, y = 0;
while (1) {
if (a[x] == k) return ++c[x], ++s[x], upd(y), splay(x);
y = x, x = ch[x][a[x]<k];
if (!x) {
a[++tot] = k, c[tot] = s[tot] = 1;
f[tot] = y, ch[y][a[y]<k] = tot, upd(y);
return splay(tot);
}
}
}
inline int rnk(int k) {
int p = rt, x = 0;
while (1)
if (k < a[p]) {
if (!lc) return splay(p), x + 1;
p = lc;
} else {
x += s[lc];
if (k == a[p]) return splay(p), x + 1;
x += c[p];
if (!rc) return splay(p), x + 1;
p = rc;
}
}
inline int kth(int k) {
int p = rt;
while (1)
if (k <= s[lc]) p = lc;
else {
k -= s[lc];
if (k <= c[p]) return splay(p), a[p];
k -= c[p], p = rc;
}
}
inline int pre(int k) {
return kth(rnk(k) - 1);
}
inline int nxt(int k) {
return kth(rnk(k + 1));
}
inline void del(int k) {
rnk(k);
if (k != a[rt]) return;
if (c[rt] > 1) return --c[rt], --s[rt], void();
int p = rt;
if (!lc && !rc) return rt = 0, clr(p), void();
if (!lc || !rc) return f[rt=lc+rc] = 0, clr(p), void();
return pre(k), f[rc] = rt, ch[rt][1] = rc, clr(p), --s[rt], void();
}
} splay;
int main() {
int n;
rd(n);
for (int i = 1, o, x; i <= n; i++) {
rd(o), rd(x);
switch (o) {
case 1 : splay.ins(x); break;
case 2 : splay.del(x); break;
case 3 : print(splay.rnk(x)); break;
case 4 : print(splay.kth(x)); break;
case 5 : print(splay.pre(x)); break;
case 6 : print(splay.nxt(x)); break;
}
}
return 0;
}
【模板】P3391 【模板】文艺平衡树
const int N = 1e5 + 7;
int n, m;
struct Splay {
int rt, tot, f[N], ch[N][2], a[N], c[N], s[N], v[N];
#define lc ch[p][0]
#define rc ch[p][1]
#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + c[p]
#define get(p) (p == ch[f[p]][1])
#define clr(p) f[p] = ch[p][0] = ch[p][1] = a[p] = c[p] = s[p] = 0
#define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])
inline void spd(int p) {
if (p && v[p]) {
if (lc) rev(lc);
if (rc) rev(rc);
v[p] = 0;
}
}
inline void rot(int p) {
int x = f[p], y = f[x], u = get(p), v = get(x);
f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
if ((f[p] = y)) ch[y][v] = p;
}
inline void splay(int p, int g = 0) {
for (int x = f[p]; (x = f[p]) != g; rot(p))
if (f[x] != g) rot(get(p) == get(x) ? x : p);
if (!g) rt = p;
}
inline void ins(int k) {
if (!rt) return a[rt=++tot] = k, c[tot] = s[tot] = 1, void();
int x = rt, y = 0;
while (1) {
if (a[x] == k) return ++c[x], ++s[x], upd(y), splay(x);
y = x, x = ch[x][a[x]<k];
if (!x) {
a[++tot] = k, c[tot] = s[tot] = 1;
f[tot] = y, ch[y][a[y]<k] = tot, upd(y);
return splay(tot);
}
}
}
inline int kth(int k) {
int p = rt;
while (1) {
spd(p);
if (k <= s[lc]) p = lc;
else {
k -= s[lc];
if (k <= c[p]) return splay(p), p;
k -= c[p], p = rc;
}
}
}
inline void work(int l, int r) {
l = kth(l - 1), r = kth(r + 1), splay(l), splay(r, l), rev(ch[r][0]);
}
void dfs(int p) {
spd(p);
if (lc) dfs(lc);
if (a[p] && a[p] <= n) print(a[p], ' ');
if (rc) dfs(rc);
}
} splay;
int main() {
rd(n), rd(m);
for (int i = 0; i <= n + 1; i++) splay.ins(i);
for (int i = 1, l, r; i <= m; i++) rd(l), rd(r), splay.work(l + 1, r + 1);
splay.dfs(splay.rt);
return 0;
}
Link Cut Tree
Link Cut Tree (LCT) 是一种数据结构，我们用它来解决动态树问题。Splay 是 LCT 的基础，但是 LCT ⽤的 Splay 和普通的 Splay 在细节处不太一样（进行了一些扩展）。
LCT 的主要结构
LCT 由多个 Splay 构成，维护一个树，树的每个节点与所有 Splay 节点一一对应。
树的每条边分为实边和虚边。
对于实边，每一个 Splay 通过其中序遍历维护一条从上到下在原树中的深度严格递增的实链。
对于虚边，各个 Splay 之间并不是独立的。每个 Splay 的根节点的父亲节点本应是空，但在 LCT 中每个 Splay 的根节点的父亲节点指向原树中这条实链的最顶端的点的父亲节点。每个这样的指向对应了原树中的一条虚边，其特点在于认父不认子。因此，每个连通块恰好有一个点的父亲节点为空。
变量信息
| $f_p$ | $ch_{p,0/1}$ | $s_p$ | $v_p$ | $a_p$ | $c_p$ |
|---|---|---|---|---|---|
| 父节点 | 左/右儿子 | 子树大小 | 翻转标记 | 节点权值 | 路径权值异或和 |
struct LCT {
int f[N], ch[N][2], s[N], v[N], a[N], c[N];
#define lc ch[p][0]
#define rc ch[p][1]
};
维护操作
$\operatorname{upd}(p)$
更新 $s_p$ 和 $c_p$。
#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1, c[p] = c[ch[p][0]] ^ c[ch[p][1]] ^ a[p]
$\operatorname{get}(p)$
判断 $p$ 是 $f_p$ 的左儿子还是右儿子。
#define get(p) (p == ch[f[p]][1])
$\operatorname{rev}(p)$
翻转 $p$。
#define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])
$\operatorname{isrt}(p)$
判断 $p$ 是否为所在 Splay 的根。
#define isrt(p) (ch[f[p]][0] != p && ch[f[p]][1] != p)
$\operatorname{spd}(p)$
下传 $v_p$。
inline void spd(int p) {
if (p && v[p]) {
if (lc) rev(lc);
if (rc) rev(rc);
v[p] = 0;
}
}
$\operatorname{rot}(p)$
将 $p$ 旋转上移一个位置。
inline void rot(int p) {
int x = f[p], y = f[x], u = get(p), v = get(x), o = isrt(x);
f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
if ((f[p] = y) && !o) ch[y][v] = p;
}
$\operatorname{pre}(p)$
$\operatorname{splay}(p)$ 之前的准备工作，要把路径上的点都 $\operatorname{spd}(p)$ 一下。
void pre(int p) {
if (!isrt(p)) pre(f[p]);
spd(p);
}
$\operatorname{splay}(p)$
将 $p$ 旋转为所在 Splay 的根。
inline void splay(int p) {
pre(p);
for (int x = f[p]; !isrt(p); rot(p), x = f[p])
if (!isrt(x)) rot(get(p) == get(x) ? x : p);
}
$\operatorname{access}(p)$
这是 LCT 中最重要的操作。
把从原树的根到 $p$ 的路径拉成一条实链放到一个 Splay 里。
inline void access(int p) {
for (int x = 0; p; p = f[x=p]) splay(p), rc = x, upd(p);
}
$\operatorname{mkrt}(p)$
使 $p$ 直接成为原树的根。
inline void mkrt(int p) {
access(p), splay(p), rev(p);
}
$\operatorname{split}(x, y)$
把原树中 $x,y$ 之间的路径拉成一条实链放到一个 Splay 里（同时使 $y$ 成为原树的根）。
inline void split(int x, int y) {
mkrt(x), access(y), splay(y);
}
访问操作
$\operatorname{fdrt}(p)$
找到 $p$ 所在的原树的根。
inline int fdrt(int p) {
access(p), splay(p);
while (lc) spd(p), p = lc;
return splay(p), p;
}
$\operatorname{link}(x, y)$
在原树的 $x,y$ 两点间连一条边（若已经连通则不连）。
inline bool link(int x, int y) {
mkrt(x);
return fdrt(y) != x && (f[x] = y);
}
$\operatorname{cut}(x, y)$
将原树的 $x,y$ 两点间的边删掉（若不存在则不删）。
inline bool cut(int x, int y) {
mkrt(x);
if (fdrt(y) != x || s[x] != 2) return 0;
return f[y] = ch[x][1] = 0, upd(x), 1;
}
$\operatorname{chg}(p, x)$
将 $p$ 的点权修改为 $x$。
inline void chg(int p, int x) {
mkrt(p), a[p] = x, upd(p);
}
【模板】P3690 【模板】Link Cut Tree （动态树）
const int N = 1e5 + 7;
int n, m;
struct LCT {
int f[N], ch[N][2], s[N], v[N], a[N], c[N];
#define lc ch[p][0]
#define rc ch[p][1]
#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1, c[p] = c[ch[p][0]] ^ c[ch[p][1]] ^ a[p]
#define get(p) (p == ch[f[p]][1])
#define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])
#define isrt(p) (ch[f[p]][0] != p && ch[f[p]][1] != p)
inline void spd(int p) {
if (p && v[p]) {
if (lc) rev(lc);
if (rc) rev(rc);
v[p] = 0;
}
}
inline void rot(int p) {
int x = f[p], y = f[x], u = get(p), v = get(x), o = isrt(x);
f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
if ((f[p] = y) && !o) ch[y][v] = p;
}
void pre(int p) {
if (!isrt(p)) pre(f[p]);
spd(p);
}
inline void splay(int p) {
pre(p);
for (int x = f[p]; !isrt(p); rot(p), x = f[p])
if (!isrt(x)) rot(get(p) == get(x) ? x : p);
}
inline void access(int p) {
for (int x = 0; p; p = f[x=p]) splay(p), rc = x, upd(p);
}
inline void mkrt(int p) {
access(p), splay(p), rev(p);
}
inline void split(int x, int y) {
mkrt(x), access(y), splay(y);
}
inline int fdrt(int p) {
access(p), splay(p);
while (lc) spd(p), p = lc;
return splay(p), p;
}
inline bool link(int x, int y) {
mkrt(x);
return fdrt(y) != x && (f[x] = y);
}
inline bool cut(int x, int y) {
mkrt(x);
if (fdrt(y) != x || s[x] != 2) return 0;
return f[y] = ch[x][1] = 0, upd(x), 1;
}
inline void chg(int p, int x) {
mkrt(p), a[p] = x, upd(p);
}
} lct;
int main() {
rd(n), rd(m);
for (int i = 1; i <= n; i++) rd(lct.a[i]), lct.c[i] = lct.a[i], lct.s[i] = 1;
for (int i = 1, o, x, y; i <= m; i++) {
rd(o), rd(x), rd(y);
switch (o) {
case 0 : lct.split(x, y), print(lct.c[y]); break;
case 1 : lct.link(x, y); break;
case 2 : lct.cut(x, y); break;
case 3 : lct.chg(x, y); break;
}
}
return 0;
}
常见应用
- 维护链信息（平衡树操作）
- 动态维护连通性 & 边双联通分量（可以说是并查集的升级，因为并查集只能连不能断）
- 维护边权（将边当成点进行操作，常用于维护生成树）
- 维护子树信息
维护子树信息
有时候，我们需要的并不是维护链的信息，而是子树的信息。要知道，LCT 强于维护链的信息，而弱于维护子树的信息。然而动态的连边和断边，又不得不要求我们使用 LCT 来维护。
我们已经可以通过 Splay 来获知实子树（也就是原树中的一条链）的信息总和，现在只需要维护虚子树的信息总和，然后两者相加即可。
讨论一下 LCT 中的每个操作会对虚实边产生怎样的影响，结果你会惊奇的发现，只有 $\operatorname{access}(p)$ 和 $\operatorname{link}(p)$ 需要进行小小的修改就能轻松的维护了。
FHQ Treap
Treap 是一种弱平衡的二叉搜索树。Treap 这个单词是 Tree 和 Heap 的组合，表明 Treap 是一种由树和堆组合形成的数据结构。Treap 除了本身储存的值要满足二叉搜索树的性质之外，每个结点上要额外储存一个值，这个值需满足大根堆的性质。而这个额外的值是每个结点建立时随机生成的，因此 Treap 是期望平衡的。
Treap 分为旋转式和无旋式两种，FHQ Treap 即无旋式 Treap。FHQ Treap 的操作方式使得它天生支持维护序列、可持久化等特性，从而使这个东西严格意义上吊打无旋式 Treap 和 Splay，它们能搞的事情 FHQ Treap 都能搞。
变量信息及基本维护操作
| $rt$ | $tot$ | $ch_{p,0/1}$ | $a_p$ | $d_p$ | $s_p$ |
|---|---|---|---|---|---|
| 根节点 | 节点个数 | 左/右儿子 | 节点权值 | 节点随机值 | 子树大小 |
struct Treap {
int rt, tot, ch[N][2], a[N], d[N], s[N];
#define lc ch[p][0]
#define rc ch[p][1]
#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1
#define clr(p) ch[p][0] = ch[p][1] = a[p] = d[p] = s[p] = 0
} treap;
维护操作
FHQ Treap 的维护操作仅有两个，分裂 (split) 与合并 (merge)。
分裂 (split)
分裂过程接受两个参数：根指针 $p$ 和关键值 $k$。结果为将根指针指向的 Treap 分裂为两个 Treap，第一个 Treap 所有结点的关键值小于等于 $k$，第二个 Treap 所有结点的关键值大于 $k$。
inline void split(int p, int k, int &x, int &y) {
if (!p) return x = y = 0, void();
if (a[p] <= k) x = p, split(rc, k, rc, y);
else y = p, split(lc, k, x, lc);
upd(p);
}
合并 (merge)
合并过程接受两个参数：左 Treap 的根指针 $x$、右 Treap 的根指针 $y$，必须满足 $x$ 中所有结点的关键值小于等于 $y$ 中所有结点的关键值。因为两个 Treap 已经有序，我们只需要考虑额外的随机值来决定哪个 Treap 应与另一个 Treap 的儿子合并。
inline int merge(int x, int y) {
if (!x || !y) return x | y;
if (d[x] < d[y]) return ch[y][0] = merge(x, ch[y][0]), upd(y), y;
return ch[x][1] = merge(ch[x][1], y), upd(x), x;
}
访问操作
$\operatorname{ins}(k)$
插入 $k$。
inline void ins(int k) {
a[++tot] = k, s[tot] = 1, d[tot] = rand();
if (!rt) return rt = tot, void();
int x, y;
split(rt, k, x, y), rt = merge(merge(x, tot), y);
}
$\operatorname{rnk}(k)$
查询 $k$ 的排名（$<k$ 的数的个数 $+1$）。
inline int rnk(int k) {
int x, y, ret;
return split(rt, k - 1, x, y), ret = s[x] + 1, merge(x, y), ret;
}
$\operatorname{kth}(k)$
查询排名为 $k$ 的数。
inline int kth(int k) {
int p = rt;
while (1)
if (k <= s[lc]) p = lc;
else {
k -= s[lc] + 1;
if (!k) return a[p];
p = rc;
}
}
$\operatorname{pre}(k)$
查询 $k$ 的前驱（$<k$ 的最大的数）。
inline int pre(int k) {
return kth(rnk(k) - 1);
}
$\operatorname{nxt}(k)$
查询 $k$ 的后继（$>k$ 的最小的数）。
inline int nxt(int k) {
return kth(rnk(k + 1));
}
$\operatorname{del}(k)$
删除 $k$（如果没有则跳过）。
inline void del(int k) {
int x, y, z;
split(rt, k, x, z), split(x, k - 1, x, y);
rt = merge(merge(x, merge(ch[y][0], ch[y][1])), z);
clr(y);
}
【模板】P3369 【模板】普通平衡树
const int N = 1e5 + 7;
struct Treap {
int rt, tot, ch[N][2], a[N], d[N], s[N];
#define lc ch[p][0]
#define rc ch[p][1]
#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1
#define clr(p) ch[p][0] = ch[p][1] = a[p] = d[p] = s[p] = 0
inline void split(int p, int k, int &x, int &y) {
if (!p) return x = y = 0, void();
if (a[p] <= k) x = p, split(rc, k, rc, y);
else y = p, split(lc, k, x, lc);
upd(p);
}
inline int merge(int x, int y) {
if (!x || !y) return x | y;
if (d[x] < d[y]) return ch[y][0] = merge(x, ch[y][0]), upd(y), y;
return ch[x][1] = merge(ch[x][1], y), upd(x), x;
}
inline void ins(int k) {
a[++tot] = k, s[tot] = 1, d[tot] = rand();
if (!rt) return rt = tot, void();
int x, y;
split(rt, k, x, y), rt = merge(merge(x, tot), y);
}
inline int rnk(int k) {
int x, y, ret;
return split(rt, k - 1, x, y), ret = s[x] + 1, merge(x, y), ret;
}
inline int kth(int k) {
int p = rt;
while (1)
if (k <= s[lc]) p = lc;
else {
k -= s[lc] + 1;
if (!k) return a[p];
p = rc;
}
}
inline int pre(int k) {
return kth(rnk(k) - 1);
}
inline int nxt(int k) {
return kth(rnk(k + 1));
}
inline void del(int k) {
int x, y, z;
split(rt, k, x, z), split(x, k - 1, x, y);
rt = merge(merge(x, merge(ch[y][0], ch[y][1])), z);
clr(y);
}
} treap;
int main() {
int n;
rd(n), treap.ins(-1e9), treap.ins(1e9);
for (int i = 1, o, x; i <= n; i++) {
rd(o), rd(x);
switch (o) {
case 1 : treap.ins(x); break;
case 2 : treap.del(x); break;
case 3 : print(treap.rnk(x) - 1); break;
case 4 : print(treap.kth(x + 1)); break;
case 5 : print(treap.pre(x)); break;
case 6 : print(treap.nxt(x)); break;
}
}
return 0;
}
【模板】P3391 【模板】文艺平衡树
const int N = 1e5 + 7;
int n, m;
struct Treap {
int rt, tot, ch[N][2], a[N], d[N], s[N], v[N];
#define lc ch[p][0]
#define rc ch[p][1]
#define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1
#define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])
inline void spd(int p) {
if (p && v[p]) {
if (lc) rev(lc);
if (rc) rev(rc);
v[p] = 0;
}
}
inline void split(int p, int k, int &x, int &y) {
if (!p) return x = y = 0, void();
spd(p);
if (s[lc] < k) x = p, k -= s[lc] + 1, split(rc, k, rc, y);
else y = p, split(lc, k, x, lc);
upd(p);
}
inline int merge(int x, int y) {
if (!x || !y) return x | y;
spd(x), spd(y);
if (d[x] < d[y]) return ch[y][0] = merge(x, ch[y][0]), upd(y), y;
return ch[x][1] = merge(ch[x][1], y), upd(x), x;
}
inline void ins(int k) {
a[++tot] = k, s[tot] = 1, d[tot] = rand();
if (!rt) return rt = tot, void();
int x, y;
split(rt, k, x, y), rt = merge(merge(x, tot), y);
}
inline void work(int l, int r) {
int x, y, z;
split(rt, r, x, z), split(x, l - 1, x, y);
rev(y), merge(merge(x, y), z);
}
void dfs(int p) {
spd(p);
if (lc) dfs(lc);
if (a[p] && a[p] <= n) print(a[p], ' ');
if (rc) dfs(rc);
}
} treap;
int main() {
rd(n), rd(m);
for (int i = 0; i <= n + 1; i++) treap.ins(i);
for (int i = 1, l, r; i <= m; i++) rd(l), rd(r), treap.work(l + 1, r + 1);
treap.dfs(treap.rt);
return 0;
}
参考资料
- OI Wiki Splay
- OI Wiki Link Cut Tree
- FlashHu LCT总结——概念篇+洛谷P3690[模板]Link Cut Tree(动态树)（LCT，Splay）
- FlashHu LCT总结——应用篇（附题单）（LCT）
- OI Wiki Treap
- _Mocha_ Fhq-Treap总结：短小精悍不旋转的神级数据结构
