40分蒟蒻求助
  • 板块P1471 方差
  • 楼主Ruins
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/12/19 22:08
  • 上次更新2023/10/28 14:02:10
查看原帖
40分蒟蒻求助
169611
Ruins楼主2021/12/19 22:08
#include <bits/stdc++.h>
#define mid (l+r>>1)
#define ls k<<1
#define rs k<<1|1 
using namespace std;
int n,m;
double sum[480000],tag[480000],sum2[480000];
void pushup(int k){
	sum[k]=sum[ls]+sum[rs];
	sum2[k]=sum2[ls]+sum2[rs];
	return ;
}
void pushdown(int k,int l,int r){
	if(!tag[k])return ;
	sum2[ls]+=(double)(mid-l+1)*tag[k]*tag[k]+2*tag[k]*sum[ls];
	sum2[rs]+=(double)(r-mid)*tag[k]*tag[k]+2*tag[k]*sum[rs];
	sum[ls]+=(double)(mid-l+1)*tag[k];
	sum[rs]+=(double)(r-mid)*tag[k];
	tag[ls]+=tag[k];
	tag[rs]+=tag[k];
	tag[k]=0;
	return ;
}
void build(int k,int l,int r){
	if(l==r){
		cin>>sum[k];
		sum2[k]=sum[k]*sum[k];
		return ;
	}
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(k);
}
void update(int k,int l,int r,int x,int y,double v){
	if(l>y||r<x)return;
	if(l>=x&&r<=y){
		
		sum2[k]+=(double)(r-l+1)*v*v+2*v*sum[k];
		sum[k]+=(double)(r-l+1)*v;
		tag[k]+=v;
		return ;
	}
	pushdown(k,l,r);
	update(ls,l,mid,x,y,v);
	update(rs,mid+1,r,x,y,v);
	pushup(k);
}
double query(int k,int l,int r,int x,int y){
	if(l>y||r<x)return 0;
	if(l>=x&&r<=y){
		return sum[k];
	}
	pushdown(k,l,r);
	return (double)query(ls,l,mid,x,y)+(double)query(rs,mid+1,r,x,y);
}
double query2(int k,int l,int r,int x,int y){
	if(l>y||r<x)return 0;
	if(l>=x&&r<=y){
		return sum2[k];
	}
	pushdown(k,l,r);
	return (double)query(ls,l,mid,x,y)+(double)query(rs,mid+1,r,x,y);
}
signed main(){
	cin>>n>>m;
	build(1,1,n);
	while(m--){
		int op,x,y;
		double z;
		cin>>op;
		if(op==1){
			cin>>x>>y>>z;
			update(1,1,n,x,y,z);
		}
		else if(op==2){
			cin>>x>>y;
			cout<<fixed<<setprecision(4)<<query(1,1,n,x,y)/(double)(y-x+1)<<endl;
		}
		else if(op==3){
			cin>>x>>y;
			int t=query(1,1,n,x,y)/(double)(y-x+1);
			cout<<fixed<<setprecision(4)<<t-t*t*2+query2(1,1,n,x,y)/(double)n<<endl;
		}
	}
	return 0;
}

感觉没啥问题了啊

2021/12/19 22:08
加载中...