线段树全WA求助
  • 板块P1471 方差
  • 楼主Kobe303
  • 当前回复21
  • 已保存回复21
  • 发布时间2021/10/1 21:07
  • 上次更新2023/11/4 05:12:50
查看原帖
线段树全WA求助
292300
Kobe303楼主2021/10/1 21:07
#include <bits/stdc++.h>
using namespace std;
#define il inline
const int N = 100005;
int n, m;
double a[N]; 
struct node {
	int l, r;
	double add1, add2, sum1, sum2; //sum1维护和,sum2维护平方和 
	#define add1(p) t[p].add1
	#define add2(p) t[p].add2
	#define sum1(p) t[p].sum1
	#define sum2(p) t[p].sum2
	#define l(p) t[p].l
	#define r(p) t[p].r
} t[N * 4];

void build(int p, int l, int r) {
	l(p) = l, r(p) = r;
	if (l == r) {
		sum1(p) = a[l], sum2(p) = a[l] * a[l];
		return;
	}
	int mid = l + r >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
	sum1(p) = sum1(p << 1) + sum1(p << 1 | 1);
	sum2(p) = sum2(p << 1) + sum2(p << 1 | 1);
}

void spread(int p) {
	if (add1(p)) {
		add2(p << 1) += add2(p);
		sum2(p << 1) += 1.0 * (r(p << 1) - l(p << 1) + 1) * add2(p) * add2(p) + 2.0 * sum1(p) * add2(p);
		add1(p << 1) += add1(p);
		sum1(p << 1) += 1.0 * (r(p << 1) - l(p << 1) + 1) * add1(p);
		add2(p << 1 | 1) += add2(p);
		sum2(p << 1 | 1) += 1.0 * (r(p << 1 | 1) - l(p << 1 | 1) + 1) * add2(p) * add2(p) + 2.0 * sum1(p) * add2(p);
		add1(p << 1 | 1) += add1(p);
		sum1(p << 1 | 1) += 1.0 * (r(p << 1 | 1) - l(p << 1 | 1) + 1) * add1(p);
		add1(p) = add2(p) = 0;
		return;
	}
}

void change(int p, int l, int r, double k) {
	if (l <= l(p) && r(p) <= r) {
		add2(p) += k, sum2(p) += 1.0 * (r(p) - l(p) + 1) * k * k + 2.0 * k * sum1(p);
		add1(p) += k, sum2(p) += 1.0 * (r(p) - l(p) + 1) * k;
		return;
	}
	spread(p);
	int mid = l(p) + r(p) >> 1;
	if (l <= mid) change(p << 1, l, r, k);
	if (r > mid) change(p << 1 | 1, l, r, k);
	sum1(p) = sum1(p << 1) + sum1(p << 1 | 1);
	sum2(p) = sum2(p << 1) + sum2(p << 1 | 1);
	return;
}

double query1(int p, int l, int r) {
	if (l <= l(p) && r(p) <= r) return sum1(p);
	spread(p);
	int mid = l(p) + r(p) >> 1;
	double ans = 0;
	if (l <= mid) ans += query1(p << 1, l, r);
	if (r > mid) ans += query1(p << 1 | 1, l, r);
//	printf("%d %d %.4lf\n", l(p), r(p), ans);
	return ans;
}

double query2(int p, int l, int r) {
	if (l <= l(p) && r(p) <= r) return sum2(p);
	spread(p);
	int mid = l(p) + r(p) >> 1;
	double ans = 0;
	if (l <= mid) ans += query2(p << 1, l, r);
	if (r > mid) ans += query2(p << 1 | 1, l, r);
	return ans;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) scanf("%lf", &a[i]);
//	for (int i = 1; i <= n; ++i) printf("%lf ", a[i]);
//	printf("\n");
	build(1, 1, n);
//	printf("%lf\n", query1(1, 3, 4));
	for (int i = 1; i <= m; ++i) {
		int op; scanf("%d", &op);
		if (op == 1) {
			int x, y; double k; scanf("%d%d%lf", &x, &y, &k);
			change(1, x, y, k);
		}
		else if (op == 2) {
			int x, y; scanf("%d%d", &x, &y);
			printf("%.4lf\n", query1(1, x, y) / (y - x + 1));
		}
		else {
			int x, y; scanf("%d%d", &x, &y);
			double ans1 = query1(1, x, y), ans2 = query2(1, x, y);
			printf("%.4lf\n", ans2 / (y - x + 1) - (ans1 / (y - x + 1)) * (ans1 / (y - x + 1)));
		}
	}
	return 0;
}
2021/10/1 21:07
加载中...