AC日记——方差 洛谷 P1471

方差

思路：

　　线段树；

代码：

#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 ;

}