专栏文章

CF925E

sshiruoyu114514
CF925E题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minalffh
此快照首次捕获于
2025/12/01 23:16
3 个月前
此快照最后确认于
2025/12/01 23:16
3 个月前
查看原文
给定一棵树，点有点权 tit_i，有颜色黑白，初始全白。
需要维护：单点翻转颜色，问有多少个白点内部有至少 ti+1t_i+1 个黑点。
n,m≤105n,m \le 10^5。
果断考虑分块。考虑建立 dfs 序之后维护 ai=tia_i=t_i 减去子树内黑点的个数。则修改可以直接转化为对一系列区间进行区间 −1/+1-1/+1，然后求全局 ≥0\ge 0 的点的个数。
对于整块而言，我们可以维护桶数组 ti,jt_{i,j} 为第 ii 个块内有多少个白点 pp 满足 ap=ja_p=j。这样在块内统一加的时候我们可以轻而易举地维护贡献变化量：只需要打一个偏移 tag 即可。散块直接暴力即可。
一个很有意思的分块：每条重链单独分块长为 len\sqrt {len} 的块，这样单次操作时间复杂度为 ∑n2i=(2+2)n\sum \limits \sqrt{\frac{n}{2^i}} = (2+\sqrt 2)\sqrt n。于是时间复杂度就来到了 O(mn)O(m \sqrt n)。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...