40pts 求调
  • 板块P1471 方差
  • 楼主hbiikk
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/6/15 09:58
  • 上次更新2024/6/15 10:30:13
查看原帖
40pts 求调
1095030
hbiikk楼主2024/6/15 09:58
#include <iostream>
using namespace std;
#define int long long
#define ls 2*u
#define rs 2*u+1
const int N=1e5+10;
struct tree{
	double sum,sumn;
	double tag ;
}tr[4*N];
int n,m;
double a[N];
void pushup(int u) {
	tr[u].sum = tr[ls].sum + tr[rs].sum ;
	tr[u].sumn = tr[ls].sumn + tr[rs].sumn;
}
void build(int u,int l,int r) {
	if(l == r) {
		tr[u].sum = a[l] ;
		tr[u].sumn = a[l]*a[l];
		tr[u].tag = 0;
		return ;
	}
	int mid = l+r >>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushup(u);
	return ;
}
void maketag(int u,int l,int r,double x) {
	int n = r-l+1;
	tr[u].tag += x;
	tr[u].sumn += n*x*x+2*tr[u].sum*x;
	tr[u].sum += n*x;
}
void pushdown(int u,int l,int r) {
	double x = tr[u].tag;
	int mid = l+r >>1;
	maketag(ls,l,mid,x),maketag(rs,mid+1,r,x);
	tr[u].tag = 0;
	return ;
}
bool inrange(int L,int R,int l,int r) {
	return (l<=L&&r>=R);
}
bool outrange(int L,int R,int l,int r) {
	return (l>R||r<L);
}
void add(int u,int L,int R,int l,int r,double x) {
	if(inrange(L,R,l,r)) {
		maketag(u,L,R,x);
	}else if(!outrange(L,R,l,r)) {
		int mid = L+R >> 1;
		pushdown(u,L,R);
		add(ls,L,mid,l,r,x),add (rs,mid+1,R,l,r,x);
		pushup(u);
		return ;
	}else return ;
}
double query(int u,int L,int R,int l,int r,int opt) {
	if(opt == 1) {
		if(inrange(L,R,l,r)) {
			return tr[u].sum;
		} else if(!outrange(L,R,l,r)) {
			pushdown(u,L,R);
			int mid = L+R >>1;
			return query(ls,L,mid,l,r,opt)+query(rs,mid+1,R,l,r,opt);
		}else return 0;
	}else {
		if(inrange(L,R,l,r)) {
			return tr[u].sumn;
		} else if(!outrange(L,R,l,r)) {
			pushdown(u,L,R);
			int mid = L+R >>1;
			return query(ls,L,mid,l,r,opt)+query(rs,mid+1,R,l,r,opt);
		}else return 0;
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	int opt,l,r;
	double x;
	build(1,1,n);
	for(int i=1;i<=m;i++) {
		cin>>opt>>l>>r;
		if(opt == 1) {
			cin>>x;
			add(1,1,n,l,r,x);
		}else if(opt == 2) {
			printf("%.4lf\n",query(1,1,n,l,r,1)/(r-l+1));
		}else {
				int n=(r-l+1);
				double avg = query(1,1,n,l,r,1)/(r-l+1);
				double sum =query(1,1,n,l,r,2)/n;
				printf("%.4lf\n",sum-avg*avg);
		}
	}
	return 0;
}
2024/6/15 09:58
加载中...