P1471

发表于 分类于
方差

方差

想到了 NOIP2021 考场上的那道题。

所以自然地想到让这个方差乘上 $n^2$，然后我们简化之后就可以得到：

$$n^2s^2=n\sum_{i=1}^nA_i^2-(\sum_{i=1}^nA_i)^2$$

于是我们的方差就是把左边的 $n^2$ 除过去。

然后这样的话我们的序列就只需要维护两种和了，一种是 $\sum_{i=1}^nA_i$，另一种是 $\sum_{i=1}^nA_i^2$。

第一种值比较好维护，关键是如何维护第二种值。

我们假设一段区间都加上了常数 $k$，那么这一段区间的第二种值的变化量就是：

$$\Delta=\sum_{i=1}^n(A_i+k)^2-\sum_{i=1}^nA_i^2$$

化简之后得到：

$$\Delta=nk^2+2k\sum_{i=1}^nA_i$$

然后显然这个 $\sum_{i=1}^nA_i$ 我们可以直接用，所以直接更新。懒标记的下传也是同理。

最后这题解决了。

然后时刻要注意线段树中的参数类型要写成 double。

时间复杂度 $O((m+n)\log n)$。

代码：

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
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=1e5;

ll n,m,op,l,r;

double k;

double a[N+5];

struct sgt{
	ll l,r;
	double dat1,dat2,laz;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define dat1(x) tree[x].dat1
	#define dat2(x) tree[x].dat2
	#define laz(x) tree[x].laz
}tree[N*4+5];

void build(ll p,ll l,ll r) {
	l(p)=l;r(p)=r;
	if(l==r) {dat1(p)=a[l];dat2(p)=a[l]*a[l];return;}
	ll mid=(l+r)>>1;
	build(p<<1,l,mid);build(p<<1|1,mid+1,r);
	dat1(p)=dat1(p<<1)+dat1(p<<1|1);
	dat2(p)=dat2(p<<1)+dat2(p<<1|1);
}

void spread(ll p) {
	dat2(p<<1)+=laz(p)*laz(p)*(r(p<<1)-l(p<<1)+1)+2*laz(p)*dat1(p<<1);
	dat1(p<<1)+=laz(p)*(r(p<<1)-l(p<<1)+1);laz(p<<1)+=laz(p);
	dat2(p<<1|1)+=laz(p)*laz(p)*(r(p<<1|1)-l(p<<1|1)+1)+2*laz(p)*dat1(p<<1|1);
	dat1(p<<1|1)+=laz(p)*(r(p<<1|1)-l(p<<1|1)+1);laz(p<<1|1)+=laz(p);
	laz(p)=0;
}

void add(ll p,ll l,ll r,double k) {
	if(l(p)>=l&&r(p)<=r) {
		dat2(p)+=k*k*(r(p)-l(p)+1)+2*k*dat1(p);
		dat1(p)+=k*(r(p)-l(p)+1);
		laz(p)+=k;return;
	}
	ll mid=(l(p)+r(p))>>1;spread(p);
	if(l<=mid) add(p<<1,l,r,k);
	if(r>mid) add(p<<1|1,l,r,k);
	dat1(p)=dat1(p<<1)+dat1(p<<1|1);
	dat2(p)=dat2(p<<1)+dat2(p<<1|1);
}

double ask1(ll p,ll l,ll r) {
	if(l(p)>=l&&r(p)<=r) {
		return dat1(p);
	}
	ll mid=(l(p)+r(p))>>1;spread(p);
	if(l>mid) return ask1(p<<1|1,l,r);
	if(r<=mid) return ask1(p<<1,l,r);
	return ask1(p<<1,l,r)+ask1(p<<1|1,l,r);
}

double ask2(ll p,ll l,ll r) {
	if(l(p)>=l&&r(p)<=r) {
		return dat2(p);
	}
	ll mid=(l(p)+r(p))>>1;spread(p);
	if(l>mid) return ask2(p<<1|1,l,r);
	if(r<=mid) return ask2(p<<1,l,r);
	return ask2(p<<1,l,r)+ask2(p<<1|1,l,r);
}

inline ll read() {
	ll ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
	return ret*f;
}

int main() {

	n=read();m=read();

	for(ll i=1;i<=n;i++) {
		scanf("%lf",&a[i]);
	}

	build(1,1,n);

	while(m--) {
		op=read();l=read();r=read();
		if(op==1) {
			scanf("%lf",&k);add(1,l,r,k);
		}
		if(op==2) {
			double tmp1=ask1(1,l,r),tmp3=r-l+1;
			tmp1=tmp1/tmp3;
			printf("%.4f\n",tmp1);
		}
		if(op==3) {
			double ans,tmp1,tmp2,tmp3;
			tmp1=ask1(1,l,r);tmp2=ask2(1,l,r);tmp3=r-l+1;
			ans=tmp2/tmp3-(tmp1/tmp3)*(tmp1/tmp3);
			printf("%.4f\n",ans);
		}
	}

	return 0;
}