# 动态路径独立性：离线倍增排序

**沿用出题人的反转路径和相邻串性质。GPT-6 用离线倍增排序得到精确全局顺序，减少操作阶段的比较和有序映射存储。**

## 1. 先读入所有实体

按输入顺序模拟节点存在性，每次插入分配新内部编号，记录其父亲和值。把每个操作中的外部编号转换为当时的内部编号。删除子树用显式栈处理，编号再用时对应另一个实体。

此后整份输入曾出现过的节点形成一棵不再改变的“创建树”：每个实体始终指向创建时的父实体。它包含不同时刻存在过的节点，只用于祖先字符串；执行操作时仍必须检查实体是否存活。

## 2. 倍增得到精确字典序

反转串从当前节点沿父链到根。使用值加一作为长度一的秩；空祖先使用秩零，表示比任何真实值更小的结束符。

设 $R_k(u)$ 为向上前 $2^k$ 项、长度不足则补结束符的串的字典序秩。按二元组
$$
\left(R_{k-1}(u),R_{k-1}(\mathrm{up}[u][k-1])\right)
$$
排序所有实体，相同二元组赋相同秩，不同二元组依次增加秩。由归纳，每层的秩同时精确反映相等性和字典序。结束符低于所有真实值，所以短串是其真扩展串的前缀时，短串排在前面。

倍增长度达到最大根路径长度后，最终秩就是整个反转串的顺序。实现做到 $2^{17}$ ，覆盖最多 $100001$ 个节点的路径。实体编号用于打破相同字符串的平局，不影响字典序结论。

## 3. 重放操作

以 $(\text{最终秩},\text{内部编号})$ 作为叶集合的有序键。

插入时，父亲原来是叶子就将它移除，再加入新叶子。删除子树时，逐个删除其中仍存活的叶子，必要时把子树外的父亲重新加入。使用内部编号防止复用外部编号混淆实体。重放开始时只有根活着，未来才插入的节点不能参加查询。

查询只比较当前叶子的前驱、后继。原因是具有固定前缀的串在字典序中连续，任何较远候选的公共前缀都被相邻候选覆盖。

求两节点的 LCP 时，从大到小查看倍增秩；只在两条剩余路径长度都至少为块长时比较并跳过相同块。这样不会把补的结束符算进答案。完整相同路径、单个叶子和最后删除根均自然处理。

## 4. 正确性与复杂度

创建树记录了每个实体真实且不变的祖先串。倍增归纳给出精确顺序与块相等性；重放保证叶集合准确；相邻串性质保证查询最大 LCP 正确。因此结果与逐条执行题意一致。

设总实体数为 $N\le q+1$ .每层排序耗时 $O(N\log N)$ ，共 $O(\log N)$ 层；操作集合比较只比较整数秩，插入、删除和查询分别耗时 $O(\log N)$ ，LCP 也为 $O(\log N)$ .每个实体至多删除一次，所以总时间为
$$
O(N\log^2 N+q\log N),
$$
空间为 $O(N\log N+q)$ .这里使用比较排序，没有声称线性的基数排序实现。

该方案必须预读输入；[在线方案](solution.zh.md)可边读边答。离线方案减少有序映射的分配开销，并在当前大范围压力数据中使用较少内存。两者都可通过完整范围。

[计算程序](alternative-offline.cpp)。