AC日记——方差 洛谷 P1471

时间:2021-06-16 21:08:55

方差

思路:

  线段树;

代码:

#include <bits/stdc++.h>
using namespace std;
#define maxn 100005
struct TreeNodeType {
int l,r,mid,size;
double sum,sum2,flag;
inline void updata(double x)
{
flag+=x;
sum2+=sum*x*+size*x*x;
sum+=x*size;
}
};
struct TreeNodeType tree[maxn<<];
int n,m;
double X,Sum,Sum2;
inline void in(int &now)
{
int if_z=;now=;
char Cget=getchar();
while(Cget>''||Cget<'')
{
if(Cget=='-') if_z=-;
Cget=getchar();
}
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
now*=if_z;
}
void build(int now,int l,int r)
{
tree[now].l=l,tree[now].r=r,tree[now].size=r-l+;
if(l==r)
{
scanf("%lf",&tree[now].sum);
tree[now].sum2=tree[now].sum*tree[now].sum;
return;
}
tree[now].mid=l+r>>;
build(now<<,l,tree[now].mid);
build(now<<|,tree[now].mid+,r);
tree[now].sum=tree[now<<].sum+tree[now<<|].sum;
tree[now].sum2=tree[now<<].sum2+tree[now<<|].sum2;
}
inline void pushdown(int now)
{
tree[now<<].updata(tree[now].flag);
tree[now<<|].updata(tree[now].flag);
tree[now].flag=;
}
void operation1(int now,int l,int r)
{
if(tree[now].l>=l&&tree[now].r<=r)
{
tree[now].updata(X);
return;
}
if(tree[now].flag) pushdown(now);
if(l<=tree[now].mid) operation1(now<<,l,r);
if(r>tree[now].mid) operation1(now<<|,l,r);
tree[now].sum=tree[now<<].sum+tree[now<<|].sum;
tree[now].sum2=tree[now<<].sum2+tree[now<<|].sum2;
}
void operation2(int now,int l,int r)
{
if(tree[now].l>=l&&tree[now].r<=r)
{
Sum+=tree[now].sum;
Sum2+=tree[now].sum2;
return;
}
if(tree[now].flag) pushdown(now);
if(l<=tree[now].mid) operation2(now<<,l,r);
if(r>tree[now].mid) operation2(now<<|,l,r);
}
int main()
{
in(n),in(m),build(,,n);
int op,l,r;
while(m--)
{
in(op),in(l),in(r);
if(op==) scanf("%lf",&X),operation1(,l,r);
if(op==) Sum=,operation2(,l,r),printf("%.4lf\n",Sum/(r-l+));
if(op==)
{
Sum=,Sum2=;
operation2(,l,r);
X=Sum/(r-l+);
printf("%.4lf\n",(Sum2-Sum*X*+(r-l+)*X*X)/(r-l+));
}
}
return ;
}