蒟蒻全Wa求调
  • 板块P1471 方差
  • 楼主忘怜城羡
  • 当前回复3
  • 已保存回复3
  • 发布时间2024/5/22 21:06
  • 上次更新2024/5/23 07:48:09
查看原帖
蒟蒻全Wa求调
374756
忘怜城羡楼主2024/5/22 21:06

rt

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+7;
struct node{
	double cnt,sum,lazytag;
	node operator + (const node &x){
		return (node){x.cnt+cnt,x.sum+sum,0.00};
	}
}tree[MAXN<<4];
double a[MAXN];
void pushdown(int p,int l,int r)
{
	int mid=(l+r)>>1;
	tree[p*2].cnt=tree[p*2].cnt+2.0000*tree[p].lazytag*tree[p*2].sum+(mid-l+1)*tree[p].lazytag*tree[p].lazytag;
	tree[p*2+1].cnt=tree[p*2+1].cnt+2.0000*tree[p].lazytag*tree[p*2+1].sum+(r-mid)*tree[p].lazytag*tree[p].lazytag;
	tree[p*2].sum+=double(mid-l+r)*tree[p].lazytag;
	tree[p*2+1].sum+=double(r-mid)*tree[p].lazytag;
	tree[p*2].lazytag+=tree[p].lazytag;
	tree[p*2+1].lazytag+=tree[p].lazytag;
	tree[p].lazytag=0.0000;
}
void build(int p,int l,int r)
{
	if(l==r)
	{
		tree[p].sum=a[l];
		tree[p].cnt=a[l]*a[l];
		tree[p].lazytag=0.0000;
		return ;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tree[p]=tree[p*2]+tree[p*2+1];
}
void change(int p,int l,int r,int x,int y,double k)
{
	if(x<=l&&r<=y)
	{
		tree[p].cnt=tree[p].cnt+2.0000*k*tree[p].sum+double(r-l+1)*k*k;
		tree[p].sum=tree[p].sum+k*double(r-l+1);
		tree[p].lazytag=k;
		return ;
	}
	int mid=(l+r)>>1;
	if(tree[p].lazytag)
		pushdown(p,l,r);
	if(x<=mid)
		change(p*2,l,mid,x,y,k);
	else
		change(p*2+1,mid+1,r,x,y,k);
	tree[p]=tree[p*2]+tree[p*2+1];
}
node query(int p,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)
		return tree[p];
	int mid=(l+r)>>1;
	if(tree[p].lazytag)
		pushdown(p,l,r);
	node ans={0,0,0};
	if(x<=mid)
		ans=ans+query(p*2,l,mid,x,y);
	if(mid<y)
		ans=ans+query(p*2+1,mid+1,r,x,y);
	return ans;
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i(1);i<=n;++i)
		scanf("%lf",&a[i]);
	build(1,1,n);
	while(m--)
	{
		int opt,x,y;
		double k;
		scanf("%d",&opt);
		if(opt==1)
		{
			scanf("%d%d%lf",&x,&y,&k);
			change(1,1,n,x,y,k);
		}
		else
		{
			scanf("%d%d",&x,&y);
			node ans=query(1,1,n,x,y);
			if(opt==2)
				printf("%.4lf\n",ans.sum/double(y-x+1));
			else
				printf("%.4lf\n",ans.cnt/double(y-x+1)-ans.sum*ans.sum/double(y-x+1)/double(y-x+1));
		}
	}
	return 0;
}
2024/5/22 21:06
加载中...