0分求调
  • 板块P1471 方差
  • 楼主sillation
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/7/5 10:15
  • 上次更新2024/7/5 12:36:26
查看原帖
0分求调
1045165
sillation楼主2024/7/5 10:15
#include<bits/stdc++.h>
using namespace std;
struct node{
	int l,r;
	double sum,pf,tag;
}t[5000100];
int m,n;
int a[1000100];
void build(int id,int l,int r){
	t[id].l =l,t[id].r =r;
	if(l==r){
		t[id].sum =a[l];
		t[id].pf =a[l]*a[l];
		return ;
	}
	build(id<<1,l,(l+r)/2);
	build(id<<1|1,(l+r)/2+1,r);
	t[id].sum =t[id<<1].sum +t[id<<1|1].sum;
	t[id].pf=t[id<<1].pf +t[id<<1|1].pf;
}
void down(int id){
	if(t[id].tag ==0)return ;
	t[id*2].tag +=t[id].tag;
	t[id*2].pf +=2*t[id].tag *t[id*2].sum +t[id].tag*t[id].tag*(t[id*2].r-t[id*2].l+1);
	t[id*2].sum +=(t[id*2].r-t[id*2].l+1)*t[id].tag;
	t[id*2+1].tag +=t[id].tag;
	t[id*2+1].pf +=2*t[id].tag*t[id*2+1].sum +t[id].tag*t[id].tag*(t[id*2+1].r-t[id*2+1].l+1);
	t[id*2+1].sum +=(t[id*2+1].r-t[id*2+1].l+1)*t[id].tag;
	t[id].tag =0;
}
void up(int id,int l,int r,int v){
	if(t[id].l >r||t[id].r <l) return ;
	if(t[id].l>=l&&t[id].r <=r){
		t[id].tag +=v;
		t[id].pf +=2*v*t[id].sum +v*v*(t[id].r-t[id].l+1);
		t[id].sum +=(t[id].r-t[id].l+1)*v;
		return ;
	}
	down(id);
	up(id<<1,l,r,v);
	up(id<<1|1,l,r,v);
	t[id].sum =t[id<<1].sum +t[id<<1|1].sum;
	t[id].pf=t[id<<1].pf +t[id<<1|1].pf;
}
double ask(int id,int l,int r){
	if(t[id].l>r||t[id].r<l) return 0;
	if(t[id].l>=l&&t[id].r<=r){
		return t[id].sum ;
	}
	down(id);
	return ask(id<<1,l,r)+ask(id<<1|1,l,r);
}
double ask1(int id,int l,int r){
	if(t[id].l>r||t[id].r<l) return 0;
	if(t[id].l>=l&&t[id].r<=r){
		return t[id].pf  ;
	}
	down(id);
	return ask1(id<<1,l,r)+ask1(id<<1|1,l,r);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int op,x,y,k;
		cin>>op>>x>>y;
		if(op==1){
			cin>>k;
			up(1,x,y,k);
		}
		else if(op==2){
			cout << fixed << setprecision(4) << ask(1, x, y) / (y-x+1) << "\n";
		}
		else{
			double p=ask(1, x, y) / (y-x+1);
			cout << fixed << setprecision(4) << -p*p+ask1(1, x, y) / (y-x+1)<< "\n";
		}
	}
	return 0;
}

2024/7/5 10:15
加载中...