样例没过求助
  • 板块P1471 方差
  • 楼主Anonymely
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/7/6 21:04
  • 上次更新2023/10/27 21:41:14
查看原帖
样例没过求助
550957
Anonymely楼主2022/7/6 21:04
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define lson(p) (p<<1)
#define rson(p) ((p<<1)|1)
#define md(l,r) ((l+r)>>1)

const int N=200005;

int n,m;
int a[N];

struct tree{
	double sum;
	int l,r;
}ta[N],tb[N];

double tag[N];

void pushup(int p){
	ta[p].sum=ta[lson(p)].sum+ta[rson(p)].sum;
	tb[p].sum=tb[lson(p)].sum+tb[rson(p)].sum;
}

void pushdown(int p){
	int len1=(ta[lson(p)].r-ta[lson(p)].l+1);
	int len2=(ta[rson(p)].r-ta[rson(p)].l+1);
	tb[lson(p)].sum+=2*tag[p]*ta[lson(p)].sum+len1*tag[p]*tag[p];
	tb[rson(p)].sum+=2*tag[p]*ta[rson(p)].sum+len2*tag[p]*tag[p];
	ta[lson(p)].sum+=len1*tag[p];
	ta[rson(p)].sum+=len2*tag[p];
	tag[lson(p)]+=tag[p];
	tag[rson(p)]+=tag[p];
	tag[p]=0;
}

void build(int p,int l,int r){
	ta[p].l=tb[p].l=l,ta[p].r=tb[p].r=r;
	if(l==r){
		ta[p].sum=a[l],tb[p].sum=a[l]*a[l];
		return ;
	}
	int mid=md(l,r);
	build(lson(p),l,mid);
	build(rson(p),mid+1,r);
	pushup(p);
}

void update(int p,int l,int r,double k){
	if(l<=ta[p].l&&ta[p].r<=r){
		tag[p]+=k;
		ta[p].sum+=(ta[p].r-ta[p].l+1)*k;
		tb[p].sum+=2*k*ta[p].sum+(ta[p].r-ta[p].l+1)*k*k; 
		return ;
	}
	int mid=md(ta[p].l,ta[p].r);
	pushdown(p);
	if(l<=mid)update(lson(p),l,r,k);
	if(r>mid)update(rson(p),l,r,k);
	pushup(p); 
}

double query(int p,int l,int r,int op){
	if(l<=ta[p].l&&ta[p].r<=r){
		if(op==1)return ta[p].sum;
		else return tb[p].sum;
	}
	int mid=md(ta[p].l,ta[p].r);
	pushdown(p);
	double ans=0;
	if(l<=mid)ans+=query(lson(p),l,r,op);
	if(mid<r)ans+=query(rson(p),l,r,op);
	return ans;
}

signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	while(m--){
		int op,l,r;cin>>op>>l>>r;
		if(op==1){
			double k;cin>>k;update(1,l,r,k);
		}else if(op==2)printf("%.4lf\n",query(1,l,r,1)/(r-l+1)*1.0);
		else{
			double sum1=1.0*query(1,l,r,0)/(r-l+1),sum2=1.0*query(1,l,r,1)/(r-l+1);
			printf("%.4lf\n",sum1-sum2*sum2);
		}
	}
	return 0;
}

第三个输出了1.6000

2022/7/6 21:04
加载中...