胡扯
$LCT$ 运用实链剖分,对于一个父亲来说,只有一个儿子对应实边,其它的对应虚边,一堆的实边连在一起就变成了实链,我们用 $Splay$ 维护。
其中实边指的是一条连通父亲儿子的双向边,而虚边则指的是儿子到父亲的单向边。在 $LCT$ 中,实边组成的实链被 $Splay$ 储存,而虚边则是 $Splay$ 的根节点连到父亲的边,所以 $LCT$ 其实可以看做一堆 $Splay$ 通过虚边相连。
性质:
- 任何结点包含且仅包含于一个 $Splay$ 中
- $Splay$ 中的结点的深度在原树中按中序遍历递增
注意 $LCT$ 维护的是森林。
)
接下来讲 $LCT$ 的基本操作。
Access
最重要的操作,将 $x$ 到树根结点之间拉一条实链,以下记 $y$ 为上一次操作的 $Splay$ 的根,$y$ 初始为 $0$。
首先我们把 $x$ 转到它所处的 $Splay$ 的根,然后把它的右儿子($y$ 深度大,由操作二替换到右儿子)改为 $y$,然后 $pushup$ 一下 $x$,最后令 $x = fa[x]$。
这样子起到了什么效果呢?显然原来的右实儿子变成了虚儿子,而右儿子的地方被替换为了上一个 $Splay$ 的根,并且连的是实边。我们的目标是将最初的 $x$ 与根结点之间打通实链,那么 $Access$ 的过程相当于在不断地将两个 $Splay$ 连接起来,形成实链。
放几个图:
先是 $Splay(N)$
然后 $Splay(I)$
然后 $Splay(H)$
最后 $Splay(A)$
如此 $A-N$ 的路径便在一个 $Splay$ 里了。
inline void access(int x) {
for (int y = 0; x; y = x, x = tr[x].p)
splay(x), tr[x].s[1] = y, pushup(x);
}
Makeroot
将 $LCT$ 的根换为 $x$。
首先 $access(x)$,然后 $splay(x)$,最后翻转一整棵 $Splay$。
由于 $access$ 一直是往右儿子挂,所以最后 $x$ 会在整棵 $Splay$ 的最右下(即中序遍历最后的点)。所以 $splay$ 后 $x$ 没有右儿子,这时再将整棵 $Splay$ 翻转,这样 $x$ 的左子树就去了右边,$x$ 就成了深度最小的点。
inline void reverse(int x) {
swap(tr[x].s[0], tr[x].s[1]);
tr[x].flag ^= 1;
}
inline void makeroot(int x) {
access(x); splay(x); pushdown(x);
}
代码中的 $pushdown$ 就是文艺平衡树中的懒标记下传。
Findroot
找 $x$ 所在树的根节点。
同样 $access(x)$,然后 $splay(x)$,接着找到最左边的,它就是 $x$ 所在树的根节点。
为了防止卡链,最后还要再 $splay(根)$。
inline void pushdown(int x) {
if (tr[x].flag) {
if (tr[x].s[0]) reverse(tr[x].s[0]);
if (tr[x].s[1]) reverse(tr[x].s[1]);
}
tr[x].flag = 0; // 这里一定是等于 0,不能 ^1
}
inline int findroot(int x) {
access(x); splay(x);
while (tr[x].s[0]) {
pushdown(x); // 记得下传懒标记
x = tr[x].s[0];
}
splay(x);
return x;
}
Link
将 $x$ 和 $y$ 连边。
首先 $makeroot(x)$,然后判断一下 $findroot(y)$ 如果等于 $x$就不连,否则将 $x$ 的父亲置为 $y$ 连一条虚边。
$findroot(y) = x$ 时不连是因为如果别人已经在一条链上了,你再连就会出现双向边或环。
inline void link(int x, int y) {
makeroot(x);
if (findroot(y) == x) return;
tr[x].p = y;
}
Cut
砍掉 $x-y$ 的边。
首先还是 $makeroot(x)$,接着考虑什么时候连边不合法。明显当 $findroot(y) != x$ 时不合法,说明两者不在一棵 $Splay$ 中。那在同一棵树中的情况呢?
你想,$Splay$ 维护的是中序遍历,并且我们已经使 $x$ 成为了根,所以如果 $y$ 还有左子结点,则二者一定在原树上不相邻。同时,我们在 $findroot$ 中已经 $access(y)$,所以如果 $x$ 与 $y$ 在同一 $Splay$ 中却还没有连边,这条路径上一定还会有其它的点,所以如果 $fa[y] != x$ 也是不合法的。
判完后令 $x$ 的右儿子和 $y$ 的父亲置为 $NULL$。
最后因为记得 $pushdown$。
为什么 $link$ 不需要 $pushdown$?因为它连的是虚边。
inline void cut(int x, int y) {
makeroot(x);
if (findroot(y) != x || tr[y].p != x || tr[y].s[0]) return;
tr[x].s[1] = tr[y].p = 0;
pushup(x);
}
一个很重要的点:在使用 $cut$ 时无论边是否一定合法都不能直接去掉判断行,因为 $findroot$ 操作会对 $y$ 进行操作,去掉答案会发生错误!!!!
Split
把 $x-y$ 拆成一棵方便操作的 $Splay$。
因为 $Access(y)$ 会使得 $y$ 到根节点拉出一条实链,所以只要事先 $makeroot(x)$ 就可以拉出一条 $x-y$ 的实链。
最后为了方便瞎搞,可以 $splay(y)$ 把 $y$ 转到根节点,原因是这样子 $y$ 只有左儿子。
inline void split(int x, int y) {
makeroot(x); access(y); splay(y);
}
Splay
由于 $LCT$ 引入了虚实边的概念,所以 $Splay$ 的代码也要稍加变化。
在 $rotate$ 中,由于 $y$ 可能是 $Splay$ 的根,这样 $y-z$ 就是虚边了,所以旋转时 $x-z$ 只能单向连边。
在 $splay$ 中,由于每次都是转到根,$splay$ 中就只传入一个变量,循环的判断条件也要改变。
inline void rotate(int x) {
int y = tr[x].p, z = tr[y].p;
int k = tr[y].s[1] == x;
tr[x].p = z;
if (ntroot(y)) tr[z].s[tr[z].s[1] == y] = x;
tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
tr[y].p = x, tr[x].s[k ^ 1] = y;
pushup(y); pushup(x);
}
inline void splay(int x) {
pushall(x);
while (ntroot(x)) {
int y = tr[x].p, z = tr[y].p;
if (ntroot(y)) {
if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
else rotate(y);
}
rotate(x);
}
}
模板
瞎扯了那么多,现在放个模板。
// 洛谷 P3690
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); i ++)
#define fro(i, a, b) for (int i = (a); i >= b; i --)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x & (-x))
#define initrand srand((unsigned)time(0))
#define random(x) ((LL)rand() * rand() % (x))
#define eb emplace_back
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
return x * f;
}
const int N = 100010;
int n, m;
struct Splay {
int s[2], p, val, res, flag;
} tr[N];
inline bool ntroot(int x) {
return tr[tr[x].p].s[0] == x || tr[tr[x].p].s[1] == x;
}
inline void reverse(int x) {
swap(tr[x].s[0], tr[x].s[1]);
tr[x].flag ^= 1;
}
inline void pushdown(int x) {
if (tr[x].flag) {
if (tr[x].s[0]) reverse(tr[x].s[0]);
if (tr[x].s[1]) reverse(tr[x].s[1]);
}
tr[x].flag = 0;
}
inline void pushall(int x) {
if (ntroot(x)) pushall(tr[x].p);
pushdown(x);
}
inline void pushup(int x) {
tr[x].res = tr[tr[x].s[0]].res ^ tr[tr[x].s[1]].res ^ tr[x].val;
}
inline void rotate(int x) {
int y = tr[x].p, z = tr[y].p;
int k = tr[y].s[1] == x;
tr[x].p = z;
if (ntroot(y)) tr[z].s[tr[z].s[1] == y] = x;
tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
tr[y].p = x, tr[x].s[k ^ 1] = y;
pushup(y); pushup(x);
}
inline void splay(int x) {
pushall(x);
while (ntroot(x)) {
int y = tr[x].p, z = tr[y].p;
if (ntroot(y)) {
if ((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
else rotate(y);
}
rotate(x);
}
}
inline void access(int x) {
for (int y = 0; x; y = x, x = tr[x].p)
splay(x), tr[x].s[1] = y, pushup(x);
}
inline void makeroot(int x) {
access(x); splay(x); reverse(x);
}
inline int findroot(int x) {
access(x); splay(x);
while (tr[x].s[0]) {
pushdown(x);
x = tr[x].s[0];
}
splay(x);
return x;
}
inline void link(int x, int y) {
makeroot(x);
if (findroot(y) == x) return;
tr[x].p = y;
}
inline void cut(int x, int y) {
makeroot(x);
if (findroot(y) != x || tr[y].p != x || tr[y].s[0]) return;
tr[x].s[1] = tr[y].p = 0;
pushup(x);
}
inline void split(int x, int y) {
makeroot(x); access(y); splay(y);
}
int main() {
n = read(), m = read();
rep(i, 1, n) tr[i].val = read();
while (m --) {
int op = read(), x = read(), y = read();
if (!op) {
split(x, y);
printf("%d\n", tr[y].res);
} else if (op == 1) {
link(x, y);
} else if (op == 2) {
cut(x, y);
} else {
splay(x);
tr[x].val = y;
}
}
return 0;
}
模板题
P3690 【模板】动态树(LCT)
代码在上面
P1501 [国家集训队] Tree II
考虑运用线段树打懒标记的思路,对于每个 $Splay$ 结点维护 $val, mul, add, sum, flag, sz$,其中 $val$ 为结点的值,$mul$ 为乘的懒标记,$add$ 为加的懒标记,$sum$ 为子树的和,$flag$ 是翻转的懒标记,$sz$ 是子树的大小。
维护懒标记时先 $mul$ 再 $add$,原因可以自己列个式子算一算。
自我感觉马蜂挺良好的?
P4219 [BJOI2014] 大融合
$A$ 操作就是 $Link$,$Q$ 操作我们可以维护每个子树的 $sz$,$split(x, y)$ 后答案就是 $sz[x] * (sz[y] - sz[x])$,这样就做完了,吗?
由于 $LCT$ 有虚边和实边的分别,所以我们不能单纯地维护实边的 $sz$,我们还要加上虚边,所以我们可以再维护一个 $sz2$ 代表虚边的大小。然后 $pushup$ 要修改,并且会改变边的虚实关系的 $access$ 和 $link$ 中都要维护 $sz2$。
注意到 $link$ 中进行了修改增加了 $makeroot(y)$,因为如果直接连 $y$ 的祖先就爆了。
inline void pushup(int x) {
tr[x].sz = tr[tr[x].s[0]].sz + tr[tr[x].s[1]].sz + 1 + tr[x].sz2;
}
inline void access(int x) {
for (int y = 0; x; y = x, x = tr[x].p)
splay(x), tr[x].sz2 += tr[tr[x].s[1]].sz - tr[y].sz, tr[x].s[1] = y, pushup(x);
}
inline void link(int x, int y) {
makeroot(x); makeroot(y);
tr[y].sz2 += tr[x].sz, tr[y].sz += tr[x].sz;
tr[x].p = y;
}
其实解决这个问题的方式还有一种就是 $link$ 当不需要判断数据合法性时还有另一种写法,直接 $split(x, y)$ 然后这时 $x, y$ 相当于一个在链首,一个在链尾,这时候直接搞就不会出问题了。
inline void link(int x, int y) {
split(x, y);
tr[x].p = y;
}