首页 > 代码库 > 洛谷P1471 方差
洛谷P1471 方差
蒟蒻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，意为在该区间的子树上要区间加，然后两个线段树共用；
代码如下：
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 double treen[1000001]; 5 double treen1[1000001]; 6 double lz[1000001]; 7 int n,m,R,L; 8 double a; 9 10 void build(int ,int ,int ); 11 void add(int ,int ,int ); 12 double sum( int ,int ,int ); 13 double sum1(int ,int ,int ); 14 void down(int ,int ,int ); 15 16 int main() 17 { 18 int i,j,b; 19 double ans,k; 20 scanf("%d%d",&n,&m); 21 build(1,n,1); 22 for(i=1;i<=m;i++) 23 { 24 scanf("%d",&b); 25 if(b==1) 26 { 27 scanf("%d%d",&L,&R); 28 cin>>a; 29 add(1,n,1); 30 } 31 if(b==2) 32 { 33 scanf("%d%d",&L,&R); 34 ans=sum(1,n,1)/(R-L+1); 35 printf("%.4lf\n",ans); 36 } 37 if(b==3) 38 { 39 scanf("%d%d",&L,&R); 40 ans=sum(1,n,1)/(R-L+1); 41 ans=ans*ans; 42 k=sum1(1,n,1); 43 ans=k/(R-L+1)-ans; 44 printf("%.4lf\n",ans); 45 } 46 } 47 } 48 49 void build(int l,int r,int nu) 50 { 51 if(l==r) 52 { 53 scanf("%lf",&treen[nu]); 54 treen1[nu]=treen[nu]*treen[nu]; 55 return ; 56 } 57 int mid=(l+r)>>1; 58 build(l,mid,nu<<1); 59 build(mid+1,r,(nu<<1)+1); 60 treen[nu]=(treen[nu<<1]*(mid-l+1)+treen[(nu<<1)+1]*(r-mid))/(r-l+1.0); 61 treen1[nu]=treen1[nu<<1]+treen1[(nu<<1)+1]; 62 } 63 64 void add(int l,int r,int nu) 65 { 66 if(L<=l&&r<=R) 67 { 68 lz[nu]+=a; 69 treen1[nu]+=(r-l+1)*(a*2*treen[nu]+a*a); 70 treen[nu]+=a; 71 return ; 72 } 73 int mid=(l+r)>>1; 74 down(l,r,nu); 75 if(L<=mid) 76 add(l,mid,nu<<1); 77 if(R>=mid+1) 78 add(mid+1,r,(nu<<1)+1); 79 treen[nu]=(treen[nu<<1]*(mid-l+1)+treen[(nu<<1)+1]*(r-mid))/(r-l+1.0); 80 treen1[nu]=treen1[nu<<1]+treen1[(nu<<1)+1]; 81 } 82 83 double sum(int l,int r,int nu) 84 { 85 double su=0; 86 if(L<=l&&r<=R) 87 { 88 return treen[nu]*(r-l+1); 89 } 90 int mid=(l+r)>>1; 91 down(l,r,nu); 92 if(L<=mid) 93 su+=sum(l,mid,nu<<1); 94 if(R>=mid+1) 95 su+=sum(mid+1,r,(nu<<1)+1); 96 return su; 97 } 98 99 double sum1(int l,int r,int nu)100 {101 double su=0;102 if(L<=l&&r<=R)103 {104 return treen1[nu];105 }106 int mid=(l+r)>>1;107 down(l,r,nu);108 if(L<=mid)109 su+=sum1(l,mid,nu<<1);110 if(R>=mid+1)111 su+=sum1(mid+1,r,(nu<<1)+1);112 return su;113 }114 115 void down(int l,int r,int nu)116 {117 int mid=(l+r)>>1;118 lz[nu<<1]+=lz[nu];119 lz[(nu<<1)+1]+=lz[nu];120 treen1[nu<<1]+=(mid-l+1)*(2*treen[nu<<1]*lz[nu]+lz[nu]*lz[nu]);121 treen1[(nu<<1)+1]+=(r-mid)*(2*treen[(nu<<1)+1]*lz[nu]+lz[nu]*lz[nu]);122 treen[nu<<1]+=lz[nu];123 treen[(nu<<1)+1]+=lz[nu];124 lz[nu]=0;125 }126 //5 5127 //1 1 1 1 1128 //1 2 2 -1129 //3 1 5
祝AC;
洛谷P1471 方差
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。