wa 0pts 求助
  • 板块P1471 方差
  • 楼主T_TLucas_Yin
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/8 20:37
  • 上次更新2024/3/8 22:15:24
查看原帖
wa 0pts 求助
835809
T_TLucas_Yin楼主2024/3/8 20:37
#include<bits/stdc++.h>
using namespace std;
int n,m,op,l,r;
double x,a[500005],f1[2000005],f2[2000005],flag[2000005];
void build(int root,int l,int r){
	if(l==r){ f1[root]=a[l],f2[root]=a[l]*a[l];return; }
	int mid=(l+r)>>1;
	build(root<<1,l,mid);
	build(root<<1|1,mid+1,r);
	f1[root]=f1[root<<1]+f1[root<<1|1];
	f2[root]=f2[root<<1]+f2[root<<1|1];
}
void pushdown(int root,int l,int r){
	if(flag[root]==0) return;
	int mid=(l+r)>>1;
	f2[root<<1]+=(flag[root]*flag[root])*(mid-l+1)+2*flag[root]*f1[root<<1],
	f1[root<<1]+=flag[root]*(mid-l+1),flag[root<<1]+=flag[root];
	f2[root<<1|1]+=(flag[root]*flag[root])*(r-(mid+1)+1)+2*flag[root]*f1[root<<1|1];
	f1[root<<1|1]+=flag[root]*(r-(mid+1)+1),flag[root<<1|1]+=flag[root];
	flag[root]=0;
}
void update(int root,int l,int r,int fl,int fr,int k){
	if(fl<=l&&r<=fr){
		f2[root]+=(k*k)*(r-l+1)+2*k*f1[root],
		f1[root]+=k*(r-l+1),flag[root]+=k;
		return;
	}
	int mid=(l+r)>>1;
	pushdown(root,l,r);
	if(fl<=mid) update(root<<1,l,mid,fl,fr,k);
	if(fr>mid) update(root<<1|1,mid+1,r,fl,fr,k);
	f1[root]=f1[root<<1]+f1[root<<1|1];
	f2[root]=f2[root<<1]+f2[root<<1|1];
}
double Find1(int root,int l,int r,int fl,int fr){
	if(fl<=l&&r<=fr) return f1[root];
	int mid=(l+r)>>1;
	double sum=0;
	pushdown(root,l,r);
	if(fl<=mid) sum+=Find1(root<<1,l,mid,fl,fr);
	if(fr>mid) sum+=Find1(root<<1|1,mid+1,r,fl,fr);
	return sum;
}
double Find2(int root,int l,int r,int fl,int fr){
	if(fl<=l&&r<=fr) return f2[root];
	int mid=(l+r)>>1;
	double sum=0;
	pushdown(root,l,r);
	if(fl<=mid) sum+=Find2(root<<1,l,mid,fl,fr);
	if(fr>mid) sum+=Find2(root<<1|1,mid+1,r,fl,fr);
	return sum;
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lf",&a[i]);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&op,&l,&r);
		if(op==1){
			scanf("%lf",&x);
			update(1,1,n,l,r,x);
		}
		else if(op==2){
			double k=Find1(1,1,n,l,r);
			printf("%.4lf\n",k/(r-l+1));
		}
		else if(op==3){
			double k=Find1(1,1,n,l,r)/(r-l+1);
			printf("%.4lf\n",Find2(1,1,n,l,r)/(r-l+1)-(k*k));
		}
	}
	return 0;
}
2024/3/8 20:37
加载中...