蒟蒻求助!有好心人帮忙吗?T_T
  • 板块P1471 方差
  • 楼主HYLW
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/27 21:57
  • 上次更新2024/3/28 11:32:16
查看原帖
蒟蒻求助!有好心人帮忙吗?T_T
663949
HYLW楼主2024/3/27 21:57
#include<bits/stdc++.h>
using namespace std;

#define l(x) tr[x].l
#define r(x) tr[x].r
#define sum1(x) tr[x].sum1
#define sum2(x) tr[x].sum2
#define add(x) tr[x].add
	
#define ls(x) x<<1
#define rs(x) x<<1|1

const int N = 1e5;
struct node{
	int l,r;
	double sum1;
	double sum2;
	double add;
}tr[N*4];
int n,m;
double a[N];
double g=1.0000000;

void couten();

void build(int u,int l,int r);
void pushup(int u);
void modify(int u,int l,int r,double v);
node query(int u,int l,int r,int e);
void pushdown(int u);


void pushdown(int u){
	double v=add(u);
	int lu=ls(u),ru=rs(u);
	
	sum2(lu)+=2*v*sum1(lu)+v*v*(r(ls(u))-l(ls(u))+1);
	sum1(lu)+=v*(r(ls(u))-l(ls(u))+1);
	add(lu)+=v;
	
	sum2(ru)+=2*v*sum1(ru)+v*v*(r(rs(u))-l(rs(u))+1);
	sum1(ru)+=v*(r(rs(u))-l(rs(u))+1);
	add(ru)+=v;
	
	add(u)=0;
}

void pushup(int u){
	int len_l=(r(ls(u))-l(ls(u))+1);
	int len_r=(r(rs(u))-l(rs(u))+1);
	
	sum1(u)=g*(sum1(ls(u))+sum1(rs(u)));
	sum2(u)=g*(sum2(ls(u))+sum2(rs(u)));
}

void modify(int u,int l,int r,double v){
	if(l<=l(u) && r(u)<=r){
		sum2(u)+=2*v*sum1(u)+v*v*(r(u)-l(u)+1);
		sum1(u)+=v*(r(u)-l(u)+1);
		add(u)+=v;;
		return ;
	}else{
		pushdown(u);
		int mid=(r(u)+l(u))>>1;
		if(l<=mid)	modify(ls(u),l,r,v);
		if(mid<r)	modify(rs(u),l,r,v);
		pushup(u);
	}
}

node query(int u,int l,int r){
	if(l<=l(u) && r(u)<=r){
		return tr[u];
	}else{
		pushdown(u);
		int mid=(l(u)+r(u))>>1;
		node a,b,re;
		if(l<=mid)	a=query(u<<1,l,r);
		if(mid<r)	b=query(u<<1|1,l,r);
		re.l=l,re.r=r;
		re.sum1=a.sum1+b.sum1;
		re.sum2=a.sum2+b.sum2;
		return re;
	}
}

void build(int u,int l,int r){
	l(u)=l,r(u)=r;
	sum1(u)=0,sum2(u)=0;
	if(l==r){
		sum1(u)=a[l];
		sum2(u)=a[l]*a[l];
		return ;
	}
	int mid=(l(u)+r(u))>>1;
	build(u<<1,l,mid),build(u<<1|1,mid+1,r);
	pushup(u);
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lf",&a[i]);
	build(1,1,n);
	//couten(); 
	while(m--){
		int e,x,y;
		scanf("%d%d%d",&e,&x,&y);
		if(e==1){
			double k;
			scanf("%lf",&k);
			modify(1,x,y,k);
		}else if(e==2){
			node ans=query(1,x,y);
			int len=ans.r-ans.l+1;
			printf("%.4lf\n",ans.sum1/len*g);
		}else{
			node ans=query(1,x,y);
			int len=ans.r-ans.l+1;
			printf("%.4lf\n",ans.sum2/len*g-ans.sum1/len*ans.sum1/len*g);
		}
		//couten();
	}
	return 0;
}

void couten(){
	printf("--------\n");
	for(int i=1,v=1;i<=2*n;i+=v,v*=2){
		for(int j=i;j<i+v;j++){
			printf("%d:[%d,%d] ",j,l(j),r(j));
		}
		puts("");
	}
	printf("========\n");
}
/*
5 4
1 2 3 4 5
1 1 3 1
1 3 5 -1
2 1 5
3 1 5
*/ 

一个hack

8 11
8.46 6.03 3.73 0.32 7.43 3.71 8.04 8.22 
3 1 8
1 2 8 -2.7566713364794850E+0000
1 2 8  2.1308819339610636E+0000
1 1 6  1.5912831262685359E+0000
1 1 8 -2.7779214559122920E+0000
1 1 8 -6.5134523715823889E-0001
3 2 8
1 1 6 -8.5440817382186651E-0001
3 2 8
2 2 8
3 2 7

答案

7.4145
5.2609
6.2101
1.8256
6.1810
2024/3/27 21:57
加载中...