首先能想到的是,BBB 没有修改,直接前缀和就能做。
考虑线段树维护区间 Ai×BiA_i \times B_iAi ×Bi 。如何维护?
push_up 的时候,一样的,不写了;
push_down 的时候,式子如下:
∑i=lr(Ai+c)×Bi=∑i=lrAi×Bi+c×Bi=(∑i=lrAi×Bi)+(c∑i=lrBi)\sum_{i=l}^r (A_i+c) \times B_i \\ =\sum_{i=l}^r A_i \times B_i + c \times B_i \\ =(\sum_{i=l}^r A_i \times B_i) + (c\sum_{i=l}^r B_i) i=l∑r (Ai +c)×Bi =i=l∑r Ai ×Bi +c×Bi =(i=l∑r Ai ×Bi )+(ci=l∑r Bi )
加号前面是已知的,加号后面直接前缀和,O(1)O(1)O(1) 计算。
然后写完了。
Code: