更好的阅读体验

题目描述

蒟蒻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

解题报告

题意理解

1. 区间加一个实数
2. 区间求平均数
3. 区间求方差

算法解析

首先我们来推倒公式。

先拿出方差公式
$$ S^2 = \frac{1}{n} * [(x_1 - \overline{x})^2 + (x_2 - \overline{x})^2 + …+(x_n - \overline{x})^2 ] $$
根据完全平方公式：
$$ (a + b)^2 = a^2 + 2ab + b^2 $$
因此带入参数进去
$$ (x_1-\overline{x})^2=x_1^2+2x\overline{x}+\overline{x}^2 $$
接着处理公式
$$ S^2 = \frac{1}{n} * ({x_1}^2 - 2{x_1}\overline{x} + {\overline{x}^2} + {x_2}^2 - 2{x_2}\overline{x} + {\overline{x}^2} + … + {x_n}^2 - 2{x_n}\overline{x} + {\overline{x}^2}) $$
然后稍微整理一下
$$ S^2 = \frac{1}{n} * [({x_1}^2 + {x_2}^2 + … + {x_n}^2)-2\overline{x}(x_1 + x_2 + …+x_n) + n\overline{x}^2] $$
然后我们通过平均数公式可得
$$ n\overline{x} = x_1 + x_2 + … + x_n $$
将上面公式，导入方差公式
$$ S^2 = \frac{1}{n} * [({x_1}^2 + {x_2}^2 + … + {x_n}^2)-2n\overline{x}^2 + n\overline{x}^2] $$
代入后
$$ S^2 = \frac{1}{n} * [({x_1}^2 + {x_2}^2 + … + {x_n}^2)-n\overline{x}^2] $$
因此我们得出了最后的公式
$$ S^2 = \frac{({x_1}^2 + {x_2}^2 + … + {x_n}^2)}{n} - \overline{x}^2 $$
接着我们着重分析分子部分。
$$ x_1^2+x_2^2+\dots+x_k^2 \\\\ $$
现在所有数增加$b$，则
$$ (x_1+b)^2+(x_2+b)^2+\dots +(x_k+b)^2 \\\\ $$
然后定义一下
$$ 令sum1=x_1+x_2+\dots+x_k \\\\ 令sum2=x_1^2+x_2^2+\dots+x_k^2 \\\\ $$
由之前的完全平方公式可得:
$$ (x_i+b)^2=x_i^2+2 \times x_i \times b+b^2\\\\ $$
然后带入之前的部分
$$ (x_1^2+x_2^2+\dots+x_k^2)+2b \times (x_1+x_2+\dots+x_k)+(b^2 \times k) \\\\ $$
最后载入定义
$$ sum2+2b \times sum1+b^2 \times k \\\\ $$
我们终于终于终于将公式打完了。。。。。。

现在我们就可以通过，线段树来维护本题目了。

1. 维护平方和
2. 维护区间和

请注意，在这里，我们肯定是要开两个$Lazy$标记的；。

但是要记住平方和的懒惰标记，是绝对高于区间和的懒惰标记。

因为，通过公式可得，平方和的修改，是要先使用区间和的。

如果说先修改区间和，那么平方和的修改必然出现问题。

代码解释

#include <bits/stdc++.h>
using namespace std;
#define Lson rt<<1,l,mid
#define Rson rt<<1 | 1,mid+1,r
#define mid  (l+r>>1)
#define len  (r-l+1)
const int N=1e5+20;
int n,m;
struct node
{
    double lazy,sum;
} t1[N<<2],t2[N<<2];
double a[N];
inline void Push_up(int rt)
{
    t1[rt].sum=t1[rt<<1].sum+t1[rt<<1 | 1].sum;
    t2[rt].sum=t2[rt<<1].sum+t2[rt<<1 | 1].sum;
}
void build(int rt,int l,int r)
{
    if (l==r)
    {
        t1[rt].sum=a[l];
        t2[rt].sum=a[l]*a[l];
        return;
    }
    build(Lson);
    build(Rson);
    Push_up(rt);
}
inline void Push_down(int rt,int l,int r)
{
    if (!(t1[rt].lazy || t2[rt].lazy))
        return ;
    t2[rt<<1].lazy+=t2[rt].lazy;
    t2[rt<<1].sum+=t1[rt<<1].sum*(t2[rt].lazy*2)+(mid-l+1)*(t2[rt].lazy*t2[rt].lazy);
    t2[rt<<1 | 1].lazy+=t2[rt].lazy;
    t2[rt<<1 | 1].sum+=t1[rt<<1 | 1].sum*(t2[rt].lazy*2)+(r-mid)*(t2[rt].lazy*t2[rt].lazy);
    t2[rt].lazy=0;
    t1[rt<<1].lazy+=t1[rt].lazy;
    t1[rt<<1].sum+=(mid-l+1)*t1[rt].lazy;
    t1[rt<<1 | 1].lazy+=t1[rt].lazy;
    t1[rt<<1 | 1].sum+=(r-mid)*t1[rt].lazy;
    t1[rt].lazy=0;
}
double Query(int rt,int l,int r,int L,int R,int x)
{
    if (L<=l && r<=R)
        return x==1 ? t1[rt].sum:t2[rt].sum;
    double ans=0;
    Push_down(rt,l,r);
    if (L<=mid)
        ans+=Query(Lson,L,R,x);
    if (R>mid)
        ans+=Query(Rson,L,R,x);
    return ans;
}
void Update(int rt,int l,int r,int L,int R,double v)
{
    if (L<=l && r<=R)
    {
        t2[rt].lazy+=v;
        t2[rt].sum+=t1[rt].sum*(v*2)+len*(v*v);
        t1[rt].lazy+=v;
        t1[rt].sum+=len*v;
        return ;
    }
    Push_down(rt,l,r);
    if (L<=mid)
        Update(Lson,L,R,v);
    if (R>mid)
        Update(Rson,L,R,v);
    Push_up(rt);
}
inline void init()
{
//  freopen("data.in","r",stdin);
//  freopen("a.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        scanf("%lf",&a[i]);
    build(1,1,n);
    while(m--)
    {
        int x,a,b;
        scanf("%d%d%d",&x,&a,&b);
        if (x==1)
        {
            double c;
            scanf("%lf",&c);
            Update(1,1,n,a,b,c);
        }
        if (x==2)
            printf("%.4lf\n",Query(1,1,n,a,b,1)/((b-a+1)*1.0));
        if (x==3)
        {
            double cnt=(b-a+1)*1.0;
            double ans=Query(1,1,n,a,b,2)/cnt,x_ba=Query(1,1,n,a,b,1)/cnt;
            double ans2=x_ba*x_ba;
            ans-=ans2;
            printf("%.4lf\n",ans);
        }
    }
}
signed main()
{
    init();
    return 0;
}

@墨染空 大佬之前点名的线段树区间平方修改来了