求大佬找问题
  • 板块学术版
  • 楼主gmx0424
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/2 22:09
  • 上次更新2023/11/2 22:14:39
查看原帖
求大佬找问题
890233
gmx0424楼主2023/11/2 22:09
/*
题目:维护平均数和方差

思路;
	平均数:求和
 	方差:求平方和,(用公示推导)
	 
sum:区间和,∑ai += (r-l+1)*k 
xsum:平方和,∑(ai)^2 -->∑(ai+k)^2-->∑(ai^2+2*k*ai+k^2)
			  --->∑ai^2 + 2*k*∑ai + n*k^2
			  += 2*k*sum+ (r-l+1)*k^2 
方差:根据公示展开 
*/
//gmx 2023.11.2

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, m;
int a[maxn];

struct node{
	int l;
	int r;
	double sum, xsum, addtag;
} v[maxn << 2] ;


void pushup(int rt){
	v[rt].sum  = v[rt<<1].sum + v[rt<<1|1].sum;
	v[rt].xsum = v[rt<<1].xsum + v[rt<<1|1].xsum;
}


void build (int rt, int l, int r){
	if (l == r){
		v[rt].sum = a[l];
		v[rt].xsum = a[l] * a[l];
		return ;
	}
	int mid = (l + r) >> 1;
	build (rt<<1,l,mid);
	build (rt<<1|1,mid+1,r);
	pushup(rt);
}


void pushdown(int rt, int l, int r){
	if(v[rt].addtag) {
		v[rt<<1].addtag += v[rt].addtag;
		v[rt<<1|1].addtag += v[rt].addtag;
		
		int mid = (l+r) >> 1;
		
		v[rt<<1].xsum += 2*v[rt].addtag*v[rt<<1].sum + (double)(mid - l + 1) * v[rt].addtag * v[rt].addtag;
		v[rt<<1|1].xsum += 2*v[rt].addtag*v[rt<<1|1].sum + (double)(r - mid) * v[rt].addtag * v[rt].addtag;
	
		v[rt<<1].sum += (double)(mid - l + 1 )*v[rt].addtag;
		v[rt<<1|1].sum += (double)(r - mid )*v[rt].addtag;
		
		v[rt].addtag = 0;
	}
}


void update(int rt, int l, int r, int ql, int qr, int k){
	if (qr < l || ql > r){
		return ;
	}
	if (ql <= l && r <= qr){
		v[rt].addtag += k;
		v[rt].xsum += 2*v[rt].sum*k+(double)(r-l+1)*k*k;
		v[rt].sum += (r-l+1)*k;
		return ;
	}
	int mid = (l+r)>>1;
	pushdown(rt,l,r);
	update(rt<<1,l,mid,ql,qr,k);
	update(rt<<1|1,mid+1,r,ql,qr,k);
	pushup(rt);
}


double query1(int rt, int l, int r, int ql, int qr){
	if (qr < l || ql > r){
		return 0;
	}
	if (ql <= l && r <= qr){
		return v[rt].sum;
	}
	int mid = (l + r)>>1;
	pushdown(rt,l,r);
	return query1(rt<<1,l,mid,ql,qr) + query1(rt<<1|1,mid+1,r,ql,qr);
}


double query2(int rt, int l, int r, int ql, int qr){
	if (qr < l || ql > r){
		return 0;
	}
	if (ql <= l && r <= qr){
		return v[rt].xsum;
	}
	int mid = (l + r)>>1;
	pushdown(rt,l,r);
	return query2(rt<<1,l,mid,ql,qr) + query2(rt<<1|1,mid+1,r,ql,qr);
}


int main () {
	cin >> n >> m;
	for (int i = 1; i <= n ;i++){
		cin >> a[i];
	}
	
	build (1,1,n);
	
	while (m -- ){
		int op, x, y, k;
		cin >> op;
		if(op == 1)
		{
			cin >> x >> y >> k;
			update(1, 1, n, x, y, k);
		}
		else if (op == 2)
		{
			cin >> x >> y;
			double ans = query1(1,1,n,x,y);
			ans = ans / (y-x+1);
			printf("%.4lf\n",ans);
		}
		else 
		{
			cin >> x >> y;
			double sum = query1(1,1,n,x,y);
			sum /= (y-x+1);//平均数 
			
			double tmp = query2(1,1,n,x,y);//区间平方和 
			
			double ans = (double)(tmp - (double)2*query1(1,1,n,x,y) * sum + (double)(y-x+1)*sum*sum)/(y-x+1);
			
			printf("%.4lf\n",ans);
		}
	}
	return 0;
}

2023/11/2 22:09
加载中...