快速做网站联系电话/深圳网络营销和推广方案

题目大意

给出N个数，Q个操作

1、t=0时，两个数a,b 表示第a个数加b
2、t=1时，三个数a,b,c 表示a~b都加c
3、t=2时，两个数a,b 表示a~b的数字和
4、t=3时，两个数a,b 表示a~b的数字的方差

方差的定义：
求N个数的方差，设这N个数的平均数为ave，第i个数为x_i
方差=1/n[(x₁-ave)²+(x₂-ave)²+⋯+(x_(n-1)-ave)²+(x_n-ave)²]

题目解析

一看到题目，点修改和区间修改，很明显的时线段树

当t=2时，求区间和，也是线段树的常规做法

当t=3时，需要求区间方差

那我们可以试着把方差的计算公式拆分开

首先，方差=1/n[(x₁-ave)²+(x₂-ave)²+⋯+(x_(n-1)-ave)²+(x_n-ave)²]，我们先不考虑前面的1/n

得：[(x₁-ave)²+(x₂-ave)²+⋯+(x_(n-1)-ave)²+(x_n-ave)²]

由完全平方公式，拆开可得:
[(x₁²+2 *x₁*ave+ave²) + (x₂²+2 *x₂*ave+ave²) + ⋯ + (x_n-1²+2 *x_n-1*ave+ave²) + (x_n²+2 *x_n*ave+ave²)]

化简可得:
(x₁²+x₂²+⋯+x_n-1²+x_n²) + (n*ave²) + 2 * ave * (x₁+x₂+⋯+x_n-1+x_n)

由此可得：
我们求了区间的平方和，以及数字和，就可以很快的求出这个区间的方差

代码

#include<bits/stdc++.h>
using namespace std;
long long n,q,a1,a2,a3,a4,x,y,S,w,P;
double ave,ans;
int a[100005];
struct A
{long long l,r,w,f,p;
}sum[4000005];
void down(int k)
{sum[k*2].f+=sum[k].f;sum[k*2+1].f+=sum[k].f;sum[k*2].p+=(sum[k*2].r-sum[k*2].l+1)*sum[k].f*sum[k].f+2*sum[k].f*sum[k*2].w;sum[k*2+1].p+=((sum[k*2+1].r-sum[k*2+1].l+1)*sum[k].f*sum[k].f+2*sum[k].f*sum[k*2+1].w);sum[k*2].w+=sum[k].f*(sum[k*2].r-sum[k*2].l+1);sum[k*2+1].w+=sum[k].f*(sum[k*2+1].r-sum[k*2+1].l+1);sum[k].f=0;
}//懒标记 
void add(int k)
{if(sum[k].l>=x&&sum[k].r<=y){sum[k].p+=((sum[k].r-sum[k].l+1)*w*w+2*w*sum[k].w);sum[k].w+=(sum[k].r-sum[k].l+1)*w;sum[k].f+=w;return;}if(sum[k].f) down(k);int m=(sum[k].l+sum[k].r)/2;if(x<=m) add(k*2);if(y>m) add(k*2+1);sum[k].w=sum[k*2].w+sum[k*2+1].w;sum[k].p=sum[k*2].p+sum[k*2+1].p;
}//更新区间和以及平方和 
void find(int rt)
{if(sum[rt].l>=x&&sum[rt].r<=y) {S+=sum[rt].w;return;}if(sum[rt].f) down(rt);int mid=(sum[rt].l+sum[rt].r)/2;if(x<=mid) find(rt*2);if(y>mid) find(rt*2+1);
}//询问区间和 
long long find2(int t)
{if (sum[t].l>=x&&sum[t].r<=y)return sum[t].p;if(sum[t].f) down(t);long long mid=(sum[t].l+sum[t].r)/2,result=0;if(x<=mid) result+=find2(t*2);if(y>mid) result+=find2(t*2+1);return result;
}//询问平方和 
void build(int l,int r,int rt)
{sum[rt].l=l;sum[rt].r=r;if (l==r) {sum[rt].w=a[l];sum[rt].p=sum[rt].w*sum[rt].w;return;}int m=(l+r)>>1;build(l,m,rt*2);build(m+1,r,rt*2+1);sum[rt].w=sum[rt*2].w+sum[rt*2+1].w;sum[rt].p=sum[rt*2].p+sum[rt*2+1].p;
}//建树 
int main()
{cin>>n>>q;for(int i=1;i<=n;i++)cin>>a[i];build(1,n,1);for(int i=1;i<=q;i++){cin>>a1;if(a1==0){cin>>a2>>a4;x=y=a2;w=a4;add(1);	}if(a1==1){cin>>a2>>a3>>a4;x=a2;y=a3;w=a4;add(1);}if(a1==2){cin>>a2>>a3;x=a2;y=a3;S=0;find(1);cout<<S<<endl;}if(a1==3){cin>>a2>>a3;x=a2;y=a3;S=P=0;find(1);long long num=y-x+1;double ave=(double)S/num;P=find2(1);double ans=(double)P-(double)2*ave*S+ave*ave*num;cout<<fixed<<setprecision(10)<<(double)ans/num<<endl;}}
}