样例正确,提交全WA求调
  • 板块P1471 方差
  • 楼主microchip
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/21 17:04
  • 上次更新2024/8/21 19:54:08
查看原帖
样例正确,提交全WA求调
241838
microchip楼主2024/8/21 17:04

目测没有本应使用double却用了int的地方

#include<iostream>
#include<iomanip>
using namespace std;

struct SegmentTree{
	double sum,powsum,tag;
}T[400005];

int n,m,op,L,R;
double a[100005],x;

void build_tree(int l,int r,int no){
	T[no].tag=0;
	if(l==r){
		T[no].sum=a[l];
		T[no].powsum=a[l]*a[l];
		return;
	}int mid=(l+r)>>1;
	build_tree(l,mid,no*2);
	build_tree(mid+1,r,no*2+1);
	T[no].sum=T[no*2].sum+T[no*2+1].sum;
	T[no].powsum=T[no*2].powsum+T[no*2+1].powsum;
}

void update(int no,int l,int r){
	int mid=(l+r)>>1;
	T[no*2].powsum+=(mid-l+1)*T[no].tag*T[no].tag+2*T[no].tag*T[no*2].sum;
	T[no*2].sum+=(mid-l+1)*T[no].tag;
	T[no*2+1].powsum+=(r-mid)*T[no].tag*T[no].tag+2*T[no].tag*T[no*2+1].sum;
	T[no*2+1].sum+=(r-mid)*T[no].tag;
	T[no].tag=0;
}

void range_add(int l,int r,int no){
	if(l>R||r<L)return;
	if(l>=L&&r<=R){
		T[no].powsum+=(r-l+1)*x*x+2*x*T[no].sum;
		T[no].sum+=(r-l+1)*x;
		T[no].tag+=x;
		return;
	}update(no,l,r);
	int mid=(l+r)>>1;
	range_add(l,mid,no*2);
	range_add(mid+1,r,no*2+1);
	T[no].sum=T[no*2].sum+T[no*2+1].sum;
	T[no].powsum=T[no*2].powsum+T[no*2+1].powsum;
}

double range_sum(int l,int r,int no){
	if(l>R||r<L)return 0;
	if(l>=L&&r<=R)return T[no].sum;
	update(no,l,r);
	int mid=(l+r)>>1;
	return range_sum(l,mid,no*2)+range_sum(mid+1,r,no*2+1);
}

double range_powsum(int l,int r,int no){
	if(l>R||r<L)return 0;
	if(l>=L&&r<=R)return T[no].powsum;
	update(no,l,r);
	int mid=(l+r)>>1;
	return range_powsum(l,mid,no*2)+range_powsum(mid+1,r,no*2+1);
}

int main()
{
//	freopen("input.txt","r",stdin);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build_tree(1,n,1);
	while(m--){
		cin>>op;
		switch(op){
			case 1:{
				cin>>L>>R>>x;
				range_add(1,n,1);
				break;
			}case 2:{
				cin>>L>>R;
				cout<<fixed<<setprecision(4)<<range_sum(1,n,1)/(R-L+1)<<endl;
				break;
			}case 3:{
				cin>>L>>R;
				cout<<fixed<<setprecision(4)<<range_powsum(1,n,1)/(R-L+1)-(range_sum(1,n,1)/(R-L+1))*(range_sum(1,n,1)/(R-L+1))<<endl;
				break;
			}default:break;
		}
	}
    return 0;
}

2024/8/21 17:04
加载中...