样例没过,大佬求调线段树,玄关
  • 板块P1471 方差
  • 楼主JiangMzz
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/8/18 09:47
  • 上次更新2024/8/18 12:32:05
查看原帖
样例没过,大佬求调线段树,玄关
1285611
JiangMzz楼主2024/8/18 09:47
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int n, m;
int a[MAXN];
int A[MAXN * 4];
int s[MAXN * 4];
int s2[MAXN * 4];
float ans1;
float ans2;
void push_up(int p) {
	s[p] = s[p << 1] + s[p << 1 | 1];
	s2[p] = s2[p << 1] + s2[p << 1 | 1];
}
void build(int l, int r, int p) {
	if (l == r) {
		s[p] = a[l];
		s2[p] = a[l] * a[l];
		return;
	}
	int mid = (l + r) / 2;
	build(l, mid , p << 1);
	build(mid + 1, r, p << 1 | 1);
	push_up(p);
}
void add1(int l, int r, int p, int k) {
	s2[p] += 2 * k * s[p] + (r - l + 1) * k * k;
	s[p] += (r - l + 1) * k;
	A[p] += k;
}
void push_down(int l, int r, int p) {
	if (A[p] != 0) {
		int mid = (l + r) / 2;
		add1(l, mid, p << 1, A[p]);
		add1(mid + 1, r, p << 1 | 1, A[p]);
		A[p] = 0;
	}
	return;
}
void add(int l, int r, int L, int R, int p, int k) {
	if (r < L || R > l) return;
	if (L <= l && r <= R) {
		add1(l, r, p, k);
		return;
	} 
	//cout << 1 << endl;
	push_down(l, r, p);
	//cout << 2 << endl;
	int mid = (l + r) / 2;
	add(l, mid, L, R, p << 1, k);
	//cout << 3 << endl;
	add(mid + 1, r, L, R, p << 1 | 1, k);
	//cout << 4 << endl;
	push_up(p);
	//cout << 5 << endl;
	return;
}
int ask(int l, int r, int L, int R, int p) {
	int ans = 0;
	if (L <= l && r <= R) {
		return s[p];
	}
	push_down(l, r, p);
	int mid = (l + r) / 2;
	if (L <= mid) ans += ask(l, mid, L, R, p << 1);
	if (R > mid) ans += ask(mid + 1, r, L, R, p << 1 | 1);
	return ans;
}
int ask2(int l, int r, int L, int R, int p) {
	int ans = 0;
	if (L <= l && r <= R) {
		return s2[p];
	}
	push_down(l, r, p);
	int mid = (l + r) / 2;
	if (L <= mid) ans += ask2(l, mid, L, R, p << 1);
	if (R > mid) ans += ask2(mid + 1, r, L, R, p << 1 | 1);
	return ans;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	build(1, n, 1);
	for (int i = 1; i <= m; i++) {
		int opt, x, y;
		cin >> opt >> x >> y;
		if (opt == 1) {
			int k;
			cin >> k;
			add(1, n, x, y, 1, k);
		}
		else if (opt == 2) {
			ans1 = ask(1, n, x, y, 1) * 1.0 / (y - x + 1) * 1.0;
			printf("%.4lf\n", ans1);
		}
		else {
			ans1 = ask(1, n, x, y, 1) * 1.0 / (y - x + 1) * 1.0;
			ans2 = ask2(1, n, x, y, 1) * 1.0 / (y - x + 1) * 1.0;
			ans1 *= ans1;
			ans2 -= ans1;
			printf("%.4lf\n", ans2);
		}
	}
	return 0;
}
2024/8/18 09:47
加载中...