洛谷——P1471 方差

P1471 方差

题目描述

蒟蒻HansBug在一本数学书里面发现了一个神奇的数列，包含N个实数。他想算算这个数列的平均数和方差。

借一下远航之曲大佬的图片，特别清晰：

那么只要维护区间平方和，就可以求方差了。

区间平方和，恩，push_down稍微改一下即可。

注意精度问题。

#include<bits/stdc++.h>

#define N int(1e6)

#define LL long long

using namespace std;

void in(LL &x) {

    register char c=getchar();

    x=;

    int f=;

    while(!isdigit(c)) {

        if(c=='-') f=-;

        c=getchar();

    }

    while(isdigit(c)) {

        x=x*+c-'';

        c=getchar();

    }

    x*=f;

}

struct node{

    LL l,r;

    double w1,w2,mul,ad;

}tr[N];

inline void push_up(int k){

    tr[k].w1=tr[k<<].w1+tr[k<<|].w1;

    tr[k].w2=tr[k<<].w2+tr[k<<|].w2;

}

inline void build(LL k,LL l,LL r){

    tr[k].l=l,tr[k].r=r;

    if(l==r) {

        scanf("%lf",&tr[k].w1);

        tr[k].w2=tr[k].w1*tr[k].w1;

        return;

    }

    LL mid=(l+r)>>;

    build(k<<,l,mid);

    build(k<<|,mid+,r);

    push_up(k);

}

inline void push_down(LL k){

    if(tr[k].ad){

        tr[k<<].w2+=tr[k<<].w1**tr[k].ad+(tr[k<<].r-tr[k<<].l+)*tr[k].ad*tr[k].ad;

        tr[k<<].w1+=tr[k].ad*(tr[k<<].r-tr[k<<].l+);

        tr[k<<].ad+=tr[k].ad;

        tr[k<<|].w2+=tr[k<<|].w1**tr[k].ad+(tr[k<<|].r-tr[k<<|].l+)*tr[k].ad*tr[k].ad;

        tr[k<<|].w1+=tr[k].ad*(tr[k<<|].r-tr[k<<|].l+);

        tr[k<<|].ad+=tr[k].ad;

        tr[k].ad=;

    }

}

inline void update(LL k,LL L,LL R,double w){

    int l=tr[k].l,r=tr[k].r,mid=(l+r)>>;

    if(l>=L&&r<=R){

        tr[k].w2+=tr[k].w1**w+(r-l+)*w*w;

        tr[k].w1+=w*(r-l+);

        tr[k].ad+=w;

        return;

    }

    push_down(k);

    if(L<=mid) update(k<<,L,R,w);

    if(R>mid) update(k<<|,L,R,w);

    push_up(k);

}

double query1(LL k,LL L,LL R){

    int l=tr[k].l,r=tr[k].r,mid=(l+r)>>;

    if(l>=L&&r<=R) return tr[k].w1;

    push_down(k);

    double an=;

    if(L<=mid) an+=query1(k<<,L,R);

    if(R>mid) an+=query1(k<<|,L,R);

    push_up(k);

    return an;

}

double query2(LL k,LL L,LL R){

    int l=tr[k].l,r=tr[k].r,mid=(l+r)>>;

    if(l>=L&&r<=R) return tr[k].w2;

    push_down(k);

    double an=;

    if(L<=mid) an+=query2(k<<,L,R);

    if(R>mid) an+=query2(k<<|,L,R);

    push_up(k);

    return an;

}

LL n,m;

int main()

{

    in(n),in(m);

    build(,,n);

    for(LL opt,l,r,i=;i<=m;i++){

        in(opt),in(l),in(r);

        if(opt==){

            double w;

            scanf("%lf",&w);

            update(,l,r,w);

        }

        if(opt==){

            printf("%.4lf\n",(double)query1(,l,r)/(r-l+));

        }

        if(opt==){

            double an=(double)query2(,l,r)/(r-l+)-(double)query1(,l,r)/(r-l+)*(double)query1(,l,r)/(r-l+);

            printf("%.4lf\n",an);

        }

    }

    return ;

}