0ptsRE玄关求调
  • 板块P1471 方差
  • 楼主pstdjr
  • 当前回复3
  • 已保存回复3
  • 发布时间2025/8/1 00:06
  • 上次更新2025/8/1 13:57:35
查看原帖
0ptsRE玄关求调
532209
pstdjr楼主2025/8/1 00:06

rt,代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, a[100010];
struct node{
	double sz, sum, k, fc, tg;
	void tag(double d){
		k += sz * d * d + 2 * sum * d;
		sum += sz * d;
		fc = (sz * 1.0 * (sum * 1.0 / sz) * (sum * 1.0 / sz) + k - 2 * sum * 1.0 / sz * sum) * 1.0 / sz;
		tg += d;
	}
} tr[400010];
node operator + (const node &x, const node &y){
	node r;
	r.sz = x.sz + y.sz;
	r.sum = x.sum + y.sum;
	r.k = x.k + y.k;
	r.fc = (r.sz * 1.0 * (r.sum * 1.0 / r.sz) * (r.sum * 1.0 / r.sz) + r.k - 2 * r.sum * 1.0 / r.sz * r.sum) * 1.0 / r.sz;
	return r;
}
void push_down(int p){
	if (tr[p*2].sz)
		tr[p*2].tag(tr[p].tg);
	if (tr[p*2+1].sz)
		tr[p*2+1].tag(tr[p].tg);
	tr[p].tg = 0;
}
void build(int p, int s, int t){
	if (s == t){
		tr[p].sz = 1;
		tr[p].tag(a[s]);
		return;
	}
	int mid=s+t>>1;
	build(p*2, s, mid);
	build(p*2+1, mid+1, t);
	tr[p] = tr[p*2] + tr[p*2+1];
}
void update(int p, int s, int t, int l, int r, double d){
	if (l <= s && t <= r){
		tr[p].tag(d);
		return;
	}
	int mid=s+t>>1;
	push_down(p);
	if (r <= mid)
		update(p*2, s, mid, l, r, d);
	else if (l > mid)
		update(p*2+1, mid+1, t, l, r, d);
	else{
		update(p*2, s, mid, l, r, d);
		update(p*2+1, mid+1, t, l, r, d);
	}
	tr[p] = tr[p*2] + tr[p*2+1];
}
node query(int p, int s, int t, int l, int r){
	if (l <= s && t <= r)
		return tr[p];
	int mid=s+t>>1;
	push_down(p);
	if (r <= mid)
		return query(p*2, s, mid, l, r);
	else if (l > mid)
		return query(p*2+1, mid+1, t, l, r);
	else
		return query(p*2, s, mid, l, r) + query(p*2+1, mid+1, t, l, r);
}
signed main(){
	cin >> n >> m;
	for (int i=1; i<=n; i++)
		cin >> a[i];
	build(1, 1, n);
	while (m--){
		int op, x, y;
		double k;
		cin >> op >> x >> y;
		if (op == 1){
			cin >> k;
			update(1, 1, n, x, y, k);
		}
		else if (op == 2){
			node s=query(1, 1, n, x, y);
			cout << fixed << setprecision(4) << s.sum * 1.0 / s.sz << '\n';
		}
		else
			cout << fixed << setprecision(4) << query(1, 1, n, x, y).fc << '\n';
	}
}
2025/8/1 00:06
加载中...