题解 P1471 【方差】
博客传送门
这道题要求两个值，一个是平均值，一个是方差，平均值很容易，就是区间和/个数就可以了。但是怎么求方差呢？看上去十分困难,不知道如何下手,不知道怎么维护？但是不妨把方差的公式拆开：
设平均数为k
则S²=((a1-k)²+(a2-k)²+(a3-k)²+...+(an-k)²)/n(将他拆开) =(a1²+a2²+a3²+...+an²+nk²-2k(a1+a2+a3+...+an)(/n ∵ (a1+a2+a3+...+an)/n=k
∴ S²=(a1²+a2²+a3²+...+an²)/n-k²
所以现在显而易见要维护方差只要维护平方的和就可以了 那么怎么维护平方和呢？
在拆开一下：
设每个数加上了x
(a1+x)²+(a2+x)²+(a3+x)²+...+(an+x)²
=a1²+a2²+a3²+...+an²+nx²+2x(a1+a2+a3+...+an)
所以现在就很容易了，接下来上代码
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
struct node {
double lazy,v,sqr;
} a[400001];
double b[400001];
void pushup(int k) {
a[k].v=a[k<<1].v+a[k<<1|1].v;
a[k].sqr=a[k<<1].sqr+a[k<<1|1].sqr;
}
void add(int k,int l,int r,double v) {
a[k].lazy+=v;
a[k].sqr+=((r-l+1)*v*v+2*v*a[k].v);
a[k].v+=(r-l+1)*v;
}
void pushdown(int k,int l,int r) {
if(a[k].lazy) {
int mid=(l+r)>>1;
add(k<<1,l,mid,a[k].lazy);
add(k<<1|1,mid+1,r,a[k].lazy);
}
a[k].lazy=0;
}
void update(int k,int l,int r,int begin,int end,double c) {
if(r<begin||l>end)
return ;
if(l>=begin&&r<=end) {
add(k,l,r,c);
return;
}
pushdown(k,l,r);
int mid=(l+r)>>1;
update(k<<1,l,mid,begin,end,c);
update(k<<1|1,mid+1,r,begin,end,c);
pushup(k);
}
double find(int k,int l,int r,int begin,int end) {
if(r<begin||l>end)
return 0;
if(l>=begin&&r<=end)
return a[k].v;
pushdown(k,l,r);
int mid=(l+r)>>1;
if(end<=mid)
return find(k<<1,l,mid,begin,end);
else if(begin>mid)
return find(k<<1|1,mid+1,r,begin,end);
else
return find(k<<1,l,mid,begin,mid)+find(k<<1|1,mid+1,r,mid+1,end);
}
double find1(int k,int l,int r,int begin,int end) {
if(r<begin||l>end)
return 0;
if(l>=begin&&r<=end)
return a[k].sqr;
pushdown(k,l,r);
int mid=(l+r)>>1;
if(end<=mid)
return find1(k<<1,l,mid,begin,end);
else if(begin>mid)
return find1(k<<1|1,mid+1,r,begin,end);
else
return find1(k<<1,l,mid,begin,mid)+find1(k<<1|1,mid+1,r,mid+1,end);
}
void build(int k,int l,int r) {
a[k].lazy=0;
if(l==r) {
a[k].v=b[l];
a[k].sqr=b[l]*b[l];
return ;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
pushup(k);
}
int main() {
int n,m,L,x,y;
double c;
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
scanf("%lf",&b[i]);
build(1,1,n);
for(int i=1; i<=m; i++) {
scanf("%d%d%d",&L,&x,&y);
if(L==1) {
scanf("%lf",&c);
update(1,1,n,x,y,c);
}
if(L==2)
printf("%0.4lf\n",find(1,1,n,x,y)*1.0/(y-x+1));
if(L==3) {
double ans=find(1,1,n,x,y)*1.0/(y-x+1);
ans*=ans;
printf("%0.4lf\n",(find1(1,1,n,x,y)*1.0/(y-x+1))-ans);
}
}
}
```egin,int end,double c) {
if(r<begin||l>end)
return ;
if(l>=begin&&r<=end) {
add(k,l,r,c);
return;
}
pushdown(k,l,r);
int mid=(l+r)>>1;
update(k<<1,l,mid,begin,end,c);
update(k<<1|1,mid+1,r,begin,end,c);
pushup(k);
}
double find(int k,int l,int r,int begin,int end) {
if(r<begin||l>end)
return 0;
if(l>=begin&&r<=end)
return a[k].v;
pushdown(k,l,r);
int mid=(l+r)>>1;
if(end<=mid)
return find(k<<1,l,mid,begin,end);
else if(begin>mid)
return find(k<<1|1,mid+1,r,begin,end);
else
return find(k<<1,l,mid,begin,mid)+find(k<<1|1,mid+1,r,mid+1,end);
}
double find1(int k,int l,int r,int begin,int end) {
if(r<begin||l>end)
return 0;
if(l>=begin&&r<=end)
return a[k].sqr;
pushdown(k,l,r);
int mid=(l+r)>>1;
if(end<=mid)
return find1(k<<1,l,mid,begin,end);
else if(begin>mid)
return find1(k<<1|1,mid+1,r,begin,end);
else
return find1(k<<1,l,mid,begin,mid)+find1(k<<1|1,mid+1,r,mid+1,end);
}
void build(int k,int l,int r) {
a[k].lazy=0;
if(l==r) {
a[k].v=b[l];
a[k].sqr=b[l]*b[l];
return ;
}
int mid=(l+r)>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
pushup(k);
}
int main() {
int n,m,L,x,y;
double c;
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
scanf("%lf",&b[i]);
build(1,1,n);
for(int i=1; i<=m; i++) {
scanf("%d%d%d",&L,&x,&y);
if(L==1) {
scanf("%lf",&c);
update(1,1,n,x,y,c);
}
if(L==2)
printf("%0.4lf\n",find(1,1,n,x,y)*1.0/(y-x+1));
if(L==3) {
double ans=find(1,1,n,x,y)*1.0/(y-x+1);
ans*=ans;
printf("%0.4lf\n",(find1(1,1,n,x,y)*1.0/(y-x+1))-ans);
}
}
}