题解 P1471 【方差】

流逝丶

2019-09-18 21:58:03

Solution

**线段树维护平均数和方差** 平均数很好搞,维护区间和,然后除以区间长度就行了 那方差如何维护呢? 先得推一波式子 ![](https://cdn.luogu.com.cn/upload/image_hosting/xtzvd8lw.png) 然后发现我们维护一个区间和还有一个区间平方和就可以了 修改的时候先修改区间平方和,再修改区间和。 特别注意的:题目中说是实数,所以原序列中的数,和区间加的数都为小数,都要开double储存 printf输出double型为%f。 这题也就没什么了 附上代码 ```cpp #include<iostream> #include<cstdio> #define R register #define LL long long #define lson k<<1,l,mid //日常为了省码量和好看 #define rson k<<1|1,mid+1,r #define mid ((l+r)>>1) #define ls k<<1 #define rs k<<1|1 #define sum(rt) tr[rt].sum #define pf(rt) tr[rt].pf #define laz(rt) tr[rt].laz using namespace std; const int maxn=100005; int n,m; double a[maxn]; struct node{ double sum,pf,laz; }tr[maxn<<2]; inline int read(){ R int s=0,w=1; R char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();} return s*w; } inline void update(R int k){ sum(k)=sum(ls)+sum(rs); pf(k)=pf(ls)+pf(rs); } void build(R int k,R int l,R int r){ if(l==r){ sum(k)=a[l]; pf(k)=a[l]*a[l]; return ; } build(lson);build(rson); update(k); } inline void down(R int k,R int l,R int r){ pf(ls)=pf(ls)+2*laz(k)*sum(ls)+(mid-l+1)*laz(k)*laz(k); sum(ls)=sum(ls)+laz(k)*(mid-l+1); laz(ls)+=laz(k); pf(rs)=pf(rs)+2*laz(k)*sum(rs)+(r-mid)*laz(k)*laz(k); sum(rs)=sum(rs)+laz(k)*(r-mid); laz(rs)+=laz(k); laz(k)=0; } void change(R int k,R int l,R int r,R int x,R int y,double z){ if(l==x&&y==r){ pf(k)=pf(k)+2*z*sum(k)+(r-l+1)*z*z; sum(k)=sum(k)+z*(r-l+1); laz(k)+=z; return ; } if(laz(k))down(k,l,r); if(y<=mid)change(lson,x,y,z); else if(x>mid)change(rson,x,y,z); else change(lson,x,mid,z),change(rson,mid+1,y,z); update(k); } double ask1(R int k,R int l,R int r,R int x,R int y){ if(l==x&&y==r){ return sum(k); } if(laz(k))down(k,l,r); if(y<=mid)return ask1(lson,x,y); else if(x>mid)return ask1(rson,x,y); else return ask1(lson,x,mid)+ask1(rson,mid+1,y); } double ask2(R int k,R int l,R int r,R int x,R int y){ if(l==x&&y==r){ return pf(k); } if(laz(k))down(k,l,r); if(y<=mid)return ask2(lson,x,y); else if(x>mid)return ask2(rson,x,y); else return ask2(lson,x,mid)+ask2(rson,mid+1,y); } int main(){ n=read();m=read(); for(R int i=1;i<=n;++i) scanf("%lf",&a[i]); build(1,1,n); R int opt,x,y; double tot,ans,ans2,z; while(m--){ opt=read(); if(opt==1){ x=read();y=read(); scanf("%lf",&z); change(1,1,n,x,y,z); } else if(opt==2){ x=read();y=read(); tot=ask1(1,1,n,x,y)/(y-x+1); printf("%.4f\n",tot); } else if(opt==3){ x=read();y=read(); ans=ask1(1,1,n,x,y)/(y-x+1); ans2=ask2(1,1,n,x,y); tot=ans2/(y-x+1)-ans*ans; printf("%.4f\n",tot); } } return 0; } ```