线段树代码求调,区间加值出错
  • 板块P1471 方差
  • 楼主Fur_Zes
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/23 11:31
  • 上次更新2024/8/23 14:25:26
查看原帖
线段树代码求调,区间加值出错
157820
Fur_Zes楼主2024/8/23 11:31
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ll n,m,a[100005],op,x,y;
ld k;
struct stu{
	ll l,r;
	ld sum,add;
}tr[400005];
void pushup(ll u)
{
	tr[u].sum=(tr[u<<1].sum+tr[u<<1|1].sum)*1.00000;
}
void build(ll u,ll l,ll r)
{
	tr[u].l=l,tr[u].r=r,tr[u].add=0.00000;
	if(l==r)
	{
		tr[u].sum=a[l]*1.00000;
		return;
	}
	ll mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
}
void pushdown(ll u)
{
	if(tr[u].add)
	{
		tr[u<<1].add+=tr[u].add*1.00000;
		tr[u<<1].sum+=(tr[u<<1].r-tr[u<<1].l+1)*1.00000*tr[u].add;
		tr[u<<1|1].add+=tr[u].add*1.00000;
		tr[u<<1|1].sum+=(tr[u<<1|1].r-tr[u<<1|1].l+1)*1.00000*tr[u].add;
		tr[u].add=0.00000;
	}
}
void modify_sum(ll u,ll l,ll r,ll v)
{
	if(tr[u].l>r||tr[u].r<l) return;
	if(tr[u].l>=l&&tr[u].r<=r)
	{
		tr[u].add=(tr[u].add+v)*1.00000;
		tr[u].sum=(tr[u].sum+(tr[u].r-tr[u].l+1)*v)*1.00000;
		return;
	}
	pushdown(u);
	modify_sum(u<<1,l,r,v);
	modify_sum(u<<1|1,l,r,v);
	pushup(u);
}
ld query(ll u,ll l,ll r)
{
	if(tr[u].l>r||tr[u].r<l) return 0.00000;
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum*1.00000;
	pushdown(u);
	return query(u<<1,l,r)*query(u<<1|1,l,r)*1.00000;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	build(1,1,n);
	while(m--)
	{
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			modify_sum(1,x,y,k);
		}
	/*	else if(op==2)
		{
			cin>>x>>y;
			printf("%.5lf\n",query(1,x,y)/(y-x+1)*(1.00000));
		}
		else
		{
			cin>>x>>y;
			ld fir,sec,thi,ave,con;
			fir=sec=thi=ave=con=0.00000;
			con=1.00000/(y-x+1)*1.00000;
			ave=query(1,x,y)*1.00000/(y-x+1);
			fir=query(1,x,y)*query(1,x,y)*1.00000;
			sec=2.00000*query(1,x,y)*ave;
			thi=ave*ave;
			printf("%.5lf\n",(fir+sec+thi)*con);
		}*/
	}
	for(int i=1;i<=4*n;i++)
	cout<<tr[i].sum<<" ";
	return 0;
}

不知道为什么pushdown进不去,导致区间加值操作废了一样

2024/8/23 11:31
加载中...