线段树WA三个点求助,可能是精度问题
  • 板块P1471 方差
  • 楼主fuyuzhe2007
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/11/5 22:12
  • 上次更新2023/10/27 04:08:09
查看原帖
线段树WA三个点求助,可能是精度问题
414521
fuyuzhe2007楼主2022/11/5 22:12
#include<bits/stdc++.h>
using namespace std;

int n,m;
double val1[400005];//区间和
double val2[400005];//平方和
double tag[400005];//延迟标记 
double a[100005];

void pushup(int o){
	val1[o]=val1[2*o]+val1[2*o+1];
	val2[o]=val2[2*o]+val2[2*o+1];
}

void pushdown(int l,int r,int o){
	tag[2*o]+=tag[o];
	tag[2*o+1]+=tag[o];
	int mid=(l+r)/2;
	val2[2*o]+=2*tag[o]*val1[2*o]+(mid-l)*tag[o]*tag[o];
	val1[2*o]+=(mid-l)*tag[o];
	val2[2*o+1]+=2*tag[o]*val1[2*o+1]+(mid-l)*tag[o]*tag[o];
	val1[2*o+1]+=(r-mid)*tag[o];
	tag[o]=0;
}

void build(int l,int r,int o){
	if(r-l<=1){
		val1[o]=a[l];
		val2[o]=a[l]*a[l];
		return;
	}
	int mid=(l+r)/2;
	build(l,mid,2*o);
	build(mid,r,2*o+1);
	pushup(o);
}

void add(int al,int ar,int l,int r,int o,double v){
	if(al<=l&&r<=ar){
		tag[o]+=v;
		val2[o]+=2*v*val1[o]+(r-l)*v*v;
		val1[o]+=(r-l)*v;
		return;
	}
	int mid=(l+r)/2;
	if(tag[o])pushdown(l,r,o);
	if(al<mid)add(al,ar,l,mid,2*o,v);
	if(mid<ar)add(al,ar,mid,r,2*o+1,v);
	pushup(o);
}

double query1(int ql,int qr,int l,int r,int o){
	if(ql<=l&&r<=qr)return val1[o];
	int mid=(l+r)/2;
	if(tag[o])pushdown(l,r,o);
	double s=0;
	if(ql<mid) s+=query1(ql,qr,l,mid,2*o);
	if(mid<qr) s+=query1(ql,qr,mid,r,2*o+1);
	pushup(o);
	return s;
}

double query2(int ql,int qr,int l,int r,int o){
	if(ql<=l&&r<=qr)return val2[o];
	int mid=(l+r)/2;
	if(tag[o])pushdown(l,r,o);
	double s=0;
	if(ql<mid) s+=query2(ql,qr,l,mid,2*o);
	if(mid<qr) s+=query2(ql,qr,mid,r,2*o+1);
	pushup(o);
	return s;
}
 
int main(){
	freopen("P1471.in","r",stdin);
	freopen("P1471.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%lf",a+i);
	}
	build(0,n,1);
	int x,y;
	double k;
	while(m--){
		int typ;
		scanf("%d",&typ);
		if(typ==1){
			scanf("%d %d",&x,&y);
			cin >> k;
			add(x-1,y,0,n,1,k);
		}
		else if(typ==2){
			scanf("%d %d",&x,&y);
			printf("%.4lf\n",query1(x-1,y,0,n,1)/(y-x+1));
		}
		else if(typ==3){
			scanf("%d %d",&x,&y);
			double ans1=query1(x-1,y,0,n,1);
			double ans2=query2(x-1,y,0,n,1);
			printf("%.4lf\n",ans2/(y-x+1)-ans1/(y-x+1)*ans1/(y-x+1));
		}
	}
	return 0;
}


2022/11/5 22:12
加载中...