线段树 2

发布时间 2023-12-23 14:55:43作者: 最爱丁珰

由于有两个操作,我们要对乘法和加法设置一个优先级

我们来看看先乘后加,lazy2表示乘数,lazy1表示加数(前者初始值为\(1\),后者初始值为\(0\)

根据我们对lazy的理解,一个节点的和的真实值,为这个节点到根节点的路径中,对每一个节点依次先乘lazy2再加lazy1得到的最终结果

假设某一步时,和的中间结果为\(x\)

那么接下来,他就会变成\(y=x \cdot lazy_2+lazy_1\),再走一步就会变成\(z=y \cdot lazy_2^{'}+lazy_1^{'}=x \cdot lazy_2 \cdot lazy_2^{'}+lazy_1 \cdot lazy_2^{'}+lazy_1^{'}\)

所以在下传的时候,我们有\(lazy_2 \times = lazy_2^{'}\)\(lazy_1=lazy_1 \times lazy_2^{'}+lazy_1^{'}\)

具体可见洛谷提交代码

为什么先加后乘不行呢?

可以尝试一下按照上面的方法列式子,最终会列出来一个分数