CF925E

shiruoyu114514 · 2025-11-10 19:27:35 · 题解

给定一棵树，点有点权 t_i，有颜色黑白，初始全白。

需要维护：单点翻转颜色，问有多少个白点内部有至少 t_i+1 个黑点。

果断考虑分块。考虑建立 dfs 序之后维护 a_i=t_i 减去子树内黑点的个数。则修改可以直接转化为对一系列区间进行区间 -1/+1，然后求全局 \ge 0 的点的个数。

对于整块而言，我们可以维护桶数组 t_{i,j} 为第 i 个块内有多少个白点 p 满足 a_p=j。这样在块内统一加的时候我们可以轻而易举地维护贡献变化量：只需要打一个偏移 tag 即可。散块直接暴力即可。

一个很有意思的分块：每条重链单独分块长为 \sqrt {len} 的块，这样单次操作时间复杂度为 \sum \limits \sqrt{\frac{n}{2^i}} = (2+\sqrt 2)\sqrt n。于是时间复杂度就来到了 O(m \sqrt n)。