LCT 和线段树分裂

· · 算法·理论

以弹飞绵羊为例，经典做法是 LCT。

考虑插入标记回收。问题在于带修，因此需要考虑时间维，值在时间轴上覆盖一段区间，总数是 O(n+m) 的。具体地，考虑离线，从左到右扫描，维护 n 棵动态开点线段树，下标为时间，一个询问挂在第 x 棵树上表示这个询问当前跳到的装置为 x。扫描到 x 时，将第 x 棵树 split 成若干个区间，分别 merge 到相应的父亲上，顺便打一个 +1 的 tag。代码没写。

这个做法有没有应用呢？我不知道，本来想造个例题，但线段数 树分裂好像几乎被 LCT 偏序了。

考虑用 LCT 解决线段树分裂模板题，其实就是上面那个反过来。扫描值，用 LCT 维护一棵树，u 连向 f_u 表示当前在第 u 个可重集的数会被放入第 f_u 个可重集。操作 0 需要新开两个可重集，x 和 y+1 时父亲会变动，操作 1 需要新开一个可重集，连两个儿子，操作 2 就是到根链修改，操作 3 可以拓展到一般半群查询，x 时将询问对应节点路径上的 tag 都 pushdown，清空这个节点上的信息，y 时查询即可，对于操作 4 维护 k-当前和，如果最小值 \le 0 就递归找到询问并解决。代码没写。

上述论述均建立在离线的基础上，需要交换下标维和时间维，在此基础上对比一下 LCT 和线段树分裂：

LCT：功能较强大，上述问题只是一个应用。

线段树分裂：只能处理根向树且需要节点有顺序，只能解决不会 LCT 的问题。

发现二者都是均摊，可能冥冥之中自有关系。