求助实在调不出来,样例没过,但40分
  • 板块P1471 方差
  • 楼主hmr26108
  • 当前回复30
  • 已保存回复30
  • 发布时间2023/8/29 18:17
  • 上次更新2023/11/3 00:28:39
查看原帖
求助实在调不出来,样例没过,但40分
473710
hmr26108楼主2023/8/29 18:17
#include<bits/stdc++.h>
#define maxn 100010
using namespace std;
double a[maxn];
int n,m;
struct node
{
	int left,right;
	double sum,sum2,lazy;
}t[maxn*4];

int len(int id)
{
	return t[id].right-t[id].left+1;
}
void update(int id)
{
	t[id].sum=t[id<<1|1].sum+t[id<<1].sum;
	t[id].sum2=t[id<<1].sum2+t[id<<1|1].sum2;
}
void build(int id,int l,int r)
{
	t[id].left=l,t[id].right=r;
	t[id].lazy=0;
	if(l==r)
	{
		t[id].sum=a[l];
		t[id].sum2=a[l]*a[l];
		return;
	}	
	int mid=(l+r)/2;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	update(id);
}
void pushdown(int id)
{
	if(t[id].lazy)
	{
		t[id<<1].lazy+=t[id].lazy;
		t[id<<1|1].lazy+=t[id].lazy;
		t[id<<1].sum+=t[id].lazy*len(id<<1);
		t[id<<1|1].sum+=t[id].lazy*len(id<<1|1);
		t[id<<1].sum2+=2.0*t[id].lazy*t[id<<1].sum+1.0*len(id<<1)*t[id].lazy*t[id].lazy;
		t[id<<1|1].sum2+=2.0*t[id].lazy*t[id<<1|1].sum+1.0*len(id<<1|1)*t[id].lazy*t[id].lazy;
		t[id].lazy=0;
	}
}
void change(int id,int l,int r,double d)
{
	if(t[id].left==l&&t[id].right==r)
	{
		t[id].lazy+=d;
		t[id].sum+=1.0*len(id)*d;
		t[id].sum2+=2.0*d*t[id].sum+1.0*len(id)*d*d;
		return;
	}
	pushdown(id);
	if(r<=t[id<<1].right) change(id<<1,l,r,d);
	else if(l>=t[id<<1|1].left) change(id<<1|1,l,r,d);
	else 
	{
		change(id<<1,l,t[id<<1].right,d);
		change(id<<1|1,t[id<<1|1].left,r,d);
	}
	update(id);
}
double query(int id,int l,int r)
{
	if(t[id].left==l&&t[id].right==r)
	{
		return t[id].sum;
	}
	pushdown(id);
	if(r<=t[id<<1].right) return query(id<<1,l,r);
	else if(l>=t[id<<1|1].left) return query(id<<1|1,l,r);
	else 
	{
		return query(id<<1,l,t[id<<1].right)+query(id<<1|1,t[id<<1|1].left,r);
	}
	update(id);
}
double query2(int id,int l,int r)
{
	if(t[id].left==l&&t[id].right==r)
	{
		return t[id].sum2;
	}
	pushdown(id);
	if(r<=t[id<<1].right) return query2(id<<1,l,r);
	else if(l>=t[id<<1|1].left) return query2(id<<1|1,l,r);
	else 
	{
		return query2(id<<1,l,t[id<<1].right)+query2(id<<1|1,t[id<<1|1].left,r);
	}
	update(id);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		int opt,x,y;
		double z;
		scanf("%d",&opt);
		if(opt==1)
		{
			scanf("%d%d%lf",&x,&y,&z);
			change(1,x,y,z);
		}
		else if(opt==2)
		{
			scanf("%d%d",&x,&y);
			printf("%.4lf\n",query(1,x,y)/(y-x+1)*1.0);
		}
		else 
		{
			scanf("%d%d",&x,&y);
			printf("%.4lf\n",(query2(1,x,y)/(y-x+1)*1.0)-(query(1,x,y)/(y-x+1)*1.0)*(query(1,x,y)/(y-x+1)*1.0));
		}
	}
}

测试是维护平方和那里出错了,但就是没找到

2023/8/29 18:17
加载中...