萌新线段树求助,输出尽是些-inf,自我感觉思路挺正确的
  • 板块P1471 方差
  • 楼主later,when
  • 当前回复4
  • 已保存回复4
  • 发布时间2020/8/9 10:01
  • 上次更新2023/11/6 20:52:44
查看原帖
萌新线段树求助,输出尽是些-inf,自我感觉思路挺正确的
219298
later,when楼主2020/8/9 10:01
#include<bits/stdc++.h>
using namespace std;
struct tree
{
	int l,r;
	double w,pow,lz;
}a[400005];
int n,m,x,y;
double o;
int read()
{
	int x=0,t=1;
	char ch=getchar();
	while (!isdigit(ch))
	{
		if (ch=='-')
			t=-1;
		ch=getchar();	
	}
	while (isdigit(ch))
	{
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return x*t;
}
void pushdown(int k)
{
	double oo=a[k].lz;
	int s=a[k<<1].r-a[k<<1].l+1;
	double p=a[k<<1].w;
	a[k<<1].w+=s*oo;
	a[k<<1].pow+=s*oo*oo+2*oo*p;
	a[k<<1].lz=oo;
	s=a[k<<1|1].r-a[k<<1|1].l+1,p=a[k<<1|1].w;
	a[k<<1|1].w+=s*oo;
	a[k<<1|1].pow+=s*oo*oo+2*oo*p;
	a[k<<1|1].lz=oo;
	return ;	
}
void build(int k,int ll,int rr)
{
	a[k].l=ll;
	a[k].r=rr;
	a[k].lz=0;
	if (ll==rr)
	{
		//cout<<1;
		scanf("%lf",&a[k].w);
		a[k].pow=a[k].w*a[k].w;
		return ;
	}
	int mid=(ll+rr)>>1;
	build(k<<1,ll,mid);
	build(k<<1|1,mid+1,rr);
	a[k].w=a[k<<1].w+a[k<<1|1].w;
	a[k].pow=a[k<<1].pow+a[k<<1|1].pow;
}
void update(int k)
{
	int ll=a[k].l;
	int rr=a[k].r;
	if (ll>=x&&rr<=y)
	{	
		int s=rr-ll+1;
		double p=a[k].w;
		a[k].w+=s*o;
		a[k].pow+=s*o*o+2*o*p;
		a[k].lz=o;
		return ;	
	}
	int mid=(ll+rr)>>1;
	if (a[k].lz)
		pushdown(k);
	if (x<=mid)
		update(k<<1);
	if (y>mid)
		update(k<<1|1);
	a[k].w=a[k<<1].w+a[k<<1|1].w;
	a[k].pow=a[k<<1].pow+a[k<<1|1].pow;	
	//cout<<a[k].w<<" "<<a[k].pow<<endl;
	return ;		
} 
double print1(int k)
{
	int ll=a[k].l;
	int rr=a[k].r;
	if (ll>=x&&rr<=y)
		return a[k].w;
	int mid=(ll+rr)>>1;
	double ans=0;
	if (a[k].lz)
		pushdown(k);
	if (x<=mid)
		ans+=print1(k<<1);
	if (y>mid)
		ans+=print1(k<<1|1);	
	return ans;			
} 
tree print2(int k)
{
	int ll=a[k].l;
	int rr=a[k].r;
	tree b;
	if (ll>=x&&rr<=y)
	{
		b.w=a[k].w;
		b.pow=a[k].pow;
		return b;	
	}
	int mid=(ll+rr)>>1;
	tree c;
	if (a[k].lz)
		pushdown(k);
	if (x<=mid)
	{
		c=print2(k<<1);
		b.w+=c.w;
		b.pow+=c.pow;
	}
	if (y>mid)
	{
		c=print2(k<<1|1);
		b.w+=c.w;
		b.pow+=c.pow;
	}
	//cout<<b.w<<" "<<b.pow<<endl;
	return b;			
} 
int main()
{
	cin>>n>>m;
	build(1,1,n);
	//for (int i=1;i<=n;++i)
	//	cout<<a[i].w<<" "<<a[i].pow<<endl;
	for (int i=1;i<=m;++i)
	{
		int p=read();
		x=read();
		y=read();
		if (p==1)
		{
			scanf("%lf",&o);
			printf("%lf\n",o);	
			update(1);
			continue;
		}
		if (p==2)
		{
			//cout<<1;
			printf("%.4f\n",print1(1)/(y-x+1));
			continue;
		}
		tree e=print2(1);
		//cout<<e.pow<<" "<<e.w<<endl;
		printf("%.4f\n",(e.pow-(e.w*e.w/(y-x+1)))/(y+1-x));
	}
	return 0;
}
2020/8/9 10:01
加载中...