P10147 题解 (2)

zjy2008 · 2025-02-12 11:26:30 · 题解

口胡一下，感谢 @chenxinyang2006 的指导。

本题事实上存在 1log 做法。考虑类似 天动万象 的，我们可以知道先先扫描 t，把树随便剖一下，每次进行 O(叶子数) 个单点修改和 O(叶子数) 个链向上 shift 即可维护出全部信息，考虑把所有还剩下 \neq 1 个儿子的节点建出虚树并维护出链信息和，那么查询可以被拆成 1 次虚树上链查询信息， O(1) 次平衡树上查询和 O(1) 次已删除节点信息查询。显然，每一轮在 O(叶子数) 个操作后会删去所有叶子，所以总时间复杂度是 O((n+q)\log n) 的，空间是线性的。

代码太难写，咕了。