自动搬运

查看原文

来自洛谷，原作者为

	EnofTaiPeople MGXS

搬运于2025-08-24 22:12:56，当前版本为作者最后更新于2022-10-13 20:55:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Part1 前言

P5649 Sone1 是一个神奇的题，用 $25$ 个字概括：

链加链赋值，最值与求和，子树加赋值，最值与求和，换根换父亲。

可以认为是一道解法很多的开放题。

---

Part2 重工业理论与实现细节

$\text{LCT}$ 的原理是使用 splay 维护实路径，这样可以实现平摊 $O(\log n)$ 实现链修改，链查询。

为了对虚儿子进行维护，我们应当新开一个 splay 维护虚儿子，编号为 $x+n$。

每一个父亲记录其虚儿子 splay 的根节点，注意，只有 isroot(x)，$x+n$ 才有意义。

事实上，实路径和虚子树的 splay 可以共用，在实路径 splay 时，需要将原来的根节点从虚子树中删除，再将新的根节点插入，复杂度瓶颈就在此处。

这样来说，如果把虚子树根看作中儿子，这就是三度化的 $\text{SATT}$。

但我还是看不懂 $\text{SATT}$，由于找前驱后继无法平摊，所以时间为 $O(\log^2n)$。

用 $\text{SLT,splay-leafy-tree}$ 来维护虚儿子可以做到 $O(\log_2n)$ 的 access。

但这样无法共用 splay，码长要翻一倍，这也称为 $\text{AAAT}$。

重工业还有一个特点，把 tag 看作一次函数，将 dat 打包，省去了 addtag 和 pushdown 的分类讨论，进一步减小码量，当然这个也可以单纯地用矩阵乘法来理解。

具体实现要记录两个标记，表示链上修改和链外（虚子树）修改，还要记录三个数据，表示链上和，链外（虚子树）和，还有自己的值。

贴上评测链接。

---

Part3 从 $\text{AAAT}$ 理论到 $\text{SATT}$

显然，大多数大佬能看懂论文哥的文章。

但实现部分我是观察 AC 代码才理解的。

如果你只想学一种动态树而不愿意多做研究，那么只需要能理解 $\text{AAAT}$ 理论，那么你也能看懂 $\text{SATT}$ 的实现过程。

但在读下文前，请先将论文哥的文章先读三遍，可以大致理解一下 $\text{top-cluster}$ 理论。

上图是一棵树，加粗的点表示实儿子，这棵树所对应的 $\text{SATT}$ 如下图：

其中的 $r1,r2$ 表示 $\text{rake node}$，其余表示 $\text{compress node}$。

可以粗略理解为 $\text{compress node}$ 维护实链，$\text{rake node}$ 维护虚儿子。

但这里 $\text{rake node}$ 并没有和上方的 $\text{compress node}$ 失去联系，而成为了$\text{compress node}$ 的中儿子。

$\text{compress node}$ 在 pushdown 时需要加给子树的标记会传给中儿子。

$\text{rake node}$ 在 pushdown 时会给子树的两个标记都加上自己的标记。

注意 $\text{rake node}$ 只有一个标记，所以接受标记时也只有一个标记会用到。

可以简单理解成 $\text{rake node}$ 是维护虚子树的 $\text{SLT}$，但如果只有一个虚儿子，唯一的 $\text{rake node}$ 也会只有一个儿子。

任何时刻 $\text{rake node}$ 都不会有中儿子。

access 时只需要一次全局 pushdown，因为任何一个节点都可以一次经过 $\text{compress node}$ 和 $\text{rake node}$ 到达根簇。

遍历时只需要从根簇出发，遍历左右儿子和中儿子即可。

这样可以整体看作一棵大 splay，access 时间复杂度为均摊 $O(\log n)$。

由于只需要一次全局 pushdown，只有一棵树，常数相较 $\text{AAAT,LCT-ETT}$ 十分优秀，码量也很小。

---

Part4 其他做法

上面提到了两种做法是 $O(q\log^2n)$ 的：虚子树 $\text{LCT}$，$\text{LCT-ETT}$。

也有两种是 $O(q\log n)$ 的：$\text{AAAT}$ 和 $\text{SATT}$。

你会发现，它们都是基于 $\text{LCT}$ 的，所以时间复杂度都是均摊的。

假如你想要严格复杂度，甚至可持久化。

我们先考虑只要非暴力就行的方法。

注意：以下部分纯口胡，有错误可以直接指出。

• 每次打通最多增加 $O(\log n)$ 势能，所以可以每 $K$ 次操作重构，注意这里需要重链剖分建全局平衡二叉树。
• 于是重构复杂度为 $O(\dfrac{qn}K)$。
• 每次操作最多使用 $O(K\log n)$ 势能。
• 总复杂度为 $O(qK\log n+\dfrac{qn}K)$。
• 平衡一下取 $K=\sqrt{n\log n}$，总时间 $O(q\sqrt{n\log n})$。

否则你就不能使用势能了，而需要保证操作结束后保持严格重剖，具体地你需要将轻边抖落，重边连上，同时使用重量平衡树，注意这里使用 treap 做到期望复杂度会相对好写。

当然这个算法是暂时被我认为是考场不可写作的，注意 $\text{LCT}$ 和 $\text{SATT}$ 并不是。

---

Part5 后记

这道题可以被称作 $\text{Top Tree}$ 的简单应用，事实上静态时的 $\log$ 划分结构也是 $\text{Top Tree}$ 的良好性质，详见此文，于是这道题就真的成为 $\text{Top Tree}$ 的简单应用了。