样例过了但是全WA线段树求调!
  • 板块P1471 方差
  • 楼主Fj234014
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/29 22:21
  • 上次更新2024/5/29 22:22:47
查看原帖
样例过了但是全WA线段树求调!
502538
Fj234014楼主2024/5/29 22:21
#define Frosty_Jackal made
#include<bits/stdc++.h>
#define MAXN 300002
using namespace std;

struct node
{
	int l,r;
	double sum,add;
	double sum2;
}t[MAXN*4];
int n,m;
double  s[MAXN];

void build(int p,int l,int r)
{
	
	t[p].l=l;t[p].r=r;
	if(l==r){ t[p].sum= s[l] ;t[p].sum2 = t[p].sum *t[p].sum; return ;}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].sum=t[p*2].sum + t[p*2+1].sum;
	t[p].sum2= t[p*2].sum2 + t[p*2+1].sum2;
}

void pushdown(int p)
{
	if(t[p].add)
	{
		int k=t[p].add;
		t[p*2].sum2 += (t[p*2].r-t[p*2].l+1)*k*k + 2*t[p*2].sum*k;  t[p*2].sum+=(t[p*2].r-t[p*2].l+1)*k;
		t[p*2+1].sum2 += (t[p*2+1].r-t[p*2+1].l+1)*k*k + 2*t[p*2+1].sum*k;  t[p*2+1].sum+=(t[p*2+1].r-t[p*2+1].l+1)*k;
		t[p].add=0;
		t[p*2].add+=k;
		t[p*2+1].add+=k;
	}
}

void chg(int p,int l,int r,double k)
{
	if(l<=t[p].l && r>=t[p].r){ t[p].add+=k;t[p].sum2 += (t[p].r-t[p].l+1)*k*k + 2*t[p].sum*k;  t[p].sum+=(t[p].r-t[p].l+1)*k;  return ; }
	pushdown(p);
	int mid=(t[p].l+t[p].r)/2;
	if(l<=mid) chg(p*2,l,r,k);
	if(r>mid) chg(p*2+1,l,r,k);
	t[p].sum = t[p*2].sum +t[p*2+1].sum;
	t[p].sum2= t[p*2].sum2 + t[p*2+1].sum2;
}

double ask1(int p,int l,int r)
{
	if(l<=t[p].l && r>=t[p].r){ return t[p].sum;}
	pushdown(p);
	int mid=(t[p].l+t[p].r)/2;double ret=0;
	if(l<=mid) ret+=ask1(p*2,l,r);
	if(r>mid) ret+=ask1(p*2+1,l,r);
	return ret;
}
double ask2(int p,int l,int r)
{
	if(l<=t[p].l && r>=t[p].r){ return t[p].sum2;}
	pushdown(p);
	int mid=(t[p].l+t[p].r)/2;double ret=0;
	if(l<=mid) ret+=ask2(p*2,l,r);
	if(r>mid) ret+=ask2(p*2+1,l,r);
	return ret;
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i) scanf("%lf",&s[i]);
	build(1,1,n);
	while(m--)
	{
		int op,l,r;double x;
		scanf("%d%d%d",&op,&l,&r);
		if(op==1) 
		{
			cin>>x;
			chg(1,l,r,x);
		}
		else if(op==2)	printf("%.4lf\n",ask1(1,l,r)/(r-l+1));
		else
		{
			double sum2=ask2(1,l,r)/(r-l+1),sum1=ask1(1,l,r)/(r-l+1);
			printf("%.4lf\n",sum2-(sum1) * (sum1) );
		}
	}
	return 0;
}
/*
  
 */ 




2024/5/29 22:21
加载中...