题解 P1471 【方差】

IzumiSagiri

2018-11-15 19:29:26

题解

我们可以设

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;
}