Mayflyyh
Mayflyyh
MayFlyyh's Blog
题解 LuoGu P1471 方差

题解 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位小数)。

http://www.mayflyyh.com/wp-content/uploads/2018/02/2264-1.png

想法

对于操作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;
}   
本文链接:http://www.mayflyyh.com/archives/62
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      线段树      题解 LuoGu P1471 方差
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

Captcha Code

MayFlyyh's Blog

题解 LuoGu P1471 方差
题解 LuoGu P1471 方差 题目描述 蒟蒻HansBug在一本数学书里面发现了一个神奇的数列,包含N个实数。他想算算这个数列的平均数和方差。 输入格式: 第一行包含两个正整数N、M,分别表示…
扫描二维码继续阅读
2018-02-26