蒟蒻HansBug在一本数学书里面发现了一个神奇的数列,包含N个实数。他想算算这个数列的平均数和方差。
——by 洛谷;
http://www.luogu.org/problem/show?pid=1471
平均数可以用线段树,维护区间和,直接维护平均数也行;
然后对于方差;她有个公式的:
S=[(a-Z)²+(b-Z)²+(c-Z)²+(d-Z)²+(e-Z)²...]/n(Z为平均数)
S=[区间平方和-2*n*平均数²+n*平均数²]/n;
S=[区间平方和-n*平均数²]/n;
所以维护个平方和就好了;
然后,平方和怎么区间加呢?
她也有个公式:
(a+z)²+(b+z)²+(c+z)²+(d+z)²+(e+z)²(你把她拆开嘛。。)
=以前平方和+(2z*(Z*n)+n*z²);
然后是代码解释,
我只打了一个Lazy,意为在该区间的子树上要区间加,然后两个线段树共用;
因为平方和修改要用区间平均数未修改的值,故两树同步修改,先改平方和;
代码如下:
#include<cstdio>
#include<iostream>
using namespace std;
double treen[];
double treen1[];
double lz[];
int n,m,R,L;
double a; void build(int ,int ,int );
void add(int ,int ,int );
double sum( int ,int ,int );
double sum1(int ,int ,int );
void down(int ,int ,int ); int main()
{
int i,j,b;
double ans,k;
scanf("%d%d",&n,&m);
build(,n,);
for(i=;i<=m;i++)
{
scanf("%d",&b);
if(b==)
{
scanf("%d%d",&L,&R);
cin>>a;
add(,n,);
}
if(b==)
{
scanf("%d%d",&L,&R);
ans=sum(,n,)/(R-L+);
printf("%.4lf\n",ans);
}
if(b==)
{
scanf("%d%d",&L,&R);
ans=sum(,n,)/(R-L+);
ans=ans*ans;
k=sum1(,n,);
ans=k/(R-L+)-ans;
printf("%.4lf\n",ans);
}
}
} void build(int l,int r,int nu)
{
if(l==r)
{
scanf("%lf",&treen[nu]);
treen1[nu]=treen[nu]*treen[nu];
return ;
}
int mid=(l+r)>>;
build(l,mid,nu<<);
build(mid+,r,(nu<<)+);
treen[nu]=(treen[nu<<]*(mid-l+)+treen[(nu<<)+]*(r-mid))/(r-l+1.0);
treen1[nu]=treen1[nu<<]+treen1[(nu<<)+];
} void add(int l,int r,int nu)
{
if(L<=l&&r<=R)
{
lz[nu]+=a;
treen1[nu]+=(r-l+)*(a**treen[nu]+a*a);
treen[nu]+=a;
return ;
}
int mid=(l+r)>>;
down(l,r,nu);
if(L<=mid)
add(l,mid,nu<<);
if(R>=mid+)
add(mid+,r,(nu<<)+);
treen[nu]=(treen[nu<<]*(mid-l+)+treen[(nu<<)+]*(r-mid))/(r-l+1.0);
treen1[nu]=treen1[nu<<]+treen1[(nu<<)+];
} double sum(int l,int r,int nu)
{
double su=;
if(L<=l&&r<=R)
{
return treen[nu]*(r-l+);
}
int mid=(l+r)>>;
down(l,r,nu);
if(L<=mid)
su+=sum(l,mid,nu<<);
if(R>=mid+)
su+=sum(mid+,r,(nu<<)+);
return su;
} double sum1(int l,int r,int nu)
{
double su=;
if(L<=l&&r<=R)
{
return treen1[nu];
}
int mid=(l+r)>>;
down(l,r,nu);
if(L<=mid)
su+=sum1(l,mid,nu<<);
if(R>=mid+)
su+=sum1(mid+,r,(nu<<)+);
return su;
} void down(int l,int r,int nu)
{
int mid=(l+r)>>;
lz[nu<<]+=lz[nu];
lz[(nu<<)+]+=lz[nu];
treen1[nu<<]+=(mid-l+)*(*treen[nu<<]*lz[nu]+lz[nu]*lz[nu]);
treen1[(nu<<)+]+=(r-mid)*(*treen[(nu<<)+]*lz[nu]+lz[nu]*lz[nu]);
treen[nu<<]+=lz[nu];
treen[(nu<<)+]+=lz[nu];
lz[nu]=;
}
//5 5
//1 1 1 1 1
//1 2 2 -1
//3 1 5
祝AC哟;