「题解」方差

(未完待续)

题目链接:Luogu P1471

题解

思路

方差的计算公式为:

$$ s ^ {2} = \frac {1} {n} \sum ^ {n} _ {i=1} {(A _ {i} – \bar {x}) ^ 2} $$

这是线段树裸题。

代码

该算法的渐进时间复杂度为 $ \Theta (n \log _ {2} n) $ 。

#include<cstdio>
#include<cmath>
#include<iostream>
using std::cin;
#define reg register
const int MAXN=100000+5;
struct SegmentTree{
    #define lson (k<<1)
    #define rson (k<<1|1)
    #define mid ((l+r)>>1)
    struct Node{
        double val1,val2,tag;
        inline Node(void){
            val1=val2=tag=0;
            return;
        }
        inline Node(reg double a,reg double b,reg double c){
            val1=a,val2=b,tag=c;
            return;
        }
    };
    Node unit[MAXN<<2];
    inline void pushup(reg int k){
        unit[k].val1=unit[lson].val1+unit[rson].val1;
        unit[k].val2=unit[lson].val2+unit[rson].val2;
        return;
    }
    inline void Add(reg int k,reg int l,reg int r,reg double val){
        unit[k].val2+=2*val*unit[k].val1+(r-l+1)*val*val;
        unit[k].val1+=(r-l+1)*val;
        unit[k].tag+=val;
        return;
    }
    inline void pushdown(reg int k,reg int l,reg int r){
        if(unit[k].tag){
            Add(lson,l,mid,unit[k].tag);
            Add(rson,mid+1,r,unit[k].tag);
            unit[k].tag=0;
        }
        return;
    }
    inline void Build(reg int k,reg int l,reg int r,reg double a[]){
        if(l==r){
            unit[k]=Node(a[l],a[l]*a[l],0);
            return;
        }
        Build(lson,l,mid,a);
        Build(rson,mid+1,r,a);
        pushup(k);
        return;
    }
    inline void Update(reg int k,reg int l,reg int r,reg int L,reg int R,reg double val){
        if(L<=l&&r<=R){
            Add(k,l,r,val);
            return;
        }
        pushdown(k,l,r);
        if(L<=mid)
            Update(lson,l,mid,L,R,val);
        if(R>mid)
            Update(rson,mid+1,r,L,R,val);
        pushup(k);
        return;
    }
    inline double Query1(reg int k,reg int l,reg int r,reg int L,reg int R){
        if(L<=l&&r<=R)
            return unit[k].val1;
        pushdown(k,l,r);
        reg double res=0;
        if(L<=mid)
            res+=Query1(lson,l,mid,L,R);
        if(R>mid)
            res+=Query1(rson,mid+1,r,L,R);
        return res;
    }
    inline double Query2(reg int k,reg int l,reg int r,reg int L,reg int R){
        if(L<=l&&r<=R)
            return unit[k].val2;
        reg double res=0;
        pushdown(k,l,r);
        if(L<=mid)
            res+=Query2(lson,l,mid,L,R);
        if(R>mid)
            res+=Query2(rson,mid+1,r,L,R);
        return res;
    }
    #undef lson
    #undef rson
    #undef mid
};
int n,m;
double a[MAXN];
SegmentTree T;
int main(void){
    reg int i;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)
        scanf("%lf",&a[i]);
    T.Build(1,1,n,a);
    while(m--){
        static int opt,x,y;
        static double k;
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d%d%lf",&x,&y,&k);
            T.Update(1,1,n,x,y,k);
        }
        if(opt==2){
            scanf("%d%d",&x,&y);
            printf("%.4f\n",T.Query1(1,1,n,x,y)/(y-x+1));
        }
        if(opt==3){
            scanf("%d%d",&x,&y);
            k=T.Query1(1,1,n,x,y)/(y-x+1);
            printf("%.4f\n",T.Query2(1,1,n,x,y)/(y-x+1)-k*k);
        }
    }
    return 0;
}