网站开发外键,松江网站开发培训课程,上海做网站比较有名的公司,wordpress首页只显示摘要不要文章正题 题目大意
4个操作 单点修改#xff0c;区间修改#xff0c;区间求和#xff0c;区间求方差 方差为:∑(xi−ave)2n\frac{\sum(x_i-ave)^2}{n}n∑(xi−ave)2 aveaveave为平均值 解题思路
我们将方差的式子分解一下 ∑(xi−ave)2n\frac{\sum(x_i-ave)^2}{n}n∑(xi…正题 题目大意
4个操作 单点修改区间修改区间求和区间求方差 方差为:∑(xi−ave)2n\frac{\sum(x_i-ave)^2}{n}n∑(xi−ave)2 aveaveave为平均值 解题思路
我们将方差的式子分解一下 ∑(xi−ave)2n\frac{\sum(x_i-ave)^2}{n}n∑(xi−ave)2 ∑(xi2−2∗x∗aveave2)n\frac{\sum(x_i^2-2*x*aveave^2)}{n}n∑(xi2−2∗x∗aveave2) (∑xi2)−2∗(∑xi)∗aven∗ave2n\frac{(\sum x_i^2)-2*(\sum x_i)*aven*ave^2}{n}n(∑xi2)−2∗(∑xi)∗aven∗ave2 然后因为aveaveave可以用区间和求所以我们只需要多维护一个区间平方和 之后我们考虑如何快速计算对于一个区间所有数都加上valvalval之后的平方和 ∑(xival)2\sum (x_ival)^2∑(xival)2 我们将其分解 ∑(xi22∗xi∗valval2)\sum (x_i^22*x_i*valval^2)∑(xi22∗xi∗valval2) (∑xi2)(∑xi)∗2∗valn∗val2(\sum x_i^2)(\sum x_i)*2*valn*val^2(∑xi2)(∑xi)∗2∗valn∗val2 然后(∑xi2)(\sum x_i^2)(∑xi2)和(∑xi)(\sum x_i)(∑xi)我们都知道所以可以直接计算之后的平方和。 codecodecode
#includecstdio
#define N 100010
#define ll long long
#define lodu long double
using namespace std;
struct tree_node{ll l,r,w,ww,lazy;
}t[N2];
ll n,q;
lodu sum_f;
void build(ll k,ll l,ll r)//建树
{t[k].ll;t[k].rr;if(lr){scanf(%lld,t[k].w);t[k].wwt[k].w*t[k].w;return;}ll mid(lr)1;build(k*2,l,mid);build(k*21,mid1,r);t[k].wt[k*2].wt[k*21].w;t[k].wwt[k*2].wwt[k*21].ww;
}
void get_fan(ll k,ll z)//求区间加了z之后的区间平方和
{t[k].wwt[k].wwt[k].w*2*zz*z*(t[k].r-t[k].l1);}
void downdata(ll k){if(t[k].lazy0) return;get_fan(k*2,t[k].lazy);get_fan(k*21,t[k].lazy); t[k*2].wt[k].lazy*(t[k*2].r-t[k*2].l1);t[k*21].wt[k].lazy*(t[k*21].r-t[k*21].l1);t[k*2].lazyt[k].lazy;t[k*21].lazyt[k].lazy;t[k].lazy0;
}//下传lazy标记
void change(ll k,ll l,ll r,ll z)//区间修改
{if(t[k].llt[k].rr){get_fan(k,z);t[k].lazyz;t[k].wz*(r-l1);return;}downdata(k);if(rt[k*2].r) change(k*2,l,r,z);else if(lt[k*21].l) change(k*21,l,r,z);else change(k*2,l,t[k*2].r,z),change(k*21,t[k*21].l,r,z);t[k].wwt[k*2].wwt[k*21].ww;t[k].wt[k*2].wt[k*21].w;
}
ll get_sum(ll k,ll l,ll r)//区间求和和平方和
{if(t[k].llt[k].rr){sum_ft[k].ww;return t[k].w;}downdata(k);if(rt[k*2].r) return get_sum(k*2,l,r);if(lt[k*21].l) return get_sum(k*21,l,r);return get_sum(k*2,l,t[k*2].r)get_sum(k*21,t[k*21].l,r);
}
int main()
{//freopen(data.in,r,stdin);//freopen(data.out,w,stdout);scanf(%lld%lld,n,q);build(1,1,n);for(ll i1;iq;i){ll ts,a,b,z;scanf(%lld%lld%lld,ts,a,b);if(ts0) change(1,a,a,b);else if(ts1){scanf(%lld,z);change(1,a,b,z);}else if(ts2) sum_f0,printf(%lld\n,get_sum(1,a,b));else{sum_f0;lodu ave,ans,sumget_sum(1,a,b),nb-a1;avesum/n;anssum_fave*ave*n-sum*ave*2; printf(%0.10Lf\n,ans/n);}}
}
