P5314 [Ynoi2011] ODT

· · 题解

我永远喜欢数据结构

题目传送门

  • 给出 n 个点的树和 q 次操作，点有点权，操作有两种类型：

不会全局平衡二叉树，但是两只 \log 跑得快。

重链剖分，考虑用树状数组维护点权的差分数组，用平衡树求第 y 小的点权。

考虑对于每个点维护其所有轻儿子的点权的平衡树，查询时暴力插入 / 删除父亲、重儿子以及它本身。

那么对于一次路径修改，只有路径上重链顶端的父亲的平衡树会受到修改。

所以每次先树状数组路径加，然后删除这些平衡树上原来的点权，插入新的点权即可。

时间复杂度为 \mathcal{O}(q\log ^2 n)，空间复杂度为 \mathcal{O}(n)。用了 pbds::tree，代码特别好写。

AC 记录

代码