0pts求调
  • 板块P1471 方差
  • 楼主yanrs1019
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/13 22:04
  • 上次更新2024/11/14 02:30:47
查看原帖
0pts求调
1304706
yanrs1019楼主2024/11/13 22:04
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define LD long double
LD a[100005],mark[400005];
LL n;
struct node
{
	LD a,b;
}tree[400005];
void push_down(LL p,LL len)
{
    if (mark[p])
    {
        tree[p<<1].b+=2*mark[p]*tree[p<<1].a+(len-len>>1)*mark[p]*mark[p];
        tree[p<<1|1].b+=2*mark[p]*tree[p<<1|1].a+(len>>1)*mark[p]*mark[p];
        tree[p<<1].a+=(len-len>>1)*mark[p];
        tree[p<<1|1].a+=(len>>1)*mark[p];
        mark[p<<1]+=mark[p];
        mark[p<<1|1]+=mark[p];
        mark[p]=0;
    }
}
void build(LL l,LL r,LL p)
{
	if(l==r)tree[p].a=a[l],tree[p].b=a[l]*a[l];
	else
	{
		LL mid=l+r>>1;
		build(l,mid,p<<1);
		build(mid+1,r,p<<1|1);
		tree[p].a=tree[p<<1].a+tree[p<<1|1].a;
		tree[p].b=tree[p<<1].b+tree[p<<1|1].b;
	}
}
void update(LL l,LL r,LD d,LL p,LL cl,LL cr)
{
	//printf("l:%lld r:%lld d:%lld p:%lld cl:%lld cr:%lld\n",l,r,d,p,cl,cr);
	if(cl>r||cr<l)return ;
	else if(cl>=l&&cr<=r)
	{
		tree[p].b+=2*d*tree[p].a+d*d*(cr-cl+1);
		tree[p].a+=(cr-cl+1)*d;
		//printf("tree[%d->%d,%d]={a:%d,b:%d}\n",cl,cr,p,tree[p].a,tree[p].b);
		mark[p]+=d;
	}
	else
	{
		LL mid=cl+cr>>1;
		push_down(p,cr-cl+1);
		if(mid>=l)update(l,r,d,p<<1,cl,mid);
        if(mid<r)update(l,r,d,p<<1|1,mid+1,cr);
		tree[p].a=tree[p<<1].a+tree[p<<1|1].a;
		tree[p].b=tree[p<<1].b+tree[p<<1|1].b;
	}
}
LD query(LL l,LL r,LL p,LL cl,LL cr)
{
	//printf("l:%lld r:%lld p:%lld cl:%lld cr:%lld\n",l,r,p,cl,cr);
	if(cl>r||cr<l)return 0;
	else if(cl>=l&&cr<=r)
	{
		//printf("return %lld\n",tree[p].a);
		return tree[p].a;
	}
	else
	{
		push_down(p,cr-cl+1);
		LL mid=cl+cr>>1;
		LD ret=0;
		if(mid>=l)ret+=query(l,r,p<<1,cl,mid);
		if(mid<r)ret+=query(l,r,p<<1|1,mid+1,cr);
		return ret;
	}
}
LD query2(LL l,LL r,LL p,LL cl,LL cr)
{
	if(cl>r||cr<l)return 0;
	else if(cl>=l&&cr<=r)return tree[p].b;
	else
	{
		push_down(p,cr-cl+1);
		LL mid=cl+cr>>1;
		return query2(l,r,p<<1,cl,mid)+query2(l,r,p<<1|1,mid+1,cr);
	}
}
int main()
{
	LL m,i,j,op,x,y;
	LD k;
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=n;i++)scanf("%Lf",&a[i]);
	build(1,n,1);
	while(m--)
	{
		scanf("%lld%lld%lld",&op,&x,&y);
		if(op==1)
		{
			scanf("%Lf",&k);
			update(x,y,k,1,1,n);
		}
		else if(op==2)printf("%.4Lf\n",query(x,y,1,1,n)/(y-x+1));
		else 
		{
			LD sum1=query2(x,y,1,1,n)/(y-x+1);
			LD sum2=query(x,y,1,1,n)/(y-x+1);
			LD ans=sum1-sum2*sum2;
			printf("%.4Lf\n",ans);
		}
	}
	return 0;
}
2024/11/13 22:04
加载中...