求好评,公式全手写

思路

展开方差公式:

$$\begin{aligned} &=\frac{(x_1-\overline{x})^2+(x_2-\overline{x})^2+...+(x_n-\overline{x})^2}{n} \\ &=\frac{(x_1^2-2x_1\overline{x}+\overline{x}^2)+(x_2^2-2x_2\overline{x}+\overline{x}^2)+...+(x_n^2-2x_n\overline{x}+\overline{x}^2)}{n} \\ &=\frac{(x_1^2+x_2^2+...+x_n^2)-2\overline{x}(x_1+x_2+...+x_n)+n\overline{x}^2}{n} \\ &=\frac{(x_1^2+x_2^2+...+x_n^2)-2n\overline{x}+n\overline{x}}{n} \\ &=\frac{(x_1^2+x_2^2+...+x_n^2)+n\overline{x}}{n} \\ &=\frac{x_1^2+x_2^2+...+x_n^2}{n}-\overline{x}^2 \\ \end{aligned} $$

在展开公式的第 $1$ 到 $2$ 行用了

$$(a-b)^2=a^2-2ab+b^2$$

在展开公式的第 $3$ 到 $4$ 行用了

$$n\overline{x}=x_1+x_2+...+x_n$$

由此可知,懒标记维护的是 区间和( 区间平均值 , $\overline{x}$ ) 和 区间平方和 ( $x_1^2+x_2^2+...+x_n^2$ )

区间和 加上 $a$ 是好写的

区间平方和 加上 $a$ 要怎么写:

$$\begin{aligned} &S_1=x_1+x_2+...+x_n \\ &S_2=x_1^2+x_2^2+...+x_n^2 \\ \end{aligned} $$

加上 $a$ 后:

$$\begin{aligned} &S_2=(x_1+a)^2+(x_2+a)^2+...+(x_n+a)^2 \\ &S_2=(x_1^2+2x_1a+a^2)+(x_2^2+2x_2a+a^2)+...+(x_n^2+2x_na+a^2) \\ &S_2=S_2+2a(x_1+...+x_n)+na^2 \\ &S_2=S_2+2aS_1+na^2 \end{aligned} $$

需要注意的是, $S_1$ 要在 $S_2$ 修改后再改

代码

#include<iostream>
#define N 100005
using namespace std;
int n,m;
double a[N];
double tree[N<<2];//区间和 
double pf[N<<2];//区间平方和 
double lazy[N<<2];//懒标记 
void push_up(int x)
{
	tree[x]=tree[x<<1]+tree[x<<1|1];
	pf[x]=pf[x<<1]+pf[x<<1|1];
}
int push_down(int s,int t,int x)
{
	int m=(s+t)>>1;
	pf[x<<1]+=2*lazy[x]*tree[x<<1]+(m-s+1)*lazy[x]*lazy[x];
	pf[x<<1|1]+=2*lazy[x]*tree[x<<1|1]+(t-m)*lazy[x]*lazy[x];
	tree[x<<1]+=lazy[x]*(m-s+1);
	tree[x<<1|1]+=lazy[x]*(t-m);
	lazy[x<<1]+=lazy[x];
	lazy[x<<1|1]+=lazy[x];
	lazy[x]=0;
	return m;
}
void btree(int l,int r,int x)
{
	if(l==r)
	{
		tree[x]=a[l];
		pf[x]=a[l]*a[l];
		return;
	}
	int m=(l+r)>>1;
	btree(l,m,x<<1);
	btree(m+1,r,x<<1|1);
	push_up(x);
}
double gstree(int l,int r,int s,int t,int x)
{
	if(l<=s && t<=r)
		return tree[x];
	int m=push_down(s,t,x);
	double sum=0;
	if(l<=m)
		sum+=gstree(l,r,s,m,x<<1);
	if(r>m)
		sum+=gstree(l,r,m+1,t,x<<1|1);
	return sum;
}
double gptree(int l,int r,int s,int t,int x)
{
	if(l<=s && t<=r)
		return pf[x];
	int m=push_down(s,t,x);
	double sum=0;
	if(l<=m)
		sum+=gptree(l,r,s,m,x<<1);
	if(r>m)
		sum+=gptree(l,r,m+1,t,x<<1|1);
	return sum;
}
void utree(int l,int r,int s,int t,double c,int x)
{
	if(l<=s && t<=r)
	{
		pf[x]+=2*c*tree[x]+(t-s+1)*c*c;
		tree[x]+=c*(t-s+1);
		lazy[x]+=c;
		return;
	}
	int m=push_down(s,t,x);
	if(l<=m)
		utree(l,r,s,m,c,x<<1);
	if(r>m)
		utree(l,r,m+1,t,c,x<<1|1);
	push_up(x);
}
int main()
{
	//freopen("P1471_1.in","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	btree(1,n,1);
	while(m--)
	{
		int o,l,r;
		double k;
		cin>>o>>l>>r;
		if(o==1)
		{
			cin>>k;
			utree(l,r,1,n,k,1);
		}
		if(o==2)
		{
			printf
			("%.4lf\n",
				(1.0*gstree(l,r,1,n,1)/(r-l+1))
			);
		}
		if(o==3)
		{
			printf
			("%.4lf\n",
				(1.0*gptree(l,r,1,n,1)/(r-l+1))-
				(1.0*gstree(l,r,1,n,1)/(r-l+1))*
				(1.0*gstree(l,r,1,n,1)/(r-l+1))
			);
		}
	}
	return 0;
}