40分求条
  • 板块P1471 方差
  • 楼主wenghaoyu
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/9 12:52
  • 上次更新2024/12/9 19:33:40
查看原帖
40分求条
679655
wenghaoyu楼主2024/12/9 12:52
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct node{
	double n,nl,l;
}t[5000005];
long double li[5000005],k1;
void build(int n,int l,int r){
	if(l==r){
		t[n].n=li[l];
		t[n].nl=li[l]*li[l];
	//	t[n].l=0;
		return ;
	}
	int mid=(l+r)/2;
	build(n*2,l,mid);
	build(n*2+1,mid+1,r);
	t[n].n=t[n*2].n+t[n*2+1].n;
	t[n].nl=t[n*2].nl+t[n*2+1].nl;
} 
void pushdown(int n,int l,int r){
	if(!t[n].l) return;
	int mid=(l+r)/2;
	t[n*2].nl+=2.0*t[n*2].n*t[n].l+t[n].l*t[n].l*(mid-l+1);
	t[n*2+1].nl+=2.0*t[n*2].n*t[n].l+t[n].l*t[n].l*(r-mid);
	t[n*2].n+=(mid-l+1)*t[n].l;
	t[n*2+1].n+=(r-mid)*t[n].l;
	t[n*2].l+=t[n].l;
	t[n*2+1].l+=t[n].l;
	t[n].l=0;
	}
int ll,rr;
void gb(int n,int l,int r){
	if(l>=ll&&r<=rr){
		//t[n].n+=(r-l+1)*k1;
		t[n].l+=k1;
		t[n].nl+=2.0*t[n].n*k1+k1*k1*(r-l+1);
		t[n].n+=(r-l+1)*k1;
	//	pushdown(n,l,r);
		return;
	}
//	cout<<n<<' '<<l<<' '<<r;
	int mid=(l+r)/2;
	pushdown(n,l,r);
	if(mid>=ll) gb(n*2,l,mid);
	if(mid<rr) gb(n*2+1,mid+1,r);
	t[n].n=t[n*2].n+t[n*2+1].n;
	t[n].nl=t[n*2].nl+t[n*2+1].nl;
}
double cx(int n,int l,int r){
//	cout<<n<<endl;
	if(l>=ll&&r<=rr){
	//	cout<<n<<endl;
		return t[n].n;
	}
	int mid=(l+r)/2;double rt=0;
	pushdown(n,l,r);
	if(mid>=ll) rt+=cx(n*2,l,mid);
	if(mid<rr) rt+=cx(n*2+1,mid+1,r);
	return rt;
}
double cx2(int n,int l,int r){
//	cout<<n<<endl;
	if(l>=ll&&r<=rr){
	//	cout<<n<<endl;
		return t[n].nl;
	}
	int mid=(l+r)/2;double rt=0;
	pushdown(n,l,r);
	if(mid>=ll) rt+=cx2(n*2,l,mid);
	if(mid<rr) rt+=cx2(n*2+1,mid+1,r);
	return rt;
}
signed main(){
	for(int i=0;i<5000005;i++) t[i].n=0;
//	freopen("P1253_7.in","r",stdin);
//	freopen("myout.out","w",stdout);
//	int a=0^1;
//	cout<<a<<endl;
	//cout<<a<<endl;
	int k,T;
	cin>>k>>T;
	for(int i=1;i<=k;i++) cin>>li[i];
	build(1,1,k);
	while(T--){
	//cout<<222<<endl; 
		int a;
		scanf("%lld",&a);
		if(a==1){
			cin>>ll>>rr>>k1;
			gb(1,1,k);
		}
		else if(a==2){
			cin>>ll>>rr;
			printf("%.4lf\n",cx(1,1,k)/(rr-ll+1));
		}else{
			cin>>ll>>rr;
			double k1=cx(1,1,k),k2=cx2(1,1,k),k3=k1/(rr-ll+1);
			printf("%.4lf\n",k2*1.0/(rr-ll+1)-1.0*k3*k3);
		}
	//	cout<<1<<endl;
	}
}

应该是求平方和的错误

2024/12/9 12:52
加载中...