luogu 1471

时间:2023-03-08 16:41:27

题意:

蒟蒻HansBug在一本数学书里面发现了一个神奇的数列,包含N个实数。他想算算这个数列的平均数和方差。

操作1:1 x y k ,表示将第x到第y项每项加上k,k为一实数。

操作2:2 x y ,表示求出第x到第y项这一子数列的平均数。

操作3:3 x y ,表示求出第x到第y项这一子数列的方差。

数据范围:n,m<=1e5

链接:

https://www.luogu.org/problemnew/show/1471

题解:

是一个不错的数学化简的问题,加上线段树的经典问题

首先来看方差的计算公式((x1-a)^2+(x2-a)^2+....) -----------还有个/n先不管

展开得到(x1^2+x2^2+......-2a(x1+x2+.....)+...*a*a)

显然,a是可以由维护区间和来得到,x1+x2+...即维护区间和

问题就在于x1^2+x2^2.....了

这是个线段树的经典问题

假设当前平方和为sum

则区间加上a后平方和变为: (x1+a)^2+(x2+a)^2+.......=x1^2+x2^2+.....+...*a*a+2a*(x1+x2+....)=sum+后面那串

这就很好维护了,只需知道那段和就可以了

但注意,不要将求和和求平方和分开求(这样求那段和就需要logn 总复杂度为nlognlogn)

如果两者同时进行,就可以在(nlogn)内完成

代码: