题解 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位小数)。
想法
对于操作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;
}
本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。
本文永久链接: http://www.mayflyyh.com/archives/62