Need Help,全WA了
  • 板块P1471 方差
  • 楼主Amon_Xolotl
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/8/22 16:34
  • 上次更新2023/11/3 01:57:43
查看原帖
Need Help,全WA了
428449
Amon_Xolotl楼主2023/8/22 16:34
#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=1e5+7;
int n,m;
db a[N+1];
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-')
		{
			f=-f;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}
struct tree
{
	db sum,sos,flag;
}tr[N<<2];
void pushup(int rt,int l,int r)
{
	tr[rt].sos=tr[rt<<1].sos+tr[rt<<1|1].sos;
	tr[rt].sum=tr[rt<<1].sum+tr[rt<<1|1].sum;
}
void build(int rt,int l,int r)
{
	tr[rt].sum=tr[rt].sos=tr[rt].flag=0;
	if(l==r)
	{
		tr[rt].sum=a[l];
		tr[rt].sos=a[l]*a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	pushup(rt,l,r);
}
inline void pushdown(int rt,int l,int r)
{
	if(tr[rt].flag==0)
	{
		return;
	}
	int mid=(l+r)>>1;
	tr[rt<<1].sos+=(db)(mid-l+1)*tr[rt].flag*tr[rt].flag+(db)2*tr[rt].flag*tr[rt<<1].sum;
	tr[rt<<1|1].sos+=(db)(r-mid)*tr[rt].flag*tr[rt].flag+(db)2*tr[rt].flag*tr[rt<<1].sum;
	tr[rt<<1].sum+=tr[rt].flag*(db)(mid-l+1),tr[rt<<1|1].sum+=tr[rt].flag*(db)(r-mid);
	tr[rt<<1].flag=tr[rt<<1|1].flag=tr[rt].flag;
	tr[rt].flag=(db)0;
}
inline void update(int rt,int l,int r,int x,int y,db v)
{
	if(l>=x&&r<=y)
	{
		tr[rt].flag+=v;
		tr[rt].sos+=(db)(r-l+1)*v*v+(db)2*v*tr[rt].sum;
		tr[rt].sum+=v*(db)(r-l+1);
		return;
	}
	pushdown(rt,l,r);
	int mid=(l+r)>>1;
	if(x<=mid)
	{
		update(rt<<1,l,mid,x,y,v);
	}
	if(y>mid)
	{
		update(rt<<1|1,mid+1,r,x,y,v);
	}
	pushup(rt,l,r);
	return;
}
inline db ask(int rt,int l,int r,int x,int y)
{
	if(l>=x&&r<=y)
	{
		return tr[rt].sum;
	}
	db ans=0;
	int mid=(l+r)>>1;
	pushdown(rt,l,r);
	if(x<=mid)
	{
		ans+=ask(rt<<1,l,mid,x,y);
	}
	if(y>mid)
	{
		ans+=ask(rt<<1|1,mid+1,r,x,y);
	}
	pushup(rt,l,r);
	return ans;
}
inline db query(int rt,int l,int r,int x,int y)
{
	if(l>=x&&r<=y)
	{
		return tr[rt].sos;
	}
	int mid=(l+r)>>1;
	db ans=0;
	pushdown(rt,l,r);
	if(x<=mid)
	{
		ans+=query(rt<<1,l,mid,x,y);
	}
	if(mid<y)
	{
		ans+=query(rt<<1|1,mid+1,r,x,y);
	}
	pushup(rt,l,r);
	return ans;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
	{
		scanf("%lf",&a[i]);
	}
	build(1,1,n);
	while(m--)
	{
		int opt,x,y;
		opt=read(),x=read(),y=read();
		if(opt==1)
		{
			db z;
			scanf("%lf",&z);
			update(1,1,n,x,y,z);
		}
		else if(opt==2)
		{
			printf("%.4lf\n",ask(1,1,n,x,y)/(db)(y-x+1));
		}
		else
		{
			printf("%.4lf\n",query(1,1,n,x,y)/(db)(y-x+1)-pow(ask(1,1,n,x,y)/(db)(y-x+1),2));
		}
	}
	return 0;
}
2023/8/22 16:34
加载中...