C语言#萌新70分求助
  • 板块P1471 方差
  • 楼主westernhan
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/9/6 22:57
  • 上次更新2023/10/27 12:22:24
查看原帖
C语言#萌新70分求助
677939
westernhan楼主2022/9/6 22:57
#include<stdio.h>
#include<math.h>
typedef double le;
int n,m,c,xi,yi,num,id[100005];
le a[100005],k;
typedef struct
{
	int l,r,len;
	le sum,lzy,sque;
}hh;
hh b[100005];
void add(int w,int li,le e)
{
	if (id[w]==id[li])
	{
		for (int x=w;x<=li;x++)
		{
			b[id[w]].sque+=2*a[x]*e+e*e;
			a[x]+=e;
			b[id[w]].sum+=e;
		}
	}
	else
	{
		for (int x=id[w]+1;x<id[li];x++)
		{
			b[x].sque+=b[x].sum*2*e+e*e*b[x].len;
			b[x].sum+=b[x].len*e;
			b[x].lzy+=e;
		}
		for (int x=w;x<=b[id[w]].r;x++)
		{
			b[id[w]].sque+=2*a[x]*e+e*e;
			a[x]+=e,b[id[w]].sum+=e;
		}
		for (int x=li;x>=b[id[li]].l;x--)
		{
			b[id[li]].sque+=2*a[x]*e+e*e;
			a[x]+=e;b[id[li]].sum+=e;
		}
	}
}
le getsum(int w,int li,int ch)
{
	le u=0;
	if (ch==1)
	{
		if (id[w]==id[li])
		{
			for (int x=w;x<=li;x++)
				u+=a[x]+b[id[w]].lzy;
		}
		else
		{
			for (int x=id[w]+1;x<id[li];x++)
				u+=b[x].sum;
			for (int x=w;x<=b[id[w]].r;x++)
				u+=a[x]+b[id[w]].lzy;
			for (int x=li;x>=b[id[li]].l;x--)
				u+=a[x]+b[id[li]].lzy;
		}
	}
	else
	{
		if (id[w]==id[li])
		{
			for (int x=w;x<=li;x++)
				u+=(a[x]+b[id[w]].lzy)*(a[x]+b[id[w]].lzy);
		}
		else
		{
			for (int x=id[w]+1;x<id[li];x++)
				u+=b[x].sque;
			for (int x=w;x<=b[id[w]].r;x++)
				u+=(a[x]+b[id[w]].lzy)*(a[x]+b[id[w]].lzy);
			for (int x=li;x>=b[id[li]].l;x--)
				u+=(a[x]+b[id[li]].lzy)*(a[x]+b[id[li]].lzy);
		}
	}
	return u;
}
int main(void)
{
	scanf("%d%d",&n,&m);
	for (int x=1;x<=n;x++)
		scanf("%lf",a+x);
	num=sqrt(n);
	for (int x=1;x<=num;x++)
	{
		b[x].l=n/num*(x-1)+1;
		b[x].r=n/num*x;
		b[x].lzy=0;
		b[x].len=b[x].r-b[x].l+1;
		for (int y=b[x].l;y<=b[x].r;y++)
			b[x].sum+=a[y],b[x].sque+=a[y]*a[y],id[y]=x;
	}
	for (int x=b[num].r+1;x<=n;x++)
		b[num].sum+=a[x],b[num].sque+=a[x]*a[x],id[x]=num;
	b[num].r=n;b[num].len=b[num].r-b[num].l+1;
	for (int x=1;x<=m;x++)
	{
		scanf("%d%d%d",&c,&xi,&yi);
		if (c==1)
		{
			scanf("%lf",&k);
			add(xi,yi,k);
		}
		else
		{
			le v=getsum(xi,yi,1)/(le)(yi-xi+1);
			if (c==2)
				printf("%.4lf\n",v);
			else if (c==3)
				printf("%.4lf\n",getsum(xi,yi,2)/((le)(yi-xi+1))-v*v);
		}
	}
	return 0;
}

总是会WA掉那三个数据最多的点。

2022/9/6 22:57
加载中...