luoguP1471 方差

题目背景

滚粗了的HansBug在收拾旧数学书，然而他发现了什么奇妙的东西。

题目描述

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

输入输出格式

输入格式：

第一行包含两个正整数N、M，分别表示数列中实数的个数和操作的个数。

第二行包含N个实数，其中第i个实数表示数列的第i项。

接下来M行，每行为一条操作，格式为以下两种之一：

操作1：1 x y k ，表示将第x到第y项每项加上k，k为一实数。

操作2：2 x y ，表示求出第x到第y项这一子数列的平均数。

操作3：3 x y ，表示求出第x到第y项这一子数列的方差。

输出格式：

输出包含若干行，每行为一个实数，即依次为每一次操作2或操作3所得的结果（所有结果四舍五入保留4位小数）。

输入输出样例

输入样例#1：

5 5
1 5 4 2 3
2 1 4
3 1 5
1 1 1 1
1 2 2 -1
3 1 5

输出样例#1：

3.0000
2.0000
0.8000

说明

样例说明：

数据规模：

显然这样的区间问题并不支持直接查询。。

把平均数变成 区间和/区间长

方差变成 区间平方和+2*区间和*平均数+平均数*平均数*区间长

单次修改 对平方和的影响就是2*区间和*增加数+增加数*增加数*区间长

代码;

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=100000+10;
double summ[maxn*4],suma[maxn*4];
double A[maxn];
double addv[maxn*4];
int ql,qr;
inline void pushdown(int o,int l,int r){
    if(addv[o]){
        int mid=(l+r)>>1;
        addv[o<<1]+=addv[o];
        suma[o<<1]+=summ[o<<1]*addv[o]*2+addv[o]*addv[o]*(mid-l+1);
        summ[o<<1]+=(mid-l+1)*addv[o];
        addv[o<<1|1]+=addv[o];
        suma[o<<1|1]+=summ[o<<1|1]*addv[o]*2+addv[o]*addv[o]*(r-mid);
        summ[o<<1|1]+=(r-mid)*addv[o];
        addv[o]=0;
    }
}
inline void add(int o,int l,int r,double x){
    if(l>=ql&&r<=qr){
        addv[o]+=x;
        suma[o]+=summ[o]*x*2+x*x*(r-l+1);
        summ[o]+=x*(r-l+1);
        return ;
    }
    else if(l!=r){
        pushdown(o,l,r);
        int mid=(l+r)>>1;
        if(ql<=mid)
            add(o<<1,l,mid,x);
        if(qr>mid)
            add(o<<1|1,mid+1,r,x);
        summ[o]=summ[o<<1]+summ[o<<1|1];
        suma[o]=suma[o<<1]+suma[o<<1|1];
    }
}
inline double query1(int o,int l,int r){
    if(l>=ql&&r<=qr)
        return summ[o];
    else if(l!=r){
        pushdown(o,l,r);
        int mid=(l+r)>>1;
        double ans=0;
        if(ql<=mid)
            ans+=query1(o<<1,l,mid);
        if(qr>mid)
            ans+=query1(o<<1|1,mid+1,r);
        return ans;
    }
    return 0;
}
inline double query2(int o,int l,int r){
    if(l>=ql&&r<=qr)
        return suma[o];
    else if(l!=r){
        pushdown(o,l,r);
        int mid=(l+r)>>1;
        double ans=0;
        if(ql<=mid)
            ans+=query2(o<<1,l,mid);
        if(qr>mid)
            ans+=query2(o<<1|1,mid+1,r);
        return ans;
    }
    return 0;
}
inline void build(int o,int l,int r){
    if(l==r){
        summ[o]=A[l];
        suma[o]=A[l]*A[l];
        return ;
    }
    else {
        int mid=(l+r)>>1;
        build(o<<1,l,mid);
        build(o<<1|1,mid+1,r);
        summ[o]=summ[o<<1]+summ[o<<1|1];
        suma[o]=suma[o<<1]+suma[o<<1|1];
    }
}
int main(){
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lf",&A[i]);
    build(1,1,n);
    int opt;
    double z;
    for(int i=1;i<=m;i++){
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d %d %lf",&ql,&qr,&z);
            add(1,1,n,z);
        }
        else if(opt==2){
            scanf("%d %d",&ql,&qr);
            double x=query1(1,1,n);
            printf("%.4lf\n",x/(qr-ql+1));
        }
        else {
            scanf("%d %d",&ql,&qr);
            double x=query1(1,1,n);
            double y=query2(1,1,n);
            double d=x/(qr-ql+1);
            printf("%.4lf\n",(y-2*d*x+d*d*(qr-ql+1))/(qr-ql+1));
        }
    }
return 0;
}