【Luogu1471】方差（线段树）

题面

题解

这题太傻比了

把方差公式拆开

维护平方和和区间和

修改就把平方和的公式拆开

简直傻逼的题目

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MAX 150000

#define lson (now<<1)

#define rson (now<<1|1)

struct Node

{

	double s,ps;

	double ly;

}t[MAX<<4];

double a[MAX];

int n,m;

void Build(int now,int l,int r)

{

	if(l==r)

	{

		t[now].s=a[l];

		t[now].ps=a[l]*a[l];

		return;

	}

	int mid=(l+r)>>1;

	Build(lson,l,mid);Build(rson,mid+1,r);

	t[now].s=t[lson].s+t[rson].s;

	t[now].ps=t[lson].ps+t[rson].ps;

}

void pushdown(int now,int l,int r)

{

	double k=t[now].ly;

	int mid=(l+r)>>1;

	t[lson].ly+=k;

	t[rson].ly+=k;

	t[lson].ps+=2*t[lson].s*k+(mid-l+1)*k*k;

	t[rson].ps+=2*t[rson].s*k+(r-mid)*k*k;

	t[lson].s+=(mid-l+1)*k;

	t[rson].s+=(r-mid)*k;

	t[now].ly=0;

}

void putlazy(int now,int l,int r,double k)

{

	t[now].ly+=k;

	t[now].ps+=2*t[now].s*k+(r-l+1)*k*k;

	t[now].s+=(r-l+1)*k;

}

void Modify(int now,int l,int r,int L,int R,double w)

{

	if(L<=l&&r<=R){putlazy(now,l,r,w);return;}

	pushdown(now,l,r);

	int mid=(l+r)>>1;

	if(L<=mid)Modify(lson,l,mid,L,R,w);

	if(R>mid)Modify(rson,mid+1,r,L,R,w);

	t[now].ps=t[lson].ps+t[rson].ps;

	t[now].s=t[lson].s+t[rson].s;

}

double Query1(int now,int l,int r,int L,int R)

{

	if(L<=l&&r<=R)return t[now].s;

	pushdown(now,l,r);

	double ret=0;

	int mid=(l+r)>>1;

	if(L<=mid)ret+=Query1(lson,l,mid,L,R);

	if(R>mid)ret+=Query1(rson,mid+1,r,L,R);

	return ret;

}

double Query2(int now,int l,int r,int L,int R)

{

	if(L<=l&&r<=R)return t[now].ps;

	pushdown(now,l,r);

	double ret=0;

	int mid=(l+r)>>1;

	if(L<=mid)ret+=Query2(lson,l,mid,L,R);

	if(R>mid)ret+=Query2(rson,mid+1,r,L,R);

	return ret;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;++i)scanf("%lf",&a[i]);

	Build(1,1,n);

	int opt,ll,rr;

	double kk;

	while(m--)

	{

		scanf("%d%d%d",&opt,&ll,&rr);

		if(opt==1)

		{

			scanf("%lf",&kk);

			Modify(1,1,n,ll,rr,kk);

		}

		else if(opt==2)

		{

			double ret=Query1(1,1,n,ll,rr);

			printf("%.4lf\n",ret/(rr-ll+1));

		}

		else

		{

			double c1=Query1(1,1,n,ll,rr);

			double c2=Query2(1,1,n,ll,rr);

			double c3=c1/(rr-ll+1);

			double ans=c2-2*c1*c3+(rr-ll+1)*c3*c3;

			printf("%.4lf\n",ans/(rr-ll+1));

		}

	}

	return 0;

}

巴特西

【Luogu1471】方差（线段树）

【Luogu1471】方差（线段树）

题面

题解

最新文章

热门文章