蒟蒻刚学 OI,分块 0pts 求调
  • 板块P1471 方差
  • 楼主__liujy
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/7/22 14:27
  • 上次更新2025/7/22 17:47:07
查看原帖
蒟蒻刚学 OI,分块 0pts 求调
1657369
__liujy楼主2025/7/22 14:27
#include<bits/stdc++.h>
const int N=1e5+5;
int n,m;
double a[N];
namespace block
{
	int len,id[N],st[N],ed[N];
	double s[N],sum[N],lazy[N];
	inline void init()
	{
		len=sqrt(n);
		for(int i=1;i<=n;i++)
			id[i]=(i-1)/len+1,
			st[i]=(i-1)*len+1,
			ed[i]=i*len,
			sum[id[i]]+=a[i]*a[i],
			s[id[i]]+=a[i];
	}
	inline void add(int l,int r,double k)
	{
		int L=id[l],R=id[r];
		if(L==R)
		{
			for(int i=l;i<=r;i++)
				sum[L]+=2*k*a[i]+k*k,
				a[i]+=k,s[L]+=k;
			return;
		}
		for(int i=l;id[i]==L;i++)
			sum[L]+=2*k*a[i]+k*k,
			a[i]+=k,s[L]+=k;
		for(int i=L+1;i<R;i++) lazy[i]+=k;
		for(int i=r;id[i]==R;i--)
			sum[R]+=2*k*a[i]+k*k,
			a[i]+=k,s[R]+=k;
	}
	inline double query(int l,int r)
	{
		int L=id[l],R=id[r];
		double ans=0,len=r-l+1;
		if(L==R)
		{
			for(int i=l;i<=r;i++)
				ans+=a[i]+lazy[L];
			return ans/len;
		}
		for(int i=l;id[i]==L;i++) ans+=a[i]+lazy[L];
		for(int i=L+1;i<R;i++) ans+=s[i]+len*lazy[i];
		for(int i=r;id[i]==R;i--) ans+=a[i]+lazy[R];
		return ans/len;
	}
	inline double getsum(int l,int r)
	{
		int L=id[l],R=id[r];
		double ans=0,ave=0,len=r-l+1;
		if(L==R)
		{
			for(int i=l;i<=r;i++)
				ave+=a[i]+lazy[L],
				ans+=(a[i]+lazy[L])*(a[i]+lazy[L]);
			return ans/len-(ave/len)*(ave/len);
		}
		for(int i=l;id[i]==L;i++)
			ave+=a[i]+lazy[L],
			ans+=(a[i]+lazy[L])*(a[i]+lazy[L]);
		for(int i=L+1;i<R;i++)
			ave+=s[i]+lazy[i]*len,
			ans+=sum[i]+2*s[i]*lazy[i]+len*lazy[i]*lazy[i];
		for(int i=r;id[i]==R;i--)
			ave+=a[i]+lazy[R],
			ans+=(a[i]+lazy[R])*(a[i]+lazy[R]);
		return ans/len-(ave/len)*(ave/len);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
	block::init();
	double k;
	for(int _=1,op,l,r;_<=m;_++)
	{
		scanf("%d%d%d",&op,&l,&r);
		if(op==1)
		{ scanf("%lf",&k); block::add(l,r,1.0*k); }
		else if(op==2) printf("%.4lf\n",block::query(l,r));
		else printf("%.4lf\n",block::getsum(l,r));
	}
	return 0;
}

回复请 at 我。

2025/7/22 14:27
加载中...