P1471 方差 题解

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

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

输入格式
第一行包含两个正整数?
�
,
�
N,M，分别表示数列中实数的个数和操作的个数。

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

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

操作?
1
1：1 x y k ，表示将第?
�
x 到第?
�
y 项每项加上?
�
k，
�
k 为一实数。
操作?
2
2：2 x y ，表示求出第?
�
x 到第?
�
y 项这一子数列的平均数。
操作?
3
3：3 x y ，表示求出第?
�
x 到第?
�
y 项这一子数列的方差。

输出格式
输出包含若干行，每行为一个实数，即依次为每一次操作?
2
2 或操作?
3
3 所得的结果（所有结果四舍五入保留?
4
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
说明/提示
关于方差：对于一个有?
�
n 项的数列?
�
A，其方差?
�
2
s?
2
? 定义如下：

�
2
=
1
�
∑
�
=
1
�
(
�
�
?
�
￣
)
2
s?
2
?=?
n
1
?
??
i=1
∑
n
?
?(A?
i
?
???
A
?)?
2
?

其中?
�
￣
A
? 表示数列?
�
A 的平均数，
�
�
A?
i
?
? 表示数列?
�
A 的第?
�
i 项。

样例说明：

操作步骤?? ?输入内容?? ?操作要求?? ?数列?? ?输出结果?? ?说明
0
0?? ?-?? ?-?? ?1 5 4 2 3?? ?-?? ?-
1
1?? ?2 1 4?? ?求?
[
1
,
4
]
[1,4] 内所有数字的平均数?? ?1 5 4 2 3?? ?3.0000?? ?平均数?
=
(
1
+
5
+
4
+
2
)
÷
4
=
3.0000
=(1+5+4+2)÷4=3.0000
2
2?? ?3 1 5?? ?求?
[
1
,
5
]
[1,5] 内所有数字的方差?? ?1 5 4 2 3?? ?2.0000?? ?平均数?
=
(
1
+
5
+
4
+
2
+
3
)
÷
5
=
3
=(1+5+4+2+3)÷5=3，方差?
=
(
(
1
?
3
)
2
+
(
5
?
3
)
2
+
(
4
?
3
)
2
+
(
2
?
3
)
2
+
(
3
?
3
)
2
)
÷
5
=
2.0000
=((1?3)?
2
?+(5?3)?
2
?+(4?3)?
2
?+(2?3)?
2
?+(3?3)?
2
?)÷5=2.0000
3
3?? ?1 1 1 1?? ?将?
[
1
,
1
]
[1,1] 内所有数字加?
1
1?? ?2 5 4 2 3?? ?-?? ?-
4
4?? ?1 2 2 -1?? ?将?
[
2
,
2
]
[2,2] 内所有数字加?
?
1
?1?? ?2 4 4 2 3?? ?-?? ?-
5
5?? ?3 1 5?? ?求?
[
1
,
5
]
[1,5] 内所有数字的方差?? ?2 4 4 2 3?? ?0.8000?? ?平均数?
=
(
2
+
4
+
4
+
2
+
3
)
÷
5
=
3
=(2+4+4+2+3)÷5=3，方差?
=
(
(
2
?
3
)
2
+
(
4
?
3
)
2
+
(
4
?
3
)
2
+
(
2
?
3
)
2
+
(
3
?
3
)
2
)
÷
5
=
0.8000
=((2?3)?
2
?+(4?3)?
2
?+(4?3)?
2
?+(2?3)?
2
?+(3?3)?
2
?)÷5=0.8000
数据规模：

数据点?? ?
�
N?? ?
�
M?? ?备注
1
～
3
1～3?? ?
�
≤
8
N≤8?? ?
�
≤
15
M≤15?? ?-
4
～
7
4～7?? ?
�
≤
1
0
5
N≤10?
5
??? ?
�
≤
1
0
5
M≤10?
5
??? ?不包含操作?
3
3
8
～
10
8～10?? ?
�
≤
1
0
5
N≤10?
5
??? ?
�
≤
1
0
5
M≤10?
5
??? ?-

我们把方差公式展开

所以只需要维护一个区间平方和和区间和

当我们更新一个区间加时

所以pushdown就很好写了

具体见代码

想要进一步学习的可以看这里

#include <cstdio>
#include <iostream>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define Maxn 300010
using namespace std;
double sega[Maxn],segb[Maxn];
double mark[Maxn];
void pushup(int x)
{
? ? sega[x]=sega[x<<1]+sega[x<<1|1];
? ? segb[x]=segb[x<<1]+segb[x<<1|1];
}
void pushdown(int rt,int x)
{
? ? if (mark[rt])
? ? {
? ? ? ? segb[rt<<1]+=2*mark[rt]*sega[rt<<1]+(x-x/2)*mark[rt]*mark[rt];
? ? ? ? segb[rt<<1|1]+=2*mark[rt]*sega[rt<<1|1]+(x/2)*mark[rt]*mark[rt];
? ? ? ? sega[rt<<1]+=(x-x/2)*mark[rt];
? ? ? ? sega[rt<<1|1]+=(x/2)*mark[rt];
? ? ? ? mark[rt<<1]+=mark[rt];
? ? ? ? mark[rt<<1|1]+=mark[rt];
? ? ? ? mark[rt]=0;
? ? }
}
void build(int rt,int l,int r)
{
? ? if (l==r)
? ? ? ? cin>>sega[rt],segb[rt]=sega[rt]*sega[rt];
? ? else
? ? {
? ? ? ? int mid=(l+r)/2;
? ? ? ? build(lson);
? ? ? ? build(rson);
? ? ? ? pushup(rt);
? ? }
}
double query_a(int rt,int l,int r,int L,int R)
{
? ? //--L--l--r--R--
? ? if (l>=L && r<=R)
? ? ? ? return sega[rt];
? ? else
? ? {
? ? ? ? pushdown(rt,r-l+1);
? ? ? ? int mid=(r+l)/2;
? ? ? ? double ret=0;
? ? ? ? if (mid>=L)
? ? ? ? ? ? ret+=query_a(lson,L,R);
? ? ? ? if (mid<R)
? ? ? ? ? ? ret+=query_a(rson,L,R);
? ? ? ? return ret;
? ? }
}
double query_b(int rt,int l,int r,int L,int R)
{
? ? //--L--l--r--R--
? ? if (l>=L && r<=R)
? ? ? ? return segb[rt];
? ? else
? ? {
? ? ? ? pushdown(rt,r-l+1);
? ? ? ? int mid=(r+l)/2;
? ? ? ? double ret=0;
? ? ? ? if (mid>=L)
? ? ? ? ? ? ret+=query_b(lson,L,R);
? ? ? ? if (mid<R)
? ? ? ? ? ? ret+=query_b(rson,L,R);
? ? ? ? return ret;
? ? }
}
void update(int rt,int l,int r,int L,int R,double x)
{
? ? if (l>=L && r<=R)
? ? ? ? mark[rt]+=x,segb[rt]+=2*x*sega[rt]+x*x*(r-l+1),sega[rt]+=(r-l+1)*x;
? ? else
? ? {
? ? ? ? pushdown(rt,r-l+1);
? ? ? ? int mid=(r+l)/2;
? ? ? ? if (mid>=L)
? ? ? ? ? ? update(lson,L,R,x);
? ? ? ? if (mid<R)
? ? ? ? ? ? update(rson,L,R,x);
? ? ? ? pushup(rt);
? ? }
}
double sqr(double x)
{
? ? return x*x;
}
main()
{
? ? int n,m,x,y,c;
? ? double z;
? ? scanf("%d %d",&n,&m);
? ? build(1,1,n);
? ? for (int i=1;i<=m;i++)
? ? {
? ? ? ? scanf("%d",&c);
? ? ? ? if (c==2)
? ? ? ? ? ? scanf("%d%d",&x,&y),printf("%.4lf\n",query_a(1,1,n,x,y)/(y-x+1));
? ? ? ? if (c==1)
? ? ? ? ? ? scanf("%d%d",&x,&y),cin>>z,update(1,1,n,x,y,z);
? ? ? ? if (c==3)
? ? ? ? {
? ? ? ? ? ? scanf("%d%d",&x,&y);
? ? ? ? ? ? double sum1=query_b(1,1,n,x,y)/(y-x+1),sum2=query_a(1,1,n,x,y)/(y-x+1);
? ? ? ? ? ? double ans=sum1-sum2*sum2;
? ? ? ? ? ? printf("%.4lf\n",ans);
? ? ? ? }
? ? }
}