]P1471 方差)
P1471 方差
时间限制: 1.00s 内存限制: 125.00MB
复制 Markdown
中文
退出 IDE 模式
题目背景
滚粗了的 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
说明/提示
关于方差：对于一个有 n 项的数列 A，其方差 s2 定义如下：
s2=n1i=1∑n(Ai−A)2
其中 A 表示数列 A 的平均数，Ai 表示数列 A 的第 i 项。
样例说明：
| 操作步骤 | 输入内容 | 操作要求 | 数列 | 输出结果 | 说明 |
|---|---|---|---|---|---|
| 0 | - | - | 1 5 4 2 3 | - | - |
| 1 | 2 1 4 | 求 [1,4] 内所有数字的平均数 | 1 5 4 2 3 | 3.0000 | 平均数 =(1+5+4+2)÷4=3.0000 |
| 2 | 3 1 5 | 求 [1,5] 内所有数字的方差 | 1 5 4 2 3 | 2.0000 | 平均数 =(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 |
| 3 | 1 1 1 1 | 将 [1,1] 内所有数字加 1 | 2 5 4 2 3 | - | - |
| 4 | 1 2 2 -1 | 将 [2,2] 内所有数字加 −1 | 2 4 4 2 3 | - | - |
| 5 | 3 1 5 | 求 [1,5] 内所有数字的方差 | 2 4 4 2 3 | 0.8000 | 平均数 =(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 |
数据规模：
| 数据点 | N | M | 备注 |
|---|---|---|---|
| 1∼3 | N≤8 | M≤15 | - |
| 4∼7 | N≤105 | M≤105 | 不包含操作 3 |
| 8∼10 | N≤105 | M≤105 | - |
保证原数列和输入的所有 k 均为 [−100,100] 范围内的实数。
方差可以推导为 平方数的和/n - 平均数的平方
一段区间加d的时候 平方和的变化：
令sum1 为区间和 sum2为区间平方和
那么当长度为len的区间加d的时候
sum2+=d*d*len+2*sum1*d;
#include <bits/stdc++.h> using namespace std; #define int long long const int N=1e5+5; double a[N]; int n,m; struct SegmentTree{ int l,r; double sum,ssum,add; #define l(x) tree[x].l #define r(x) tree[x].r #define sum(x) tree[x].sum #define ssum(x) tree[x].ssum #define add(x) tree[x].add }tree[N<<2]; void pushup(int p){ sum(p)=sum(p<<1)+sum(p<<1|1); ssum(p)=ssum(p<<1)+ssum(p<<1|1); } void pushdown(int p){ if(add(p)){ ssum(p<<1)+=add(p)*add(p)*(r(p<<1)-l(p<<1)+1)+2*(sum(p<<1)*add(p)); ssum(p<<1|1)+=add(p)*add(p)*(r(p<<1|1)-l(p<<1|1)+1)+2*(sum(p<<1|1)*add(p)); add(p<<1)+=add(p); add(p<<1|1)+=add(p); sum(p<<1)+=add(p)*(r(p<<1)-l(p<<1)+1); sum(p<<1|1)+=add(p)*(r(p<<1|1)-l(p<<1|1)+1); add(p)=0; } } void build(int p,int l,int r){ l(p)=l,r(p)=r; if(l==r){sum(p)=a[l];ssum(p)=a[l]*a[l];return;} int mid=(l+r)>>1; build(p<<1,l,mid); build(p<<1|1,mid+1,r); pushup(p); } void changeadd(int p,int l,int r,double k){ if(l<=l(p)&&r>=r(p)){ ssum(p)+=k*k*(r(p)-l(p)+1)+2*(k*sum(p)); add(p)+=k; sum(p)+=k*(r(p)-l(p)+1); return; } pushdown(p); int mid=(l(p)+r(p))>>1; if(l<=mid)changeadd(p<<1,l,r,k); if(r>mid)changeadd(p<<1|1,l,r,k); pushup(p); } double querysum(int p,int l,int r){ if(l<=l(p)&&r>=r(p)){ return sum(p); } pushdown(p); int mid=(l(p)+r(p))>>1; double val=0; if(l<=mid)val+=querysum(p<<1,l,r); if(r>mid)val+=querysum(p<<1|1,l,r); return val; } double queryssum(int p,int l,int r){ if(l<=l(p)&&r>=r(p)){ return ssum(p); } pushdown(p); int mid=(l(p)+r(p))>>1; double val=0; if(l<=mid)val+=queryssum(p<<1,l,r); if(r>mid)val+=queryssum(p<<1|1,l,r); return val; } signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m;cout << fixed << setprecision(4); for(int i=1;i<=n;i++)cin>>a[i]; build(1,1,n); while(m--){ int op,l,r;cin>>op>>l>>r; if(op==1){ double k;cin>>k; changeadd(1,l,r,k); }else if(op==2){ cout<<1.0*querysum(1,l,r)/(r-l+1)<<'\n'; }else{ cout<<queryssum(1,l,r)/(r-l+1)-1.0*querysum(1,l,r)/(r-l+1)*1.0*querysum(1,l,r)/(r-l+1)<<'\n'; } } return 0; }
