0pts求调(玄关)
  • 板块P1471 方差
  • 楼主wantongxue
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/7/16 23:39
  • 上次更新2024/7/17 09:06:08
查看原帖
0pts求调(玄关)
705623
wantongxue楼主2024/7/16 23:39
#include <bits/stdc++.h>
using namespace std;

int n,m;
double a[100010];
int r,x,y;
double k;
struct node{
	int l,r;
	double ans,lazy,fang;
}tr[100010*4];

void build(int l,int r,int now){
	tr[now].l=l;tr[now].r=r;
	if(l==r){
		tr[now].ans=a[l];
		tr[now].fang=tr[now].ans*tr[now].ans*1.0;
		return;
	}
	int mid=l+r>>1;
	build(l,mid,now<<1);
	build(mid+1,r,now<<1|1);
	tr[now].ans=tr[now<<1].ans*1.0+tr[now<<1|1].ans;
	tr[now].fang=tr[now<<1].fang*1.0+tr[now<<1|1].fang;
}

void pushdown(int p){
	if(tr[p].lazy){
		tr[p<<1].fang+=1.0*tr[p].lazy*tr[p].lazy*(tr[p<<1].r-tr[p<<1].l+1)+tr[p<<1].ans*2*k;
		tr[p<<1|1].fang+=1.0*tr[p].lazy*tr[p].lazy*(tr[p<<1|1].r-tr[p<<1|1].l+1)+tr[p<<1|1].ans*2*k;
		tr[p<<1].ans+=1.0*(tr[p<<1].r-tr[p<<1].l+1)*tr[p].lazy;
		tr[p<<1|1].ans+=1.0*(tr[p<<1|1].r-tr[p<<1|1].l+1)*tr[p].lazy;
		tr[p<<1].lazy+=1.0*tr[p].lazy;
		tr[p<<1|1].lazy+=1.0*tr[p].lazy;
		tr[p].lazy=0;
	}
}

void modify(int l,int r,double k,int now){
	if(tr[now].l>=l&&tr[now].r<=r){
		tr[now].lazy+=k*1.0;
		tr[now].fang+=k*k*1.0*(tr[now].r-tr[now].l+1)+tr[now].ans*1.0*2*k;
		tr[now].ans+=(tr[now].r-tr[now].l+1)*k*1.0;
		return;
	}
	pushdown(now);
	int mid=tr[now].l+tr[now].r>>1;
	if(l<=mid) modify(l,r,k,now<<1);
	if(r>mid) modify(l,r,k,now<<1|1);
	tr[now].ans=tr[now<<1].ans+tr[now<<1|1].ans;
	tr[now].fang=tr[now<<1|1].fang+tr[now<<1].fang;
}

double query(int l,int r,int now){
	if(tr[now].l>=l&&tr[now].r<=r) 
	return tr[now].ans;
	int mid=tr[now].l+tr[now].r>>1;
	pushdown(now);
	double ans=0;
	if(l<=mid) ans+=query(l,r,now<<1);
	if(r>mid) ans+=query(l,r,now<<1|1);
	return ans;
}

double query2(int l,int r,int now){
	if(tr[now].l>=l&&tr[now].r<=r) 
	return tr[now].fang;
	int mid=tr[now].l+tr[now].r>>1;
	pushdown(now);
	double ans=0;
	if(l<=mid) ans+=query2(l,r,now<<1);
	if(r>mid) ans+=query2(l,r,now<<1|1);
	return ans;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,n,1);
	while(m--){
		cin>>r;
		if(r==1){
			cin>>x>>y;
			cin>>k;
			modify(x,y,k,1);
		}else if(r==2){
			cin>>x>>y;
			cout<<fixed<<setprecision(4)<<query(x,y,1)*1.0/(y-x+1)<<endl;
		}else{
			cin>>x>>y;
			double u=query2(x,y,1)*1.0/(y-x+1);
			double t=query(x,y,1)*1.0/(y-x+1);
			cout<<fixed<<setprecision(4)<<u-t*t*1.0<<endl;
		}
	}
	return 0;
}

/*
5 3
1 5 4 2 3
1 1 1 1
1 2 2 -1
3 1 5
*/
2024/7/16 23:39
加载中...