摘要:维护方差需要的信息

luogu1471方差

题面

分寝室竟然和菜菜子和神m一起插到了有4个化学人和1个生物人的原化学寝室…

宣称:化学,生物

文化:化学 (不是信息的相容文化)

p社分析.jpg

于是晚上无聊就想了想这道题.

题目分析

要维护区间的方差,先看看方差的定义式:

拆开:

首先平均值是很好维护的,因为只会在询问时用到,查询出区间和除以区间长度就可以了.

然后还需要维护出每个值的平方和,拆一下修改操作:

这样在一次方和的基础上就可以算出二次方和的修改量了.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include "iostream"
#include "cstdlib"
#include "cstdio"
#include "cstring"
#include "cmath"
#include "cctype"
#include "ctime"
#include "iomanip"
#include "algorithm"
#include "set"
#include "queue"
#include "map"
#include "stack"
#include "deque"
#include "vector"
#define R register
#define INF 0x3f3f3f3f
#define debug(x) printf("debug:%lld\n",x)
#define debugi(x) printf("debug:%d\n",x)
#define debugf(x) printf("debug:%llf\n",x)
#define endl putchar('\n')
typedef long long lxl;
const lxl big=100010;
lxl n,m,root,NodeCnt;
lxl c[2][big<<2];
double sum[big<<2],sum2[big<<2],tag[big<<2],a[big];
inline lxl read()
{
char c(getchar());
lxl f(1),x(0);
for(;!isdigit(c);(c=='-')&&(f=-1),c=getchar());
for(;isdigit(c);x=(x<<1)+(x<<3)+(c^48),c=getchar());
return f*x;
}
inline void PushUp(lxl t,lxl l,lxl r)
{
sum[t]=sum[c[0][t]]+sum[c[1][t]];
sum2[t]=sum2[c[0][t]]+sum2[c[1][t]];
}
inline void PushDown(lxl t,lxl l,lxl r)
{
if(tag[t]==0)return;
lxl mid((l+r)>>1);
#define lson c[0][t]
#define rson c[1][t]
tag[lson]+=tag[t],tag[rson]+=tag[t];
sum2[lson]+=2*sum[lson]*tag[t]+tag[t]*tag[t]*(mid-l+1);
sum2[rson]+=2*sum[rson]*tag[t]+tag[t]*tag[t]*(r-mid);
sum[lson]+=tag[t]*(mid-l+1),sum[rson]+=tag[t]*(r-mid);
tag[t]=0;
}
void build(lxl &t,lxl l,lxl r)
{
if(!t)t=++NodeCnt;
if(l==r){sum[t]=a[l],sum2[t]=a[l]*a[l];return;}
lxl mid((l+r)>>1);
build(c[0][t],l,mid),build(c[1][t],mid+1,r);
PushUp(t,l,r);
}
void modify(lxl t,lxl l,lxl r,lxl x,lxl y,double val)
{
if(x<=l&&y>=r)
{
tag[t]+=val;
sum2[t]+=2*sum[t]*val+val*val*(r-l+1);
sum[t]+=val*(r-l+1);
return;
}
PushDown(t,l,r);
lxl mid((l+r)>>1);
if(x<=mid)modify(c[0][t],l,mid,x,y,val);
if(y>mid)modify(c[1][t],mid+1,r,x,y,val);
PushUp(t,l,r);
}
double query2(lxl t,lxl l,lxl r,lxl x,lxl y)
{
if(x<=l&&y>=r)return sum2[t];
PushDown(t,l,r);
lxl mid((l+r)>>1);
double ret=0;
if(x<=mid)ret+=query2(c[0][t],l,mid,x,y);
if(y>mid)ret+=query2(c[1][t],mid+1,r,x,y);
return ret;
}
double query3(lxl t,lxl l,lxl r,lxl x,lxl y)
{
if(x<=l&&y>=r)return sum[t];
PushDown(t,l,r);
lxl mid((l+r)>>1);
double ret=0;
if(x<=mid)ret+=query3(c[0][t],l,mid,x,y);
if(y>mid)ret+=query3(c[1][t],mid+1,r,x,y);
return ret;
}
int main(void)
{
// freopen("P1471_2.in","r",stdin);
// freopen("test.out","w",stdout);
n=read(),m=read();
for(R int i(1);i<=n;++i)scanf("%lf",a+i);
build(root,1,n);
for(R int i(1);i<=m;++i)
{
lxl opt=read(),x=read(),y=read();
if(opt==1)
{
double k;scanf("%lf",&k);
modify(root,1,n,x,y,k);
}
else if(opt==2)printf("%.4lf\n",query3(root,1,n,x,y)/(y-x+1));
else
{
double sum2_=query2(root,1,n,x,y),sum_=query3(root,1,n,x,y);
double ave_=sum_/(y-x+1);
printf("%.4lf\n",(sum2_-2*sum_*ave_)/(y-x+1)+ave_*ave_);
}
}
return 0;
}