【BZOJ 4712】洪水

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4712
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/6006305.html
神犇题解Ⅱ:http://blog.csdn.net/lych_cys/article/details/53454323

解题报告

考虑每一个节点保存三个值

  1. $w(i)$ 表示第i个点自己的权值
  2. $f(i) = \sum\limits_{j \in son(i)} {d(j)} $
  3. $d(i) = \min (w(i),f(i))$

显然 $d(i)$ 就是答案
于是我们只需要考虑维护 $f(i)$ 即可

考虑每一次修改操作
其一定是改变了到根节点的路径上连续一个区间的 $f(i)$
这个连续的区间满足 $f(i) + delta < w(i)$ 于是可以直接用树链剖分搞区间加就可以了

现在考虑复杂度:

因为 $f(i)$ 是不减的,所以如果一个点的 $f(i)$ 大于了 $w(i)$ 那么便会一直大下去
初始每一个点会贡献一次暴力修改,每一次修改操作也会贡献一次暴力修改

于是均摊下来,单次操作的暴力修改次数就是 $O(1)$ 的了
于是总复杂度:$O((n+m)log^2n)$

2 thoughts to “【BZOJ 4712】洪水”

  1. I have not checked in here for some time because I thought it was getting boring, but the last several posts are great quality so I guess I will add you back to my daily bloglist. You deserve it my friend 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *