线段树求方差MLE
  • 板块P1471 方差
  • 楼主cmaths
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/8/1 15:11
  • 上次更新2023/10/27 17:30:38
查看原帖
线段树求方差MLE
300098
cmaths楼主2022/8/1 15:11
#include <cstdio>

int n, m;
double ar[100005], sum1[400005], sum2[400005], lazy[400005];
void pushup(int x)
{
	sum1[x] = sum1[x * 2] + sum1[x * 2 + 1];
	sum2[x] = sum2[x * 2] + sum2[x * 2 + 1];
}
double ask1(int x, int l, int r, int s, int t);
double ask2(int x, int l, int r, int s, int t);
void pushdown(int x, int l, int r)
{
	if(l == r)
	{
		return;
	}
	int lx = x * 2, rx = x * 2 + 1, mid = (l + r) / 2;
	if(lazy[x] != 0)
	{
		sum2[lx] += (ask1(1, 1, n, l, mid) * 2.0 + (mid - l + 1) * lazy[x]) * lazy[x];
		sum2[rx] += (ask1(1, 1, n, mid + 1, r) * 2.0 + (r - mid) * lazy[x]) * lazy[x];		
		sum1[lx] += (mid - l + 1) * lazy[x];
		sum1[rx] += (r - mid) * lazy[x];
		lazy[lx] += lazy[x];
		lazy[rx] += lazy[x];
		lazy[x] = 0;
	}
}
void build(int x, int l, int r)
{
	if(l == r)
	{
		sum1[x] = ar[l];
		sum2[x] = ar[l] * ar[l];
		return;
	}
	int mid = (l + r) / 2;
	build(x * 2, l, mid);
	build(x * 2 + 1, mid + 1, r);
	pushup(x);
}
void add(int x, int l, int r, int s, int t, double k)
{
	if(l >= s && r <= t)
	{
		sum2[x] += (ask1(1, 1, n, l, r) * 2.0 + (r - l + 1) * k) * k;
		sum1[x] += (r - l + 1) * k;
		lazy[x] += k;
		return;
	}
	pushdown(x, l, r);
	int mid = (l + r) / 2;
	if(s <= mid)
	{
		add(x * 2, l, mid, s, t, k);
	}
	if(t > mid)
	{
		add(x * 2 + 1, mid + 1, r, s, t, k);
	}
	pushup(x);
}
int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++)
	{
		scanf("%lf", &ar[i]);
	}
	build(1, 1, n);
	for(int i = 1; i <= m; i++)
	{
		int op, x, y;
		scanf("%d %d %d", &op, &x, &y);
		if(op == 1)
		{
			double k;
			scanf("%lf", &k);
			add(1, 1, n, x, y, k);
		}
		else if(op == 2)
		{
			printf("%f\n", ask1(1, 1, n, x, y) / (y - x + 1));
		}
		else
		{
			double tem = ask1(1, 1, n, x, y);
			printf("%f\n", (ask2(1, 1, n, x, y) - tem * tem / (y - x + 1)) / (y - x + 1));
		}
	}
	return 0;
}
double ask1(int x, int l, int r, int s, int t)
{
	if(l >= s && r <= t)
	{
		return sum1[x];
	}
	pushdown(x, l, r);
	int mid = (l + r) / 2;
	double ret = 0;
	if(s <= mid)
	{
		ret += ask1(x * 2, l, mid, s, t);
	}
	if(t > mid)
	{
		ret += ask1(x * 2 + 1, mid + 1, r, s, t);
	}
	return ret;
}
double ask2(int x, int l, int r, int s, int t)
{
	if(l >= s && r <= t)
	{
		return sum2[x];
	}
	pushdown(x, l, r);
	int mid = (l + r) / 2;
	double ret = 0;
	if(s <= mid)
	{
		ret += ask2(x * 2, l, mid, s, t);
	}
	if(t > mid)
	{
		ret += ask2(x * 2 + 1, mid + 1, r, s, t);
	}
	return ret;
}

求调 感激不尽 orz

2022/8/1 15:11
加载中...