求助 0PTS
  • 板块P1471 方差
  • 楼主D2019ly
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/2/1 11:43
  • 上次更新2023/10/24 02:15:25
查看原帖
求助 0PTS
843293
D2019ly楼主2023/2/1 11:43

有人能帮忙看看吗

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,m;
struct SegTree{
	int l,r;double s1,s2,add;
}tr[N<<2];
void pushup(int p)
{
	tr[p].s1=tr[p<<1].s1+tr[p<<1|1].s1;
	tr[p].s2=tr[p<<1].s2+tr[p<<1|1].s2;
}
void pushdown(int p)
{
	int mid=(tr[p].l+tr[p].r)/2;
	tr[p<<1].add+=tr[p].add;
	tr[p<<1|1].add+=tr[p].add;
	
	tr[p<<1].s2+=2*tr[p].add*tr[p<<1].s1+(tr[p<<1].r-tr[p<<1].l+1)*tr[p].add*tr[p].add;
	tr[p<<1|1].s2+=2*tr[p].add*tr[p<<1|1].s1+(tr[p<<1|1].r-tr[p<<1|1].l+1)*tr[p].add*tr[p].add;
	
	tr[p<<1].s1+=tr[p].add*(tr[p<<1].r-tr[p<<1].l+1);
	tr[p<<1|1].s1+=tr[p].add*(tr[p<<1|1].r-tr[p<<1|1].l+1);
	tr[p].add=0;
}
void build(int p,int l,int r)
{
	tr[p].l=l,tr[p].r=r;
	if(l==r)
	{
		double x;cin>>x;
		tr[p].s1=x,tr[p].s2=x*x;
		return ;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	pushup(p);
}
void modify(int p,int l,int r,double k)
{
	if(l<=tr[p].l&&r>=tr[p].r)
	{
		tr[p].add+=1.0*k;
		tr[p].s2+=2.0*k*tr[p].s1+(tr[p].r-tr[p].l+1)*k*k;
		tr[p].s1+=1.0*(tr[p].r-tr[p].l+1)*k;
		return ;
	}
	pushdown(p);
	int mid=(tr[p].l+tr[p].r)/2.0;
	if(l<=mid)modify(p<<1,l,r,k);
	if(r>mid)modify(p<<1|1,l,r,k);
	pushup(p);
}
int q1(int p,int l,int r)
{
	if(l<=tr[p].l&&r>=tr[p].r)return tr[p].s1;
	int sum=0;
	int mid=(tr[p].l+tr[p].r)/2.0;
	pushdown(p);
	if(l<=mid)sum+=q1(p<<1,l,r);
	if(r>mid)sum+=q1(p<<1|1,l,r);
	return sum;
}
int q2(int p,int l,int r)
{
	if(l<=tr[p].l&&r>=tr[p].r)return tr[p].s2;
	int sum=0;
	int mid=(tr[p].l+tr[p].r)/2;
	pushdown(p);
	if(l<=mid)sum+=q2(p<<1,l,r);
	if(r>mid)sum+=q2(p<<1|1,l,r);
	return sum;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		double op,x,y,k;
		cin>>op;
		if(op==1)
		{
			cin>>x>>y>>k;
			modify(1,x,y,k);
		}
		if(op==2)
		{
			cin>>x>>y;
			int s1=q1(1,x,y);
			printf("%.4lf\n",(double)(s1)/(double)(y-x+1));
		}
		if(op==3)
		{
			cin>>x>>y;
			double s1=q2(1,x,y)/(y-x+1),s2=q1(1,x,y)/(y-x+1);
			double ans=s1-s2*s2; 
			printf("%.4lf\n",ans);
		}
	}
}
2023/2/1 11:43
加载中...