OI线段树

做了几题思维难度并不算太高的线段树题目,难点就是有巨巨巨多细节要注意.

luoguP6327:https://www.luogu.com.cn/problem/P6327

题意:每次修改一个点,求区间sin值的和
区间sin和的信息不可加,但可以考虑和差化积公式,

$$sin(x+v)=sin(x)cos(v)+sin(v)cos(x) cos(x+v)=cos(x)cos(v)-sin(x)sin(v)$$

同时记录cos和sin值就可以转化为线段树求和.
由于节点的tag不能直接和子节点的和相加,需要注意每次询问时先下放标签.还有浮点运算的常数极大,下放时先判一下0,不然很容易tle.

luoguP1471:https://www.luogu.com.cn/problem/P1471

题意:每次修改一个点,求区间平均数和方差
首先是平均数的合并$a_3=(a_1n_1+a_2n_2)/(n_1+n_2)$
再考虑方差的更改,每次修改时可以$O(1)$的更新

$$D_1=\frac 1n\Sigma(x_i-a_1)^2\\ D_2=\frac 1n\Sigma(x_i+v-a_2)^2\\ D_2-D_1=\frac 1n\Sigma((x_i+v-a_2)^2-(x_i-a_1)^2)\\ =\frac 1n\Sigma(v^2+a_2^2+2x_iv-2a_2v-2a_2x_i-a_1^2+2x_ia_1)\\ =v^2+a_2^2-a_1^2-2a_2v+(2v-2a_2+2a_1)\frac 1n \Sigma x_i\\ =v^2+a_2^2-a_1^2-2a_2v+2a_1v-2a_1a_2+2a_1^2\\ =a_1^2+a_2^2+v^2+2a_1v-2a_2v-2a_1a_2$$

最后是方差的合并

$$D_1=\frac 1{n_1}\Sigma(x_1i-a_1)^2\\ D_2=\frac 1{n_2}\Sigma(x_2i-a_2)^2\\ D_3=\frac 1{n_1+n_2}\Sigma(x_i-a_3)^2\\ (n_1+n_2)D_3-D_1n_1-D_2n_2=\Sigma((x_i-a_3)^2-(x_i-a_j)^2)(j=1,2)\\ =\Sigma(a_3^2-a_j^2+2x_i(a_j-a_3))\\ =n_1(a_3^2-a_1^2)+2n_1a_1(a_1-a_3)\\ +n_2(a_3^2-a_2^2)+2n_2a_2(a_2-a_3)$$

最后特别要注意在合并方差时跨中点情况的判断,左右两段的长度应该取min(当前区间长度,询问区间长度)