正文

洛谷P1471 方差

IP云
IP云V管理员/2 阅读
06/22
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

蒟蒻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哟;