题解 LuoGu P1471 方差

作者: MayFlyyh 分类: 线段树 发布时间: 2018-02-26 18:02 ė 6 没有评论

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

![image](http://www.mayflyyh.com/wp-content/uploads/2018/02/2264-1.png)

## 想法

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

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

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

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

\bar A 我们可以计算得出

“`math
(a- \bar A)^{2}=(a^{2}-2 \times a \times \bar A+\bar A^{2})

S^{2}=\frac{1}{n} \times ( \sum _ {i=l}^{r}a_{i}^{2}-2 \times \sum_{i=l}^{r}a_{i} \times \bar A+ (r-l+1) \times \bar A^{2} )

\sum_{i=l}^{r}a_{i}

\bar A

\sum _{i}=_ {2}a{i}

“`

故我们仅用再维护 \sum_{i=_ {2}a{i} 即可,即再维护一个平方和

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

代码如下:

“`cpp
#include
#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>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; } ```

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/62

发表评论

电子邮件地址不会被公开。

Ɣ回顶部