屎山求条
  • 板块P1471 方差
  • 楼主TFHS_arsc
  • 当前回复9
  • 已保存回复10
  • 发布时间2024/12/1 14:39
  • 上次更新2024/12/1 17:19:57
查看原帖
屎山求条
821849
TFHS_arsc楼主2024/12/1 14:39
#include<iostream>
#define left_son x<<1
#define right_son x<<1|1

using namespace std;

int n,m;
double a[100005],s1[200005],s2[200005];
double lz[200005];

void push_up(int x){
	s1[x]=s1[x<<1]+s1[x<<1|1];
	s2[x]=s2[x<<1]+s2[x<<1|1];
}

void push_down(int l,int r,int x){
	if(lz[x]){
		int midle=(l+r)/2;
		s2[left_son]+=lz[x]*lz[x]*(midle-l+1)+2*s1[left_son]*lz[x];
		s2[right_son]+=lz[x]*lz[x]*(r-midle)+2*s1[right_son]*lz[x];
		s1[left_son]+=lz[x]*(midle-l+1);
		s1[right_son]+=lz[x]*(r-midle);
		lz[left_son]+=lz[x];
		lz[right_son]+=lz[x];
		lz[x]=0;
	}
}

void build(int l,int r,int x){
	if(l==r){
		s1[x]=a[l];
		s2[x]=a[l]*a[l];
		return;
	}
	int midle=(l+r)/2;
	build(l,midle,left_son);
	build(midle+1,r,right_son);
	push_up(x);
}

void update(int L,int R,double k,int l,int r,int x){
	if(L<=l&&R>=r){
		s2[x]+=k*k*(r-l+1)+2*s1[x]*k;
		s1[x]+=k*(r-l+1);
		lz[x]+=k;
		return;
	}
	push_down(l,r,x);
	int midle=(l+r)/2;
	if(L<=midle) update(L,R,k,l,midle,left_son);
	if(R>midle) update(L,R,k,midle+1,r,right_son);
	push_up(x);
}

double query_1(int L,int R,int l,int r,int x){
	if(L<=l&&r<=R){
		return s1[x];
	}
	push_down(l,r,x);
	int midle=(l+r)/2;
	double res=0;
	if(L<=midle) res+=query_1(L,R,l,midle,left_son);
	if(R>midle) res+=query_1(L,R,midle+1,r,right_son);
	return res;
}

double query_2(int L,int R,int l,int r,int x){
	if(L<=l&&r<=R){
		return s2[x];
	}
	push_down(l,r,x);
	int midle=(l+r)/2;
	double res=0;
	if(L<=midle) res+=query_2(L,R,l,midle,left_son);
	if(R>midle) res+=query_2(L,R,midle+1,r,right_son);
	return res;
}

int main(){
	
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	build(1,n,1);
	for(int i=1;i<=m;i++){
		int op,l,r;
		double k;
		cin>>op>>l>>r;
		if(op==1){
			cin>>k;
			update(l,r,k,1,n,1);
		}
		else if(op==2) printf("%.4lf\n",query_1(l,r,1,n,1));
		else{
			double sum=query_1(l,r,1,n,1);
			double avg=sum/(r-l+1);
			double res=query_2(l,r,1,n,1);
			printf("%.4lf\n",(res-2*sum*avg+avg*avg*(r-l+1))/(r-l)+1);
		}
	}
	
	return 0;
}
2024/12/1 14:39
加载中...