线段树分治（更新）

左偏树/可并堆（更新）

重构树

2020牛客国庆集训派对

回文树

序列自动机

洛谷p3261

左偏树

给定一棵以 $1$ 为根的树，每个点拥有属性 $(h_i,a_i,v_i)$。同时给定 $m$ 个士兵，每个士兵初始时在 $s_i$ 号点，且拥有 $c_i$ 点生命。

当士兵 $i$ 处在点 $j$ 时，如果 $c_i\lt h_j$，则该士兵在该点死亡。

否则该士兵生命产生变化。具体得，如果 $a_i=0$ 则士兵生命增加 $v_i$，如果 $a_i=1$ 则士兵生命乘以 $v_i$。

如果士兵未死亡，则士兵通过当前结点且继续前往该结点的父节点。

询问每个结点死亡的士兵数和每个士兵最终通过的结点数。数据保证士兵任意时刻生命值不爆 $\text{long long}$ 且如果 $a_i=1$ 则 $v_i\gt 0$。

考虑 $\text{dfs}$ 遍历城市，左偏树合并子节点士兵信息，每次弹出堆顶所有 $c\lt h$ 的结点，同时更新答案。

对于修改操作，类似线段树懒标记处理即可。由于 $a_i=1$ 时保证 $v_i\gt 0$，所有结点的相对大小不改变，所有懒标记处理可以保证正确性。

合并操作总复杂度 $(n\log m)$，弹出操作总复杂度 $O(m\log m)$，修改操作总时间复杂度 $O(n)$。于是总时间复杂度 $O((n+m)\log m)$。

左偏树好题。