题解 P2122 【还教室】

· · 题解

显然这题要用线段树搞。

平均数？

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

方差？

先说下这是个什么东西。

就是上面那个式子。 显然我们不能直接搞。 考虑化简，运用完全平方公式把$(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+)我就不展示了。