萌新求助关于精度
  • 板块P1471 方差
  • 楼主SIXIANG32
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/7 17:18
  • 上次更新2024/7/7 19:48:02
查看原帖
萌新求助关于精度
298549
SIXIANG32楼主2024/7/7 17:18

如题。这是我的线段树

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
double Abs(double x) {return max(x, -x);}
int n, m;

double a[N + 10];
double sum[N * 4 + 10], squ[N * 4 + 10], add[N * 4 + 10];
int ls(int x) {
	return 2 * x;
}
int rs(int x) {
	return 2 * x + 1;
}
void push_up(int x) {
	sum[x] = sum[ls(x)] + sum[rs(x)];
	squ[x] = squ[ls(x)] + squ[rs(x)];
}
void push_tag(int x, int s, int t, double val) {
	squ[x] = squ[x] + 2.0 * val * sum[x] +
	(double)(t - s + 1) * val * val;
	sum[x] = sum[x] + (double)(t - s + 1) * val;
	add[x] += val;
}
void push_down(int x, int s, int t) {
	if(Abs(add[x]) > 1e-7) {
		int mid = (s + t) >> 1;
		push_tag(ls(x), s, mid, add[x]);
		push_tag(rs(x), mid + 1, t, add[x]);
		add[x] = 0;
	}
}
void update(int ql, int qr, int s, int t, int now, double val) {
	if(ql <= s && t <= qr) {
		push_tag(now, s, t, val);
		return ;
	}
	int mid = (s + t) >> 1;
	push_down(now, s, t);
	if(ql <= mid) update(ql, qr, s, mid, ls(now), val);
	if(qr > mid) update(ql, qr, mid + 1, t, rs(now), val);
	push_up(now);
}
double query1(int ql, int qr, int s, int t, int now) {
	if(ql <= s && t <= qr) return sum[now];
	int mid = (s + t) >> 1;
	double rest = 0;
	push_down(now, s, t);
	if(ql <= mid) rest += query1(ql, qr, s, mid, ls(now));
	if(qr > mid) rest += query1(ql, qr, mid + 1, t, rs(now));
	return rest;
}
double query2(int ql, int qr, int s, int t, int now) {
	if(ql <= s && t <= qr) return squ[now];
	int mid = (s + t) >> 1;
	double rest = 0;
	push_down(now, s, t);
	if(ql <= mid) rest += query2(ql, qr, s, mid, ls(now));
	if(qr > mid) rest += query2(ql, qr, mid + 1, t, rs(now));
	return rest;
}
void build(int l, int r, int x) {
	if(l == r) {
		sum[x] = a[l];
		squ[x] = a[l] * a[l];
		return ;
	}
	int mid = (l + r) >> 1;
	build(l, mid, ls(x));
	build(mid + 1, r, rs(x));
	push_up(x);
}

int main() {
	cin >> n >> m;
	for(int p = 1; p <= n; p++)
		cin >> a[p];

	build(1, n, 1);

	for(int p = 1; p <= m; p++) {
		int opt, l, r;
		cin >> opt >> l >> r;
		if(opt == 1) {
			double val;
			cin >> val;
			update(l, r, 1, n, 1, val);
		}
		else if(opt == 2) {
			double tmp = query1(l, r, 1, n, 1);
			cout << fixed << setprecision(4) << 
			(double)(tmp / (double)(r - l + 1)) << endl;
		}
		else if(opt == 3) {
			double tmp = query1(l, r, 1, n, 1);
			double bax = (double)(tmp / (double)(r - l + 1));
			double pa2 = query2(l, r, 1, n, 1) / (double)(r - l + 1);
			double pa3 = 2 * bax * tmp / (double)(r - l + 1);
			cout << fixed << setprecision(4) << 
			bax * bax + pa2 - pa3 << endl;
		}
	}
}

然后我又写了一份暴力对拍。我自己对拍的时候将 A 开到 1e5 然后精度就寄了,但是我试着交了一发这个线段树是能 AC 的,所以想问下这个怎么样才能让精度掉的少一点。对拍的暴力代码放在下面。

顺便请问这道题题面给了 A 范围嘛?QAQ 我没有看到

2024/7/7 17:18
加载中...