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

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

1. 先读入所有实体¶

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

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

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

设 \(R_k(u)\) 为向上前 \(2^k\) 项、长度不足则补结束符的串的字典序秩。按二元组

\[ \left(R_{k-1}(u),R_{k-1}(\mathrm{up}[u][k-1])\right) \]

排序所有实体，相同二元组赋相同秩，不同二元组依次增加秩。由归纳，每层的秩同时精确反映相等性和字典序。结束符低于所有真实值，所以短串是其真扩展串的前缀时，短串排在前面。

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

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

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

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

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

创建树记录了每个实体真实且不变的祖先串。倍增归纳给出精确顺序与块相等性；重放保证叶集合准确；相邻串性质保证查询最大 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)\) .这里使用比较排序，没有声称线性的基数排序实现。

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