题解 P1471 【方差】

我们可以设 $ sum1[n]=a[1]+a[2]+\cdots+a[n] $ $ sum2[n]=a[1]^{2}+a[2]^{2}+\cdots+a[n]^{2} $ 那么我们就可以表示出方差了 #### 方差公式展开： $ \frac {\sum_{i=1}^{n} (a[i]-\overline{a})^{2} } {n} $ $ = \frac {(a[1]-\overline{a})^{2} + (a[2]-\overline{a})^{2} + \cdots +(a[n]-\overline{a})^{2} } {n} $ $ = \frac{a[1]^{2} + a[2]^{2} + \cdots +a[n]^{2}- 2 \overline{a}(a[1] + a[2] + \cdots +a[n] ) +n\overline{a}^{2} }{n} $ $ = \frac{a[1]^{2} + a[2]^{2} + \cdots +a[n]^{2} }{n} - 2\overline{a} \frac{a[1]+a[2]+\cdots+a[n]}{n}+\overline{a}^{2} $ $ = \frac{a[1]^{2} + a[2]^{2} + \cdots +a[n]^{2} }{n} - 2\overline{a}^{2}+\overline{a}^{2} $ $ = \frac{a[1]^{2} + a[2]^{2} + \cdots +a[n]^{2} }{n} - \overline{a}^{2} $ $ = \frac{sum2[n]}{n} - \overline{a}^{2} $ 至于修改也很简单了 #### 区间加展开： $ \sum_{i=1}^{n} (a[i]+x)^{2} $ $ = (a[1]+x)^{2} + (a[2]+x)^{2} + \cdots +(a[n]+x)^{2} $ $ = a[1]^{2} + a[2]^{2} + \cdots +a[n]^{2}+ 2 x(a[1] + a[2] + \cdots +a[n] ) +nx^{2} $ $ = sum2[n]+ 2 x $ $sum1[n] +nx^{2} $ 于是就可以用带lazy的线段树来解决 ###### *注意：优先级应该是要先处理sum2，再处理sum1 丑陋的代码如下: ``` #include<cstdio> #define ll long long #define lc(x) (x<<1) #define rc(x) (x<<1|1) const ll maxn=100000; double sum1[(maxn<<2)+5],sum2[(maxn)<<2+5]; double lazy[(maxn<<2)+5]; inline void pushup(ll v){ sum1[v]=sum1[lc(v)]+sum1[rc(v)]; sum2[v]=sum2[lc(v)]+sum2[rc(v)]; } inline void pushdown(ll v,ll l,ll r){ if(lazy[v]){ ll mid=l+r>>1; lazy[lc(v)]+=lazy[v]; lazy[rc(v)]+=lazy[v]; sum2[lc(v)]+=2.0*lazy[v]*sum1[lc(v)]+(mid-l+1)*lazy[v]*lazy[v]; sum2[rc(v)]+=2.0*lazy[v]*sum1[rc(v)]+(r-mid)*lazy[v]*lazy[v]; sum1[lc(v)]+=lazy[v]*(mid-l+1); sum1[rc(v)]+=lazy[v]*(r-mid); lazy[v]=0; } } void update(ll v,ll l,ll r,ll left,ll right,double add){ if(left<=l&&r<=right){lazy[v]+=add,sum2[v]+=2.0*sum1[v]*add+(r-l+1)*add*add,sum1[v]+=add*(r-l+1);return;} ll mid=l+r>>1; pushdown(v,l,r); if(left<=mid)update(lc(v),l,mid,left,right,add); if(right>mid)update(rc(v),mid+1,r,left,right,add); pushup(v); } double query_a(ll v,ll l,ll r,ll left,ll right){ if(left<=l&&r<=right){return sum1[v];} ll mid=l+r>>1;double ans=0; pushdown(v,l,r); if(left<=mid)ans+=query_a(lc(v),l,mid,left,right); if(right>mid)ans+=query_a(rc(v),mid+1,r,left,right); return ans; } double query_b(ll v,ll l,ll r,ll left,ll right){ if(left<=l&&r<=right){return sum2[v];} ll mid=l+r>>1;double ans=0; pushdown(v,l,r); if(left<=mid)ans+=query_b(lc(v),l,mid,left,right); if(right>mid)ans+=query_b(rc(v),mid+1,r,left,right); return ans; } ll n,m; int main(){ scanf("%lld%lld",&n,&m); for(ll i=1;i<=n;i++){ double p;scanf("%lf",&p); update(1,1,n,i,i,p); } for(ll i=1;i<=m;i++){ ll op,l,r;scanf("%lld%lld%lld",&op,&l,&r); if(op==1){ double k;scanf("%lf",&k); update(1,1,n,l,r,k); } if(op==2){ double ans=(double)query_a(1,1,n,l,r)/(r-l+1); printf("%.4lf\n",(double)ans); } if(op==3){ double ans=(double)query_a(1,1,n,l,r)/(r-l+1); double ans1=(double)query_b(1,1,n,l,r)/(r-l+1); double ans2=(double)ans1-(double)ans*ans; printf("%.4lf\n",(double)ans2); } } return 0; } ```