大佬!!!40pts 式子正确 只建了两棵树
  • 板块P1471 方差
  • 楼主a1a2a3a4a5
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/9/15 17:02
  • 上次更新2023/11/2 20:44:34
查看原帖
大佬!!!40pts 式子正确 只建了两棵树
658008
a1a2a3a4a5楼主2023/9/15 17:02

我在jia2里加&&l==r就T,不加就wa。

#include<bits/stdc++.h>
#define lp (p<<1)
#define rp ((p<<1)|1)

using namespace std;
int n,m;
double lan[110000<<2],sum[110000<<2],a[110000];//a和
void pushdown(int l,int r,int p)
{
	int mid=(l+r)>>1;
	sum[lp]+=(double)(mid-l+1)*lan[p];
	sum[rp]+=(double)(r-mid)*lan[p];
	lan[lp]+=lan[p];
	lan[rp]+=lan[p];
	lan[p]=0;
}
void build(int l,int r,int p)
{
	if(l==r) {sum[p]=a[l];return ;}
	int mid=(l+r)>>1;
	build(l,mid,lp);
	build(mid+1,r,rp);
	sum[p]=sum[lp]+sum[rp];
}
void jia(int l,int r,int L,int R,int p,double c)
{
	if(l>=L&&r<=R)
	{
		sum[p]=sum[p]+c*(double)(r-l+1);
		lan[p]+=c;
		return ;
	}
	int mid=(l+r)>>1;
	pushdown(l,r,p);
	if(mid>=L) jia(l,mid,L,R,lp,c);
	if(mid<R) jia(mid+1,r,L,R,rp,c);
	sum[p]=sum[lp]+sum[rp];
}
double he(int l,int r,int L,int R,int p)
{
	if(l>=L&&r<=R)
	{
		return sum[p];
	}
	int mid=(l+r)>>1;
	double da=0;
	pushdown(l,r,p);
	if(mid>=L) da+=he(l,mid,L,R,lp);
	if(mid<R) da+=he(mid+1,r,L,R,rp);
	return da;
}
struct xxx //平方和
{
	double lan[110000<<2],sum[110000<<2];
	void pushdown2(int l,int r,int p)
	{
		int mid=(l+r)>>1;
		sum[lp]+=(double)(mid-l+1)*lan[p]*lan[p]+2*lan[p]*he(1,n,l,mid,1);
		sum[rp]+=(double)(r-mid)*lan[p]*lan[p]+2*lan[p]*he(1,n,mid+1,r,1);
		lan[lp]+=lan[p];
		lan[rp]+=lan[p];
		lan[p]=0;
	}
	void build2(int l,int r,int p)
	{
		lan[p]=0;
		if(l==r) {sum[p]=a[l]*a[l];return ;}
		int mid=(l+r)>>1;
		build2(l,mid,lp);
		build2(mid+1,r,rp);
		sum[p]=sum[lp]+sum[rp];
	}
	void jia2(int l,int r,int L,int R,int p,double c)
	{
//		if(l>=L&&r<=R&&l==r) 加则T,不加则WA
		if(l>=L&&r<=R)
		{
			sum[p]=sum[p]+c*c*(double)(r-l+1)+(double)2*c*he(1,n,l,r,1);
			lan[p]+=c;
			return ;
		}
		int mid=(l+r)>>1;
		pushdown2(l,r,p);
		
		if(mid>=L) jia2(l,mid,L,R,lp,c);
		if(mid<R) jia2(mid+1,r,L,R,rp,c);
		sum[p]=sum[lp]+sum[rp];
	}
	double he2(int l,int r,int L,int R,int p)
	{
		if(l>=L&&r<=R)
		{
			return sum[p];
		}
		int mid=(l+r)>>1;
		double da=0;
		pushdown2(l,r,p);
		
		if(mid>=L) da+=he2(l,mid,L,R,lp);
		if(mid<R) da+=he2(mid+1,r,L,R,rp);
		return da;
	}
} shu;
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,n,1);
	shu.build2(1,n,1);
	for(double i=1,op,x,y,k;i<=m;i++)
	{
		cin>>op>>x>>y;
		if(op==1) cin>>k,shu.jia2(1,n,x,y,1,k),jia(1,n,x,y,1,k);
		else if(op==2)
		{
			double h=he(1,n,x,y,1);
			printf("%.4lf\n",(h/(double)(y-x+1)));
		}
		else if(op==3)
		{
			double h=he(1,n,x,y,1),p=h/(double)(y-x+1);
			printf("%.4lf\n",((shu.he2(1,n,x,y,1)+(double)p*p*(double)(y-x+1)-(double)2*p*h)/(double)(y-x+1)));
//			cout<<shu.he2(1,n,x,y,1)<<" "<<p<<" "<<h<<'\n';调试
		}
	}
	return 0;
}
2023/9/15 17:02
加载中...