样例未过求调
  • 板块P1471 方差
  • 楼主Cute_Furina
  • 当前回复3
  • 已保存回复3
  • 发布时间2025/8/2 12:47
  • 上次更新2025/8/2 19:36:17
查看原帖
样例未过求调
1181602
Cute_Furina楼主2025/8/2 12:47
#include<bits/stdc++.h>
using namespace std;
struct node {
	double lzy, sum1, sum2; 
}w[500005];
double a[10005];
int n, m;
bool InRange(int l, int r, int L, int R) {
	return (l >= L) && (r <= R);
}
bool OutofRange(int l, int r, int L, int R) {
	return (l > R) || (r < L);
}
void pushup(int u) {
	w[u].sum1 = w[u * 2].sum1 + w[u * 2 + 1].sum1;
	w[u].sum2 = w[u * 2 + 1].sum2 + w[u * 2].sum2;
}
void maketag(int u, int len, double x) {
	w[u].lzy += x;
	w[u].sum2 += w[u].sum1 * (x * 2) + len * x * x;
	w[u].sum1 += len * x;
}
void pushdown(int u, int l, int r) {
	if(w[u].lzy == 0) return ;
	int mid = l + r >> 1;
	maketag(u * 2, mid - l + 1, w[u].lzy);
	maketag(u * 2 + 1, r - mid, w[u].lzy);
	w[u].lzy = 0;
} 
void update(int u, int l, int r, int L, int R, double x) {
	if(InRange(l, r, L, R)) {
		maketag(u, r - l + 1, x);
		return ;
	}
	if(OutofRange(l, r, L, R)) {
		return ;
	}
	int mid = l + r >> 1;
	pushdown(u, l, r);
	update(u * 2, l, mid, L, R, x);
	update(u * 2 + 1, mid + 1, r, L, R, x);
	pushup(u);
}
double query(int u, int l, int r, int L, int R) {
	if(InRange(l, r, L, R)) {
		return w[u].sum1;
	}
	if(OutofRange(l, r, L, R)) return 0;
	pushdown(u, l, r);
	int mid = l + r >> 1;
	return query(u * 2, l, mid, L, R) + query(u * 2 + 1, mid + 1, r, L, R);
}
double query2(int u, int l, int r, int L, int R) {
	if(InRange(l, r, L, R)) {
		return w[u].sum2;
	}
	if(OutofRange(l, r, L, R)) return 0;
	pushdown(u, l, r);
	int mid = l + r >> 1;
	return query(u * 2, l, mid, L, R) + query(u * 2 + 1, mid + 1, r, L, R);
}
void build(int u, int l, int r) {
	if(l == r) {
		w[u].sum1 = a[l];
		w[u].sum2 = a[l] * a[l];
		return ;
	}
	int mid = l + r >> 1;
	build(u * 2, l, mid);
	build(u * 2 + 1, mid + 1, r);
	pushup(u);
}
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;
		cin >> op >> x >> y;
		if(op == 1) {
			double k;
			cin >> k;
			update(1, 1, n, x, y, k); 
		} 
		if(op == 2) {
			printf("%.4lf\n", query(1, 1, n, x, y) / (y - x + 1)); 
		}
		else {
			printf("%.4lf\n", query2(1, 1, n, x, y) / (y - x + 1) - query(1, 1, n, x, y) / (y - x + 1)) * (query(1, 1, n, x, y) / (y - x + 1)); 
		}
	} 
} 

2025/8/2 12:47
加载中...