题解 LuoGu P1471 方差

• 题目描述
  蒟蒻HansBug在一本数学书里面发现了一个神奇的数列，包含N个实数。他想算算这个数列的平均数和方差。

• 输入格式：
  第一行包含两个正整数N、M，分别表示数列中实数的个数和操作的个数。

• 第二行包含N个实数，其中第i个实数表示数列的第i项。

• 接下来M行，每行为一条操作，格式为以下两种之一：

• 操作1：1 x y k ，表示将第x到第y项每项加上k，k为一实数。

• 操作2：2 x y ，表示求出第x到第y项这一子数列的平均数。

• 操作3：3 x y ，表示求出第x到第y项这一子数列的方差。

• 输出格式：
  输出包含若干行，每行为一个实数，即依次为每一次操作2或操作3所得的结果（所有结果四舍五入保留4位小数）。

想法

对于操作2 我们只用求出[x,y]区间的和然后除以该区间元素数量即可，由于平均值是随区间而不定的，所以我们无法利用线段树存储区间平均值，直接计算即可

对于操作3 我们需要算出区间每个元素减去区间平均值后平方，再求和，后除以元素数量

由于(a- \bar A)^{2}=(a^{2}-2_a_\bar A+\bar A^{2})

所以 S^{2}=\frac{1}{n} * ( \sum_{i=l}^{r}a_{i}^{2}-2_\sum_{i=l}^{r}a_{i}_\bar A+ (r-l+1) *\bar A^{2} )
其中 \sum_{i=l}^{r}a_{i} 为区间和，我们已经在求平均值的时候维护了

而\bar A 我们可以计算得出

故我们仅用再维护\sum_{i=l}^{2}a_{i}即可，即再维护一个平方和

而给a加上b，也可以通过该方法添加

代码如下：

#include<bits/stdc++.h> 
#define N 100021
double a[N],sum[N*4],cov[N*4];
double sum2[N*4];
int n,m;
inline void pushdown(int cur,int x){
    sum2[cur<<1]+=2*sum[cur<<1]*cov[cur]+cov[cur]*cov[cur]*(x+1>>1);
    sum2[cur<<1|1]+=2*sum[cur<<1|1]*cov[cur]+cov[cur]*cov[cur]*(x>>1);
    sum[cur<<1|1]+=(x>>1)*cov[cur];
    sum[cur<<1]+=(x+1>>1)*cov[cur];
    cov[cur<<1]+=cov[cur];
    cov[cur<<1|1]+=cov[cur];
    cov[cur]=0;
}
inline void pushup(int cur,int x){
    sum[cur]=sum[cur<<1]+sum[cur<<1|1];
    sum2[cur]=sum2[cur<<1]+sum2[cur<<1|1];
}
inline void add(int l,int r,int L,int R,double x,int cur){
    if(L<=l&&r<=R){
        sum2[cur]+=2*sum[cur]*x+x*x*(r-l+1);
        sum[cur]+=(r-l+1)*x;
        cov[cur]+=x;
        return ;
    }
    pushdown(cur,r-l+1);
    int mid=l+r>>1;
    if(L<=mid) add(l,mid,L,R,x,cur<<1);
    if(R>mid) add(mid+1,r,L,R,x,cur<<1|1);
    pushup(cur,r-l+1);
}
inline double ask(int l,int r,int L,int R,int cur,int od){
    if(L<=l&&r<=R&&od==1){
        return sum[cur];
    }
    if(L<=l&&r<=R&&od==2){
        return sum2[cur];
    }
    pushdown(cur,r-l+1);
    int mid=l+r>>1;double ans=0;
    if(L<=mid) ans+=ask(l,mid,L,R,cur<<1,od);
    if(mid<R) ans+=ask(mid+1,r,L,R,cur<<1|1,od);
    return ans;
} 
inline double askvar(int l,int r,int L,int R,int cur){
    double ans=0,x=0,y=0,z;
    x=ask(1,n,L,R,1,2),y=ask(1,n,L,R,1,1);
    z=(y*1.0)/((R-L+1)*1.0);
    ans=x-2*y*z+z*z*(R-L+1);
    return ans;
}
inline void build (int l,int r,int cur){
    if(l==r) {
        sum[cur]=a[l];
        sum2[cur]=a[l]*a[l];
        return ;
    }
    int mid=l+r>>1;
    build(l,mid,cur<<1);
    build(mid+1,r,cur<<1|1);
    pushup(cur,r-l+1);
}
int main (){
    scanf("%d %d ",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%lf",&a[i]);
    build(1,n,1);
    for(int i=1;i<=m;++i){
        int od,x,y;double z;
        scanf("%d",&od);
        if(od==1){
            scanf("%d %d %lf",&x,&y,&z);
            add(1,n,x,y,z,1);
        }
        if(od==2){
            scanf("%d %d",&x,&y);
            z=(1.0*ask(1,n,x,y,1,1))/(1.0*(y-x+1));
            printf("%.4lf\n",z);
        }
        if(od==3){
            scanf("%d %d",&x,&y);
            z=askvar(1,n,x,y,1)*1.0;
            z=(z*1.0)/(y-x+1);
            printf("%.4lf\n",z);
        }
    }
    return 0;
}