自动搬运

查看原文

来自洛谷，原作者为

	夏色祭 **

搬运于2025-08-24 21:34:15，当前版本为作者最后更新于2018-01-11 17:56:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

显然这题要用线段树搞。

平均数？

出门左拐线段树模板一再加个gcd就行了。

方差？

先说下这是个什么东西。

$\sum_{i=l}^{r}(a[i]-q)^2/(r-l+1)$ (q为这r-l+1个数的平均数)

就是上面那个式子。

显然我们不能直接搞。

考虑化简，运用完全平方公式把$(a[i]-q)^2$化开，得：

$\sum_{i=l}^{r}(a[i]^2-2*q*a[i]+q^2)/(r-l+1)$ (q为这r-l+1个数的平均数)

那么我们再用线段树维护下区间平方和就行了。

然后问题是平方和区间加怎么维护？

哎哎哎，别慌。。。

我们可以再用完全平方公式把$(a[i]+d)^2$化开来，得：

$a[i]^2+2*a[i]*d+d^2$

a[i]平方就是我们原先的答案，然后就加上 区间和*2*d 和 区间长度*d 就行了

具体还有些小细节，我就不一一说了。。

由于代码是在太长(4K+)我就不展示了。