70分求调!玄关!
  • 板块P1471 方差
  • 楼主Marky_shine
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/28 21:29
  • 上次更新2024/8/29 08:53:13
查看原帖
70分求调!玄关!
996732
Marky_shine楼主2024/8/28 21:29
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6;
int lson(int x){
	return x << 1;
}
int rson(int x){
	return x << 1 | 1;
}
int n,m;
double taga[N + 5],tagb[N + 5],mark[N + 5];
void push_up(int k){
	taga[k] = taga[lson(k)] + taga[rson(k)];
	tagb[k] = tagb[lson(k)] + tagb[rson(k)];
}
void push_down (int k,int x){
	if (mark[k]){
		tagb[lson(k)] += 2 * mark[k] * taga[lson(k)] + (x - x / 2) * mark[k] * mark[k];
		tagb[rson(k)] += 2 * mark[k] * taga[rson(k)] + (x - x / 2) * mark[k] * mark[k];
		taga[lson(k)] += (x - x / 2) * mark[k];
		taga[rson(k)] += (x / 2) * mark[k];
		mark[lson(k)] += mark[k];
		mark[rson(k)] += mark[k];
		mark[k] = 0;
	}
}
void build (int k,int lft,int rgt){
	if (lft == rgt){
		cin >> taga[k];
		tagb[k] = taga[k] * taga[k];
	}
	else{
		int mid = lft + rgt >> 1;
		build (lson(k),lft,mid);
		build (rson(k),mid + 1,rgt);
		push_up (k);
	}
}
double query_mean (int k,int lft,int rgt,int Lft,int Rgt){
	if (Lft <= lft && rgt <= Rgt) return taga[k];
	else{
		push_down (k,rgt - lft + 1);
		int mid = lft + rgt >> 1; 
		double res = 0;
		if (Lft <= mid) res += query_mean(lson(k),lft,mid,Lft,Rgt);
		if (Rgt > mid) res += query_mean(rson(k),mid + 1,rgt,Lft,Rgt);
		return res; 
	}
}
double query_variance (int k,int lft,int rgt,int Lft,int Rgt){
	if (Lft <= lft && rgt <= Rgt) return tagb[k];
	else{
		push_down (k,rgt - lft + 1);
		int mid = lft + rgt >> 1; 
		double res = 0;
		if (Lft <= mid) res += query_variance(lson(k),lft,mid,Lft,Rgt);
		if (Rgt > mid) res += query_variance(rson(k),mid + 1,rgt,Lft,Rgt);
		return res; 
	}
}
void update (int k,int lft,int rgt,int Lft,int Rgt,double x){
	if (Lft <= lft && rgt <= Rgt){
		mark[k] += x;
		tagb[k] += 2 * x * taga[k] + x * x * (rgt - lft + 1);
		taga[k] +=  (rgt - lft + 1) * x;
	} 
	else{
		push_down (k,rgt - lft + 1);
		int mid = lft + rgt >> 1;
		if (Lft <= mid) update (lson(k),lft,mid,Lft,Rgt,x);
		if (Rgt > mid) update (rson(k),mid + 1,rgt,Lft,Rgt,x);
		push_up (k);
	}
} 
signed main(){
	cin >> n >> m;
	build (1,1,n);
	while (m --){
		int op;
		cin >> op;
		if (op == 1){
			int x,y;
			double z;
			cin >> x >> y >> z;
			update (1,1,n,x,y,z);
		}
		if (op == 2){
			int x,y;
			cin >> x >> y;
			printf ("%.4lf\n",query_mean(1,1,n,x,y) / (y - x + 1));
		}
		if (op == 3){
			int x,y;
			cin >> x >> y;
			double sum1 = query_variance(1,1,n,x,y) / (y - x + 1);
			double sum2 = query_mean(1,1,n,x,y) / (y - x + 1);
			double ans = sum1 - sum2 * sum2;
			printf ("%.4lf\n",ans); 
		}
	}
	return 0;
}
2024/8/28 21:29
加载中...