样例没过,求调qwq
  • 板块P1471 方差
  • 楼主穼柗°
  • 当前回复4
  • 已保存回复4
  • 发布时间2025/1/23 21:20
  • 上次更新2025/1/24 08:54:21
查看原帖
样例没过,求调qwq
1045961
穼柗°楼主2025/1/23 21:20
#include <iostream>
using namespace std;
using cint=const int;
using cdb=const double;
double a[100001],pj[400001],fc[400001],pf[400001],he[400001],tag[400001];
// pj[] 存平均数,fc[] 存方差,pf[] 存平方和,he[] 存区间和,tag[] 表示区间加的懒标记
void build(cint u,cint l,cint r) {
	if(l==r) {
		he[u]=pj[u]=a[l],pf[u]=a[l]*a[l];
		return;
	}
	cint mid=(l+r)>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	he[u]=he[u<<1]+he[u<<1|1];
	pf[u]=pf[u<<1]+pf[u<<1|1];
	pj[u]=he[u]/(r-l+1);
	fc[u]=pj[u]*pj[u]+(1-pj[u]*2)/(r-l+1)*pf[u];
}
void apply(cint u,cint l,cint r,cdb x) {
	tag[u]+=x,pj[u]+=x,he[u]+=(r-l+1)*x;
	pf[u]+=2*x*he[u]+x*x;
	fc[u]=pj[u]*pj[u]+(1-pj[u]*2)/(r-l+1)*pf[u];
}
void pushdown(cint u,cint l,cint r) {
	if(tag[u]) { // 标记下传
		cint mid=(l+r)>>1;
		apply(u<<1,l,mid,tag[u]);
		apply(u<<1|1,mid+1,r,tag[u]);
		tag[u]=0;
	}
}
void upd(cint u,cint l,cint r,cint s,cint t,cdb x) { // 区间加
	if(s<=l&&r<=t) {apply(u,l,r,x);return;}
	pushdown(u,l,r);
	cint mid=(l+r)>>1;
	if(s<=mid) upd(u<<1,l,mid,s,t,x);
	if(t>mid) upd(u<<1|1,mid+1,r,s,t,x);
	he[u]=he[u<<1]+he[u<<1|1];
	pf[u]=pf[u<<1]+pf[u<<1|1];
	pj[u]=he[u]/(r-l+1);
	fc[u]=pj[u]*pj[u]+(1-pj[u]*2)/(r-l+1)*pf[u];
}
double queryhe(cint u,cint l,cint r,cint s,cint t) { // 查询区间和
	if(s<=l&&r<=t) return he[u];
	cint mid=(l+r)>>1;
	pushdown(u,l,r);
	if(t<=mid) return queryhe(u<<1,l,mid,s,t);
	if(s>mid) return queryhe(u<<1|1,mid+1,r,s,t);
	return queryhe(u<<1,l,mid,s,t)+queryhe(u<<1|1,mid+1,r,s,t);
}
double querypf(cint u,cint l,cint r,cint s,cint t) { 查询区间平方和
	if(s<=l&&r<=t) return pf[u];
	cint mid=(l+r)>>1;
	pushdown(u,l,r);
	if(t<=mid) return querypf(u<<1,l,mid,s,t);
	if(s>mid) return querypf(u<<1|1,mid+1,r,s,t);
	return querypf(u<<1,l,mid,s,t)+querypf(u<<1|1,mid+1,r,s,t);
}
double queryfc(cint u,cint l,cint r,cint s,cint t) { // 查询方差
	cdb pjs=queryhe(u,l,r,s,t)/(r-l+1);
	return pjs*pjs+querypf(u,l,r,s,t)/(r-l+1)*(1-pjs*2);
}
int n,m;
int main() {
	cin.tie(nullptr)->sync_with_stdio(false),
	cout.tie(nullptr);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lf",a+i);
	build(1,1,n);
	for(int op,x,y;m--;) {
		scanf("%d%d%d",&op,&x,&y);
		if(op==1) {
			double k;
			scanf("%lf",&k);
			upd(1,1,n,x,y,k);
		}
		else if(op==2)
			printf("%.4lf\n",queryhe(1,1,n,x,y)/n);
		else
			printf("%.4lf\n",queryfc(1,1,n,x,y));
	}
	return 0;
}
2025/1/23 21:20
加载中...