线段树30pts求调,悬赏关注
  • 板块P1471 方差
  • 楼主halehu
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/7/26 20:10
  • 上次更新2023/11/3 07:30:13
查看原帖
线段树30pts求调,悬赏关注
365777
halehu楼主2023/7/26 20:10

查了一个小时了,各位大佬能否看看(球球了)

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
int n,m;
double a[N],tag[N],sum1[N],sum2[N];
void build(int l,int r,int p){
	if(l == r){
		sum1[p] = a[l];
		sum2[p] = a[l] * a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(l,mid,p*2);
	build(mid+1,r,p*2 + 1);
    sum1[p] = sum1[p*2] + sum1[p*2 + 1];
    sum2[p] = sum2[p*2] + sum2[p*2 + 1];
}
void pushdown(int p,int l,int L,int R){
	if(tag[p] == 0.0) return;
	double len = (double)l;
	tag[p*2] += tag[p];
	tag[p*2 + 1] += tag[p];
	sum2[p*2] += 2 * tag[p] * sum1[p*2] + (len - len / 2) * tag[p] * tag[p];
	sum1[p*2] += (len - len / 2) * tag[p];
	sum2[p*2 + 1] += 2 * tag[p] * sum1[p*2 + 1] + (len / 2) * tag[p] * tag[p];
	sum1[p*2 + 1] += (len / 2) * tag[p];
	tag[p] = 0.0;
}
void update(int x,int y,double v,int l,int r,int p){
	if(x > r || y < l) return;
	if(x <= l && r <= y){
		tag[p] += v;
		sum2[p] += 2 * v * sum1[p] + (double)(r - l + 1) * v * v;
		sum1[p] += (double)(r - l + 1) * v;
		return;
	}
	int mid = (l + r) >> 1;
	pushdown(p,r - l + 1,l,r);
	update(x,y,v,l,mid,p*2);
	update(x,y,v,mid+1,r,p*2 + 1);
	sum2[p] = sum2[p*2] + sum2[p*2 + 1];
	sum1[p] = sum1[p*2] + sum1[p*2 + 1];
}
double query1(int x,int y,int l,int r,int p){
	if(x > r || y < l) return 0.0;
	if(x <= l && r <= y) return sum1[p];
	int mid = (l + r) >> 1;
	pushdown(p,r - l + 1,l,r);
	return query1(x,y,l,mid,p*2) + query1(x,y,mid+1,r,p*2 + 1);
}
double query2(int x,int y,int l,int r,int p){
	if(x > r || y < l) return 0.0;
	if(x <= l && r <= y) return sum2[p];
	int mid = (l + r) >> 1;
	pushdown(p,r - l + 1,l,r);
	return query2(x,y,l,mid,p*2) + query2(x,y,mid+1,r,p*2 + 1);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
	build(1,n,1);
	for(int i=1;i<=m;i++){
		int x,y,op;
		scanf("%d%d%d",&op,&x,&y);
		if(op == 1){
			double k;
			scanf("%lf",&k);
			update(x,y,k,1,n,1);
		}
		else if(op == 2){
			double len = (double)(y - x + 1);
			printf("%.4lf\n",query1(x,y,1,n,1) / len);
		}
		else{
			double len = (double)(y - x + 1);
			double sgm1,sgm2,avr,sqt;
			sgm2 = query2(x,y,1,n,1),sgm1 = query1(x,y,1,n,1);
			avr = sgm1 / len,sqt = sgm2 / len;
			printf("%.4lf\n",sqt - avr * avr);
		}
	}
	return 0;
}
2023/7/26 20:10
加载中...