[SDOI2016]游戏题解

思路

显然需要树链剖分。

对于每一个 \(a \times dis + b\) 的操作,向懒惰标记里添加。如果碰上已经有懒惰信息,那么我们只需要把这样的操作理解为加上直线,把直线下边缘下传到左右子节点即可。(计算长度进行左右决策下传)对于每一个节点,懒惰加法为等差数列求和,计算 \(b \times subtreeSize + a \times \frac{subtreeSize*(subtreeSize-1)}{2}\)。

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注