线段树求方差板子题P1417 40分
  • 板块题目总版
  • 楼主GalwayGirl
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/7/14 21:07
  • 上次更新2023/10/27 20:19:19
查看原帖
线段树求方差板子题P1417 40分
327295
GalwayGirl楼主2022/7/14 21:07
#include<bits/stdc++.h>
using namespace std;
long long n,m,op,l,r;
double a[110000],k;
struct xzh
{
	int l,r;
	double add,sum,sqsum;
}tree[110000*4];
void build(long long  p,long long l,long long r)
{
	tree[p].l=l;
	tree[p].r=r;
	if(l==r)
	{
		tree[p].sum=a[l];
		tree[p].sqsum=a[l]*a[l];
		return;
	}
	long long mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
	tree[p].sqsum=tree[p*2].sqsum+tree[p*2+1].sqsum;
}
void spread(long long p)
{
	if(tree[p].add)
	{
		tree[p*2].sqsum+=tree[p].add*tree[p].add*(tree[p*2].l-tree[p*2].r+1)+2.0*tree[p].add*tree[p*2].sum;
		tree[p*2+1].sqsum+=tree[p].add*tree[p].add*(tree[p*2+1].l-tree[p*2+1].r+1)+2.0*tree[p].add*tree[p*2+1].sum;
		tree[p*2].sum+=tree[p].add*(tree[p*2].r-tree[p*2].l+1);
		tree[p*2+1].sum+=tree[p].add*(tree[p*2+1].r-tree[p*2+1].l+1);
		tree[p*2].add+=tree[p].add;
		tree[p*2+1].add+=tree[p].add;	
	}
	tree[p].add=0;
}
void change(long long p,long long l,long long r,double d)
{
	if(l<=tree[p].l&&tree[p].r<=r)
	{
		tree[p].add+=d;
		tree[p].sqsum+=tree[p].sum*2.0*d+d*d*(tree[p].r-tree[p].l+1);
		tree[p].sum+=d*(tree[p].r-tree[p].l+1);
		return;
	}
	spread(p);
	long long mid=(tree[p].l+tree[p].r)/2;
	if(l<=mid)change(p*2,l,r,d);
	if(r>mid)change(p*2+1,l,r,d);
	tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
	tree[p].sqsum=tree[p*2].sqsum+tree[p*2+1].sqsum;
}
double ask1(long long p,long long l,long long r)
{
	double ans=0;
	if(l<=tree[p].l&&tree[p].r<=r)return tree[p].sum;
	spread(p);
	long long mid=(tree[p].l+tree[p].r)/2;
	if(l<=mid)ans+=ask1(p*2,l,r);
	if(r>mid)ans+=ask1(p*2+1,l,r);
	return ans;
}
double ask2(long long p,long long l,long long r)
{
	double ans=0;
	if(l<=tree[p].l&&tree[p].r<=r)return tree[p].sqsum;
	spread(p);
	long long mid=(tree[p].l+tree[p].r)/2;
	if(l<=mid)ans+=ask2(p*2,l,r);
	if(r>mid)ans+=ask2(p*2+1,l,r);
	return ans;
}
int main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
	build(1,1,n);
	while(m--)
	{
		scanf("%lld%lld%lld",&op,&l,&r);
		if(op==1)
		{
			scanf("%lf",&k);
			change(1,l,r,k);
		}
		if(op==2)printf("%.4lf\n",(double)ask1(1,l,r)/(r-l+1));
		if(op==3)
		{
			double pin=(double)ask1(1,l,r)*1.0/(r-l+1);
			printf("%.4lf\n",(double)ask2(1,l,r)*1.0/(r-l+1)-(double)pin*pin);
		}
	}
	return 0;
}
2022/7/14 21:07
加载中...