BZOJ4712洪水

永恒的一氧化碳大爷在讨论版里发了个单log的做法&＃xff0c;还没来得及看……

先写个链剖再说

考虑没有修改的情况&＃xff0c;我们可以树DP&＃xff0c;f[x]表示把x的子树截断的最小代价&＃xff0c;v[x]表示截断每个点的代价&＃xff0c;然后我们求出每个点的s[x]&＃xff0c;代表x的所有儿子节点的f之和&＃xff0c;f[x]就等于min(v[x],s[x])

考虑修改&＃xff0c;一次修改操作后&＃xff0c;v[x]会增加&＃xff0c;f[x]可能增加&＃xff0c;可能不变&＃xff0c;如果f[x]增加了d&＃xff0c;那么从x到根的一段路径上的点的s值和f值都会增加d&＃xff0c;直到第一个有v[x]-s[x]<&＃61;d的点&＃xff0c;即s[x]在加d之后会变得比v[x]大&＃xff0c;或原来v[x]就小于等于s[x]&＃xff0c;则f[x]不再等于s[x]&＃43;d&＃xff0c;而改为v[x]&＃xff0c;则增加量会改变一次&＃xff0c;我们继续对顶上的路径重复上述过程&＃xff0c;直到增加量为0或者到根

对于一次处理增加操作&＃xff0c;我们可以用链剖加线段树&＃xff0c;支持区间加和区间查询v[x]-s[x]的最小值&＃xff0c;在线段树上爬来找到第一个v[x]-s[x]<&＃61;d的点

由于修改操作的增加量是非负的&＃xff0c;并且每次只更改一个点&＃xff0c;所以至多有n&＃43;m次s[x]变得比v[x]大的时刻&＃xff0c;处理一个这样的时刻是O(log^2 n)的&＃xff0c;所以总复杂度O((n&＃43;m) log^2 n)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include