样例过了·,但零分求调!
  • 板块P1471 方差
  • 楼主hnxxwpf
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/5/14 20:53
  • 上次更新2024/5/14 23:08:25
查看原帖
样例过了·,但零分求调!
700122
hnxxwpf楼主2024/5/14 20:53
#include<iostream>
#include<cmath>
#define lc p << 1
#define rc p << 1 | 1
using namespace std;
const int maxn = 1e5 + 1;
struct Tree{
	int l,r;
	double add,ave,sum;
}tr[maxn << 2];
int n,m;
double a[maxn];
void build(int p,int l,int r){
	tr[p] = (Tree) {l,r,0,a[l],a[l]*a[l]};
	if(l == r) return;
	int m = l + (r - l >> 1);
	build(lc,l,m);
	build(rc,m+1,r);
	tr[p].ave = tr[lc].ave + tr[rc].ave;
	tr[p].sum = tr[lc].sum + tr[rc].sum;
}
void update(int p,int x,int y,int k){
	if(x <= tr[p].l && tr[p].r <= y){
		tr[p].sum += k * (tr[p].ave * 2 + k * (tr[p].r - tr[p].l + 1));
		tr[p].ave += (tr[p].r - tr[p].l + 1) * k;
		tr[p].add += k;
		return;
	}
	if(tr[p].add){
		tr[lc].sum += 2 * tr[p].add * tr[lc].ave + (tr[lc].r - tr[lc].l + 1) * tr[p].add * tr[p].add;
		tr[lc].ave += (tr[lc].r - tr[lc].l + 1) * tr[p].add;
		tr[lc].add += tr[p].add;
		tr[rc].sum += 2 * tr[p].add * tr[rc].ave + (tr[rc].r - tr[rc].l + 1) * tr[p].add * tr[p].add;
		tr[rc].ave += (tr[rc].r - tr[rc].l + 1) * tr[p].add;
		tr[rc].add += tr[p].add;
		tr[p].add = 0;
	}
	int m = tr[p].l + (tr[p].r - tr[p].l >> 1);
	if(x <= m) update(lc,x,y,k);
	if(y > m) update(rc,x,y,k);
	tr[p].ave = tr[lc].ave + tr[rc].ave;
	tr[p].sum = tr[lc].sum + tr[rc].sum;
}
double query1(int p,int x,int y){
	if(x <= tr[p].l && tr[p].r <= y) return tr[p].ave;
	if(tr[p].add){
		tr[lc].sum += 2 * tr[p].add * tr[lc].ave + (tr[lc].r - tr[lc].l + 1) * tr[p].add * tr[p].add;
		tr[lc].ave += (tr[lc].r - tr[lc].l + 1) * tr[p].add;
		tr[lc].add += tr[p].add;
		tr[rc].sum += 2 * tr[p].add * tr[rc].ave + (tr[rc].r - tr[rc].l + 1) * tr[p].add * tr[p].add;
		tr[rc].ave += (tr[rc].r - tr[rc].l + 1) * tr[p].add;
		tr[rc].add += tr[p].add;
		tr[p].add = 0;
	}
	int m = tr[p].l + (tr[p].r - tr[p].l >> 1);
	double res = 0;
	if(x <= m) res += query1(lc,x,y);
	if(y > m) res += query1(rc,x,y);
	return res;
}
double query2(int p,int x,int y){
	if(x <= tr[p].l && tr[p].r <= y) return tr[p].sum;
	if(tr[p].add){
		tr[lc].sum += 2 * tr[p].add * tr[lc].ave + (tr[lc].r - tr[lc].l + 1) * tr[p].add * tr[p].add;
		tr[lc].ave += (tr[lc].r - tr[lc].l + 1) * tr[p].add;
		tr[lc].add += tr[p].add;
		tr[rc].sum += 2 * tr[p].add * tr[rc].ave + (tr[rc].r - tr[rc].l + 1) * tr[p].add * tr[p].add;
		tr[rc].ave += (tr[rc].r - tr[rc].l + 1) * tr[p].add;
		tr[rc].add += tr[p].add;
		tr[p].add = 0;
	}
	int m = tr[p].l + (tr[p].r - tr[p].l >> 1);
	double res = 0;
	if(x <= m) res += query2(lc,x,y);
	if(y > m) res += query2(rc,x,y);
	return res;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++i) scanf("%lf",&a[i]);
	build(1,1,n);
	for(int i = 0,opt,x,y;i < m;++i){
		scanf("%d%d%d",&opt,&x,&y);
		if(opt == 1){
			double k;
			scanf("%lf",&k);
			update(1,x,y,k);
		}else if(opt == 2) printf("%.4lf\n",query1(1,x,y) * 1.0 / (y-x+1));
		else printf("%.4lf\n",query2(1,x,y) * 1.0 / (y-x+1) - pow(query1(1,x,y) * 1.0 / (y-x+1),2));
	}
	return 0;
}
2024/5/14 20:53
加载中...