0pts求调
  • 板块P1471 方差
  • 楼主WhiteNight__
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/6 17:27
  • 上次更新2024/7/6 19:41:48
查看原帖
0pts求调
1098596
WhiteNight__楼主2024/7/6 17:27
#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

#define ll long long
#define MAXN 120050

int n , m;
double a[MAXN];

struct Tree {
	int l , r;
	double s , s2 , ad;
}t[MAXN*4];

void unionn (int num)
{
	t[num].s = t[num*2].s + t[num*2+1].s;
	t[num].s2 = t[num*2].s2 + t[num*2+1].s2;
	return;
}

void down (int num)
{
	double &ad = t[num].ad;
	Tree &lson = t[num*2] , &rson = t[num*2+1];
	
	if(abs (ad) <= 0.0000001)
		return;
	
	lson.s2 += (lson.r - lson.l + 1) * ad * ad + 2 * ad * lson.s;
	lson.ad += ad;
	lson.s += (lson.r - lson.l + 1) * ad;
	
	rson.s2 += (rson.r - rson.l + 1) * ad * ad + 2 * ad * rson.s;
	rson.ad += ad;
	rson.s += (rson.r - rson.l + 1) * ad;
	
	ad = 0;
	return;
}

void update (int num , int L , int R , double k)
{
	const int l = t[num].l , r = t[num].r , mid = (l+r)/2;
	
	if(L <= l && R >= r)
	{
		t[num].s2 += (r - l + 1) * k * k + 2 * k * t[num].s;
		t[num].ad += k;
		t[num].s += (r - l + 1) * k;
		return;
	}
	
	down (num);
	
	if(L <= mid)
		update (num*2 , L , R , k);
	if(R >= mid+1)
		update (num*2+1 , L , R , k);
	unionn (num);
}

double sum (int num , int L, int R , int c)
{
	const int l = t[num].l , r = t[num].r , mid = (l+r)/2;
	
	if(L <= l && R >= r)
	{
		if(c == 1)
			return t[num].s;
		else return t[num].s2;
	}
	
	double ans = 0;
	if(L <= mid)
		ans += sum (num*2 , L , R , c);
	if(R >= mid+1)
		ans += sum (num*2+1 , L , R , c);
	return ans;
}

void build (int num , int L , int R)
{
	Tree &p = t[num];
	p.l = L , p.r = R , p.ad = 0 , p.s = 0 ,  p.s2 = 0;
	if(L == R)
	{
		p.s = a[L];
		p.s2 = a[L] * a[L];
		return;
	}
	
	build (num*2 , L , (L+R)/2);
	build (num*2+1 , (L+R)/2+1 , R);
	
	unionn (num);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= n ; i ++)
		scanf("%lf",&a[i]);
	build (1 , 1 , n);
	
	while (m --)
	{
		int op , x , y;
		double k , s , s_;
		scanf("%d%d%d",&op,&x,&y);
		
		if(op == 1)
		{
			scanf("%lf",&k);
			update (1 , x , y , k);
			continue;
		}
		
		s = sum (1 , x , y , 1) * 1.0;
		s_ = s / double(y - x + 1);
		
		if(op == 2)
			printf("%.4f\n",s_);
		else {
			printf("%.4f\n",(sum(1 , x , y , 2) * 1.0 / double(y - x + 1)) - s_ * s_);
		}
	}
	
	return 0;
}

自己感觉写得没问题,也检查了,对着题解看没看出来哪里错了,谢谢大佬!!!

2024/7/6 17:27
加载中...