样例没过,猫猫难过QAQ
  • 板块P1471 方差
  • 楼主Atri_Lobato
  • 当前回复4
  • 已保存回复5
  • 发布时间2024/8/15 20:45
  • 上次更新2024/8/16 00:32:07
查看原帖
样例没过,猫猫难过QAQ
1065103
Atri_Lobato楼主2024/8/15 20:45

线段树怎么debug啊

#include<iostream>
using namespace std;
int n,m;
double num[100005];
double sum1[500005];
double sum2[500005];
struct Line
{
	int l,r;
	double add;
}line[500005];
void build(int l,int r,int now)
{
	line[now].l=l;
	line[now].r=r;
	line[now].add=0;
	if(l==r)
	{
		sum1[now]=num[l];
		sum2[now]=num[l]*num[l];
		return;
	}
	int mid=(r+l)>>1;
	build(l,mid,now*2);
	build(mid+1,r,now*2+1);
	sum1[now]=sum1[now*2]+sum1[now*2+1];
	sum2[now]=sum2[now*2]+sum2[now*2+1];
}
void Add(int l,int r,double value,int now)
{
	line[now].add+=value;
	sum2[now]+=(2*sum1[now]*value+(r-l+1)*value*value);
	sum1[now]+=(r-l+1)*value;
}
void pushdown(int now)
{
	if(line[now].add==0)
	return;
	Add(line[now*2].l,line[now*2].r,line[now].add,now*2);
	Add(line[now*2+1].l,line[now*2+1].r,line[now].add,now*2+1);
	line[now].add=0;
}
void modify(int l,int r,double value,int now)
{
	if(line[now].l>=l&&line[now].r<=r)
	{
		Add(line[now].l,line[now].r,value,now);
		return;
	}
	pushdown(now);
	if(r>=line[now*2+1].l)
	{
		modify(l,r,value,now*2+1);
	}
	if(l<=line[now*2].r)
	{
		modify(l,r,value,now*2);
	}
	sum1[now]=sum1[now*2]+sum1[now*2+1];
	sum2[now]=sum2[now*2]+sum2[now*2+1];
}
double query1(int l,int r,int now)
{
	if(line[now].l>=l&&line[now].r<=r)
	{
		return sum1[now];
	}
	pushdown(now);
	double ans=0;
	if(r>=line[now*2+1].l)
	{
		ans+=query1(l,r,now*2+1);
	}
	if(l<=line[now*2].r)
	{
		ans+=query1(l,r,now*2);
	}
	return ans;
}
double query2(int l,int r,int now)
{
	if(line[now].l>=l&&line[now].r<=r)
	{
		return sum2[now];
	}
	pushdown(now);
	double ans=0;
	if(r>=line[now*2+1].l)
	{
		ans+=query2(l,r,now*2+1);
	}
	if(l<=line[now*2].r)
	{
		ans+=query2(l,r,now*2);
	}
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%lf",&num[i]);
	}
	build(1,n,1);
	for(int i=1;i<=m;i++)
	{
		int t;
		scanf("%d",&t);
		if(t==1)
		{
			int x,y,k;
			scanf("%d%d%lf",&x,&y,&k);
			modify(x,y,k,1);
		}
		if(t==2)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			printf("%.4lf\n",query1(x,y,1)*1.0/(y-x+1));
		}
		if(t==3)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			double tmp1,tmp2;
			tmp1=query2(x,y,1);
			tmp2=query1(x,y,1)*1.0/(y-x+1);
			printf("%.4lf\n",(tmp1/(y-x+1)-tmp2*tmp2));
		}
	}
	return 0;
}
2024/8/15 20:45
加载中...