感觉思路正确 样例没过 求条
  • 板块P1471 方差
  • 楼主Eater_Tree
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/27 20:15
  • 上次更新2024/12/28 09:17:04
查看原帖
感觉思路正确 样例没过 求条
1110209
Eater_Tree楼主2024/12/27 20:15
#include<bits/stdc++.h>
using namespace std;
int n,m;
double a[101000];
struct node{
	int l,r;
	double dat,pow_dat,add,pow_;
}tree[401000];
void build(int p,int l,int r){
	tree[p].l=l,tree[p].r=r;
	if(l==r){
		tree[p].dat=a[l];
		tree[p].pow_dat=a[l]*a[l];
		return ;
	}
	int mid=(tree[p].l+tree[p].r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tree[p].dat=tree[p*2].dat+tree[p*2+1].dat;
	tree[p].pow_dat=tree[p*2].pow_dat+tree[p*2+1].pow_dat;
}
void down(int p){
	int k=tree[p].pow_;
	tree[p*2].pow_dat+=2*tree[p*2].dat*k+k*(tree[p*2].r-tree[p*2].l+1);
	tree[p*2+1].pow_dat+=2*tree[p*2+1].dat*k+k*(tree[p*2+1].r-tree[p*2+1].l+1);
	tree[p*2].pow_+=k;
	tree[p*2+1].pow_+=k;
	tree[p].pow_=0;
	k=tree[p].add;
	tree[p*2].dat+=k*(tree[p*2].r-tree[p*2].l+1);
	tree[p*2+1].dat+=k*(tree[p*2+1].r-tree[p*2+1].l+1);
	tree[p*2].add+=k;
	tree[p*2+1].add+=k;
	tree[p].add=0;
}
void update(int p,int l,int r,double k){
	if(tree[p].l>=l&&tree[p].r<=r){
		tree[p].pow_dat+=2*tree[p].dat*k+k*(tree[p].r-tree[p].l+1);
		tree[p].dat+=k*(tree[p].r-tree[p].l+1);
		tree[p].pow_+=k;
		tree[p].dat+=k;
		return ;
	}
	down(p);
	int mid=(tree[p].l+tree[p].r)/2;
	if(l<=mid)
		update(p*2,l,r,k);
	if(r>mid)
		update(p*2+1,l,r,k);
	tree[p].dat=tree[p*2].dat+tree[p*2+1].dat;
	tree[p].pow_dat=tree[p*2].pow_dat+tree[p*2+1].pow_dat;
}
double add_ask(int p,int l,int r){
	if(tree[p].l>=l&&tree[p].r<=r)
		return tree[p].dat;
	down(p);
	double ans=0;
	int mid=(tree[p].l+tree[p].r)/2;
	if(l<=mid)
		ans+=add_ask(p*2,l,r);
	if(r>mid)
		ans+=add_ask(p*2+1,l,r);
	return ans;
}
double pow_ask(int p,int l,int r){
	if(tree[p].l>=l&&tree[p].r<=r)
		return tree[p].pow_dat;
	down(p);
	double ans=0;
	int mid=(tree[p].l+tree[p].r)/2;
	if(l<=mid)
		ans+=pow_ask(p*2,l,r);
	if(r>mid)
		ans+=pow_ask(p*2+1,l,r);
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lf",&a[i]);
	build(1,1,n);
	while(m--){
		int op,x,y;
		double k;
		scanf("%d",&op);
		if(op==1){
			scanf("%d%d%lf",&x,&y,&k);
			update(1,x,y,k);
		}
		if(op==2){
			scanf("%d%d",&x,&y);
			double sum=add_ask(1,x,y);
			int len=y-x+1;
			double ans=sum/len;
			printf("%.4lf\n",ans);
		}
		if(op==3){
			scanf("%d%d",&x,&y);
			double sum=add_ask(1,x,y);
			double pow_sum=pow_ask(1,x,y);
			int len=y-x+1;
			double ans=(len*(sum/len)*(sum/len)+pow_sum-2*(sum/len)*sum)/len;
			printf("%.4lf\n",ans);
		}
	}
	return 0;
}
/*
x1 x2 x3 x4 x n
s=(1/n)*[(x1-x)^2+(x2-x)^2+(x3-x)^2+(x4-x)^2]
s=(1/n)*(x1^2-2*x1*x+x^2+x2^2-2*x2*x+x^2+x3^2-2*x3*x+x^2+x4^2-2*x4*x+x^2)
s=(1/n)*(n*x^2+x1^2+x2^2+x3^2+x4^2-2*x*(x1+x2+x3+x4))
x1+x2+x3+x4
x1+d+x2+d+x3+d+x4+d
+=d*(r-l+1)
x1*x1+x2*x2+x3*x3+x4*x4
(x1+d)^2+(x2+d)^2+(x3+d)^2+(x4+d)^2
x1*x1+2*x1*d+d*d+x2*x2+2*x2*d+d*d+...+d*d
x1^2+x2^2+x3^2+x4^2 + 2*d*(x1+x2+x3+x4)+4*d^2
+=2*d*dat+(r-l+1)*d*d
*/
2024/12/27 20:15
加载中...