萌新分块 60pts求助
  • 板块P1471 方差
  • 楼主Soul_Love
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/3/13 21:12
  • 上次更新2023/10/23 21:38:00
查看原帖
萌新分块 60pts求助
110009
Soul_Love楼主2023/3/13 21:12
#include<bits/stdc++.h>
#define ll long long
using namespace std;
double sum1[1001000],sum2[1001000],add[1001000],a[1001000];//sum1是和,sum2是平方和
ll t,L[1001000],R[1001000],pos[1001000],m,n;
inline void update(ll l,ll r,double k)
{
	ll q=pos[l],p=pos[r];
	if(p==q)
	{
		for(ll i=l;i<=r;i++)
		{
			sum2[p]-=a[i]*a[i];
			a[i]+=k;
			sum2[p]+=a[i]*a[i];
		}
		sum1[p]+=(r-l+1)*k;
	}
	else
	{
		for(ll i=q+1;i<p;i++)
		{
			add[i]+=k;
			sum2[i]+=2*sum1[i]*k+(R[i]-L[i]+1)*k*k;
			sum1[i]+=(R[i]-L[i]+1)*k;
		}
		for(ll i=l;i<=R[q];i++)
		{
			sum2[q]-=a[i]*a[i];
			a[i]+=k;
			sum2[q]+=a[i]*a[i];
		}
		for(ll i=L[p];i<=r;i++)
		{
			sum2[p]-=a[i]*a[i];
			a[i]+=k;
			sum2[p]+=a[i]*a[i];
		}
		sum1[q]+=(R[q]-l+1)*k;
		sum1[p]+=(r-L[p]+1)*k;
	}
}
inline double ask1(ll l,ll r)//和
{
	ll q=pos[l],p=pos[r];
	double ans=0;
	if(p==q)
	{
		for(ll i=l;i<=r;i++) ans+=a[i];
		ans+=add[p]*(r-l+1);
	}
	else
	{
		for(ll i=q+1;i<p;i++) ans+=sum1[i];
		for(ll i=l;i<=R[q];i++) ans+=a[i];
		for(ll i=L[p];i<=r;i++) ans+=a[i];
		ans+=add[q]*(R[q]-l+1);
		ans+=add[p]*(r-L[p]+1);
	}
	return ans;
}
inline double ask2(ll l,ll r)//平方和
{
	ll q=pos[l],p=pos[r];
	double ans=0;
	if(p==q) for(ll i=l;i<=r;i++) ans+=(a[i]+add[p])*(a[i]+add[p]);
	else
	{
		for(ll i=q+1;i<p;i++) ans+=sum2[i];
		for(ll i=l;i<=R[q];i++) ans+=(a[i]+add[q])*(a[i]+add[q]);
		for(ll i=L[p];i<=r;i++) ans+=(a[i]+add[p])*(a[i]+add[p]);
	}
	return ans;
}
inline void build()
{
	t=sqrt(n);
	for(ll i=1;i<=t;i++)
	{
		L[i]=R[i-1]+1;
		R[i]=i*t;
	}
	if(R[t]<n)
	{
		t++;
		L[t]=R[t-1]+1;
		R[t]=n;
	}
	for(ll i=1;i<=t;i++)
	{
		for(ll j=L[i];j<=R[i];j++)
		{
			pos[j]=i;
			sum1[i]+=a[j];
			sum2[i]+=a[j]*a[j];
		}
	}
}
int main()
{
	scanf("%lld %lld",&n,&m);
	for(ll i=1;i<=n;i++) scanf("%lf",&a[i]);
	build();
	while(m--)
	{
		ll o1,o2,o3;
		scanf("%lld %lld %lld",&o1,&o2,&o3);
		if(o1<2)
		{
			double o4;
			scanf("%lf",&o4);
			update(o2,o3,o4);
		}
		else if(o1<3) printf("%.4lf\n",ask1(o2,o3)/(o3-o2+1));
		else
		{
			double o4=ask1(o2,o3)/(o3-o2+1);
			printf("%.4lf\n",(ask2(o2,o3)-2*ask1(o2,o3)*o4+(o3-o2+1)*o4*o4)/(o3-o2+1));
		}
	}
	return 0;
}
2023/3/13 21:12
加载中...