40分,求助神仙
  • 板块P1471 方差
  • 楼主JeffZhao
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/7/7 19:52
  • 上次更新2023/11/4 18:27:51
查看原帖
40分,求助神仙
120017
JeffZhao楼主2021/7/7 19:52
#include<iostream>
#include<cstdio>
#include<algorithm>
#define int long long

using namespace std;

const int N = 1e6 + 10;

int n, m;
double a[N], sum[N << 2], mul[N << 2], tag[N << 2];

inline void build(int k, int l, int r) {
	if (l == r) {
		sum[k] = a[l];
		mul[k] = a[l] * a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(k << 1, l, mid);
	build(k << 1 | 1, mid + 1, r);
	sum[k] = sum[k << 1] + sum[k << 1 | 1];
	mul[k] = mul[k << 1] + mul[k << 1 | 1];
	return;
}

inline void Add(int k, int l, int r, double v) {
	tag[k] += v;
	mul[k] += (1.0 * (r - l + 1) * v * v + 2 * v * sum[k]);
	sum[k] += 1.0 * (r - l + 1) * v;
	return;
}

inline void pushdown(int k, int l, int r) {
	if (tag[k] == 0)
		return;
	int mid = (l + r) >> 1;
	Add(k << 1, l, mid, tag[k]);
	Add(k << 1 | 1, mid + 1, r, tag[k]);
	tag[k] = 0;
	return;
}

inline void update(int k, int l, int r, int ql, int qr, double v) {
	if (ql <= l && r <= qr) {
		Add(k, l, r, v);
		return;
	}
	pushdown(k, l, r);
	int mid = (l + r) >> 1;
	if (ql <= mid)update(k << 1, l, mid, ql, qr, v);
	if (qr > mid)update(k << 1 | 1, mid + 1, r, ql, qr, v);
	sum[k] = sum[k << 1] + sum[k << 1 | 1];
	mul[k] = mul[k << 1] + mul[k << 1 | 1];
	return;
}

double Sum(int k, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr)
		return sum[k];
	pushdown(k, l, r);
	int mid = (l + r) >> 1;
	double res = 0;
	if (ql <= mid)res += Sum(k << 1, l, mid, ql, qr);
	if (qr > mid)res += Sum(k << 1 | 1, mid + 1, r, ql, qr);
	return res;
}
double Sin(int k, int l, int r, int ql, int qr) {
	if (ql <= l && r <= qr)
		return mul[k];
	pushdown(k, l, r);
	int mid = (l + r) >> 1;
	double res = 0;
	if (ql <= mid)res += Sin(k << 1, l, mid, ql, qr);
	if (qr > mid)res += Sin(k << 1 | 1, mid + 1, r, ql, qr);
	return res;
}


signed main(void) {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	//n = du(), m = du();

	cin >> n >> m;

	for (int i = 1; i <= n; ++i) {
		//a[i] = du();
		cin >> a[i];
	}

	build(1, 1, n);

	int ins, x, y;
	double k;

	for (int i = 1; i <= m; ++i) {
		cin >> ins;
		if (ins == 1) {
			cin >> x >> y >> k;
			//x = du(), y = du(), k = du();
			update(1, 1, n, x, y, k);
		}
		if (ins == 2) {
			//x = du(), y = du();
			cin >> x >> y;
			printf("%0.4lf\n", Sum(1, 1, n, x, y) * 1.0 / (y - x + 1));
		}
		if (ins == 3) {
			//x = du(), y = du();
			cin >> x >> y;
			int t = Sum(1, 1, n, x, y), tt = Sin(1, 1, n, x, y);
			double ave = Sum(1, 1, n, x, y) * 1.0 / (y - x + 1);
			printf("%0.4lf\n", (1.0 * tt + 1.0 * (y - x + 1) * ave * ave - 2 * 1.0 * ave * t) * 1.0 / n);
		}
	}

	return 0;
}
2021/7/7 19:52
加载中...