新手自学线段树,WA 40pts 求助!!!
  • 板块P1471 方差
  • 楼主zMinYu
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/4/14 18:21
  • 上次更新2023/10/23 18:31:22
查看原帖
新手自学线段树,WA 40pts 求助!!!
882092
zMinYu楼主2023/4/14 18:21
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define db double
const int N=1e5+10;
struct node
{
	ll  l,r;
	db num,pf; 
}tr[N*4];
db a[N],lazy[N*4];
void pushup(ll u)
{
	tr[u].num=tr[u<<1].num+tr[u<<1|1].num;
	tr[u].pf=tr[u<<1].pf+tr[u<<1|1].pf;
}
void build(ll u,ll l,ll r)
{
	lazy[u]=0;
	if(l==r)
	{
		tr[u].num=a[l];
		tr[u].pf=a[l]*a[l];
		tr[u].l=l;
		tr[u].r=r;
	}
	else
	{
		tr[u].l=l;
		tr[u].r=r;
		ll mid=(l+r)/2;
		build(u<<1,l,mid);
		build(u<<1|1,mid+1,r);
		pushup(u);
	}
}
//点修改
//void modify(int u,int l,int r,int x,int k) //将编号为x的值加k
//{
//	if(l==r)
//	{
//		tr[u].num=tr[u].num+k;
//	}
//	else
//	{
//		int mid=(l+r)/2;
//		if(x<=mid) modify(u<<1,l,mid,x,k);
//		if(x>mid) modify(u<<1,mid+1,r,x,k);
//		pushup(u);
//	}
//}
void pushdown(ll u,ll ln,ll rn)
{
	lazy[u<<1]+=lazy[u];
	lazy[u<<1|1]+=lazy[u];
	tr[u<<1].pf+=ln*lazy[u]*lazy[u]+2*lazy[u]*tr[u<<1].num;
	tr[u<<1|1].pf+=rn*lazy[u]*lazy[u]+2*lazy[u]*tr[u<<1|1].num;
	tr[u<<1].num+=lazy[u]*ln;
	tr[u<<1|1].num+=lazy[u]*rn;
	lazy[u]=0;
}
void modify(ll u,ll L,ll R,db k)
{
	if(tr[u].l>=L&&tr[u].r<=R)
	{
		tr[u].pf+=(tr[u].r-tr[u].l+1)*k*k+2*k*tr[u].num;
		tr[u].num+=(tr[u].r-tr[u].l+1)*k;
		lazy[u]+=k;
	}
	else
	{
		ll mid=(tr[u].l+tr[u].r)/2;
		pushdown(u,mid-tr[u].l+1,tr[u].r-mid);
		if(L<=mid) modify(u<<1,L,R,k);
		if(R>mid) modify(u<<1|1,L,R,k);
		pushup(u);
	}
}
db query(ll u,ll L,ll R)
{
	if(tr[u].l>=L&&tr[u].r<=R)
	{
		return tr[u].num;
	}
	ll mid=(tr[u].l+tr[u].r)/2;
	pushdown(u,mid-tr[u].l+1,tr[u].r-mid);
	db ans=0.0000;
	if(L<=mid) ans+=query(u<<1,L,R);
	if(R>mid) ans+=query(u<<1|1,L,R);
	return ans;
}
db querypf(ll u,ll L,ll R)
{
	if(tr[u].l>=L&&tr[u].r<=R)
	{
		return tr[u].pf;
	}
	ll mid=(tr[u].l+tr[u].r)/2;
	pushdown(u,mid-tr[u].l+1,tr[u].r-mid);
	db ans=0.0000;
	if(L<=mid) ans+=query(u<<1,L,R);
	if(R>mid) ans+=query(u<<1|1,L,R);
	return ans;
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	ll op,x,y;
	db k;
	while(m--)
	{
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			modify(1,x,y,k);
		}
		else if(op==2)
		{
			cin>>x>>y;
			printf("%.4f\n",query(1,x,y)/(y-x+1));
		}
		else if(op==3)
		{
			cin>>x>>y;
			k=query(1,x,y)/((db)(y-x+1.0000));
			printf("%.4f\n",querypf(1,x,y)/(y-x+1)-k*k);
		}
	}
	return 0;
} 
2023/4/14 18:21
加载中...