线段树样例全过,0pts求调
查看原帖
线段树样例全过,0pts求调
928955
_smart_stupid_楼主2024/7/30 16:57
#include <bits/stdc++.h>
using namespace std;
int n, m;
long double a[100100];
struct node{
	int l, r;
	long double sum, sqr_sum, tag;
};
node t[800100];
void pushtag(int p) {
	int len = t[p].r - t[p].l + 1;
	t[p].sqr_sum += t[p].tag * t[p].tag * len + 2 * t[p].sum * t[p].tag;
	t[p].sum += t[p].tag * len;
	t[p * 2].tag += t[p].tag;
	t[p * 2 + 1].tag += t[p].tag;
	t[p].tag = 0;
}
void maketree(int l, int r, int p) {
	t[p].l = l, t[p].r = r;
	if (l < r) {
		maketree(l, (l + r) / 2, p * 2);
		maketree((l + r) / 2 + 1, r, p * 2 + 1);
		t[p].sum = t[p * 2].sum + t[p * 2 + 1].sum;
		t[p].sqr_sum = t[p * 2].sqr_sum + t[p * 2 + 1].sqr_sum;
	}
	else {
		t[p].sum = a[l], t[p].sqr_sum = a[l] * a[l];
	}
}
void add(int l, int r, int p, int k) {
	if (t[p].tag) pushtag(p);
	if (l <= t[p].l && t[p].r <= r) {
		t[p].tag += k;
		pushtag(p);
		return;
	}
	if (l > t[p].r || r < t[p].l) return;
	add(l, r, p * 2, k);
	add(l, r, p * 2 + 1, k);
	if (t[p].l < t[p].r) t[p].sum = t[p * 2].sum + t[p * 2 + 1].sum, t[p].sqr_sum = t[p * 2].sqr_sum + t[p * 2 + 1].sqr_sum;
}
long double get(int l, int r, int p) {
	if (t[p].tag) pushtag(p);
	if (l <= t[p].l && t[p].r <= r) return t[p].sum;
	if (l > t[p].r || r < t[p].l) return 0;
	return get(l, r, p * 2) + get(l, r, p * 2 + 1);
}
long double get_sqr(int l, int r, int p) {
	if (t[p].tag) pushtag(p);
	if (l <= t[p].l && t[p].r <= r) return t[p].sqr_sum;
	if (l > t[p].r || r < t[p].l) return 0;
	return get_sqr(l, r, p * 2) + get_sqr(l, r, p * 2 + 1);
}
long double get_avr(int l, int r) {
	return (long double)get(l, r, 1) / (r - l + 1);
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	maketree(1, n, 1);
	while (m--) {
		int op, x, y;
		cin >> op >> x >> y;
		if (op == 1) {
			long double k;
			cin >> k;
			add(x, y, 1, k);
		}
		else if (op == 2) {
			printf("%.4LF\n", get_avr(x, y));
		}
		else {
			printf("%.4LF\n", (long double)(get_sqr(x, y, 1)) / (y - x + 1) - get_avr(x, y) * get_avr(x, y));
		}
//		for (int i = 1; i <= n; i++) {
//			cout << get_sqr(1, i, 1) << ' ';
//		}
//		cout << '\n';
	}
	return 0;
}
2024/7/30 16:57
加载中...