过样例但0分求调!!!
  • 板块P1471 方差
  • 楼主我是歌者
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/11/27 11:58
  • 上次更新2024/11/27 15:54:44
查看原帖
过样例但0分求调!!!
566190
我是歌者楼主2024/11/27 11:58
#include<bits/stdc++.h>
using namespace std;
long long int n,m;
struct node{
	long long int l,r;
	double w,add;
}tree[5001000],tree2[5000100];
double arr[1000010];
void build(long long int l,long long int r,long long int idx){
	tree[idx].l=l;tree[idx].r=r;
	tree2[idx].l=l;tree2[idx].r=r;
	if(l==r){
		tree[idx].w=arr[l];
		tree2[idx].w=arr[l]*arr[l];
		return;
	}
	build(l,(l+r)/2,idx*2);build((l+r)/2+1,r,idx*2+1);
	tree[idx].w=tree[idx*2].w+tree[idx*2+1].w;
	tree2[idx].w=tree2[idx*2].w+tree2[idx*2+1].w;
	return;
}
void spread(long long int idx){
	if(tree[idx].add!=0||tree2[idx].add!=0){
		tree2[idx*2+1].w+=2*tree2[idx].add*tree[idx*2+1].w+((double)(tree2[idx*2+1].r-tree[idx*2+1].l+1))*tree2[idx].add*tree2[idx].add;
		tree2[idx*2].w+=2*tree2[idx].add*tree[idx*2].w+((double)(tree2[idx*2].r-tree[idx*2].l+1))*tree2[idx].add*tree2[idx].add;
		tree2[idx*2].add+=tree2[idx].add;tree2[idx*2+1].add+=tree2[idx].add;
		tree[idx*2].w+=tree[idx].add*(tree[idx*2].r-tree[idx*2].l+1);
		tree[idx*2+1].w+=tree[idx].add*(tree[idx*2+1].r-tree[idx*2+1].l+1);
		tree[idx*2].add+=tree[idx].add;
		tree[idx*2+1].add+=tree[idx].add;
		tree[idx].add=0;
	}
	return;
}
void add(long long int l,long long int r,double w,long long int idx){
	if(tree[idx].l>=l&&tree[idx].r<=r){
		tree2[idx].w += tree[idx].w * (w * 2) + (tree2[idx].r - tree2[idx].l + 1) * w * w;
		tree2[idx].add+=w;
		tree[idx].w+=w*(tree[idx].r-tree[idx].l+1);
		tree[idx].add+=w;
		return;
	}
	spread(idx);
	long long int mid=(tree[idx].l+tree[idx].r)/2;
	if(mid<r){
		add(l,r,w,idx*2+1);
	}
	if(mid>=l){
		add(l,r,w,idx*2);
	}
	tree[idx].w=tree[idx*2].w+tree[idx*2+1].w;
	tree2[idx].w=tree2[idx*2].w+tree2[idx*2+1].w;
	return;
}
double check(long long int l,long long int r,long long int idx){
	if(tree[idx].l>=l&&tree[idx].r<=r){
		return tree[idx].w;
	}
	spread(idx);
	if(tree[idx].r<l||tree[idx].l>r) return 0;
	long long int mid=(tree[idx].l+tree[idx].r)/2;
	double ans=0;
	if(l<=mid) ans+=check(l,r,idx*2);
	if(r>mid) ans+=check(l,r,idx*2+1);
	tree[idx].w=tree[idx*2].w+tree[idx*2+1].w;
	tree2[idx].w=tree2[idx*2].w+tree2[idx*2+1].w;
	return ans;
}
double check2(long long int l,long long int r,long long int idx){
	if(tree2[idx].l>=l&&tree2[idx].r<=r){
		return tree2[idx].w;
	}
	spread(idx);
	if(tree2[idx].r<l||tree2[idx].l>r) return 0;
	long long int mid=(tree2[idx].l+tree2[idx].r)/2;
	double ans=0;
	if(l<=mid) ans+=check2(l,r,idx*2);
	if(r>mid) ans+=check2(l,r,idx*2+1);
	tree[idx].w=tree[idx*2].w+tree[idx*2+1].w;
	tree2[idx].w=tree2[idx*2].w+tree2[idx*2+1].w;
	return ans;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	build(1,n,1);
	int a=0;
	while(m--){
		cin>>a;
		if(a==1){
			int x=0,y=0;
			double k=0;
			scanf("%d%d%lf", &x, &y, &k);
			add(x,y,k,1);
		}
		if(a==2){
			long long int x=0,y=0;
			cin>>x>>y;
			 printf("%.4lf\n", check(x,y,1) / ((y - x + 1) * 1.0));
		}
		if(a == 3)
		{
			long long int x, y;
			scanf("%d%d", &x, &y);
			printf("%.4lf\n", (check2(x, y,1) / ((y - x + 1) * 1.0)) - (check(x,y,1) / ((y - x + 1) * 1.0)) * (check(x,y,1) / ((y - x + 1) * 1.0)));
		}
	}
	return 0;
}
2024/11/27 11:58
加载中...