样例过了,0pts求调(马蜂优美)
  • 板块P1471 方差
  • 楼主CNS_5t0_0r2
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/9 15:23
  • 上次更新2024/7/9 15:38:36
查看原帖
样例过了,0pts求调(马蜂优美)
999274
CNS_5t0_0r2楼主2024/7/9 15:23
#include<bits/stdc++.h>
#define mid ((l + r) >> 1)
#define lchild (root << 1)
#define rchild ((root << 1) + 1)
using namespace std;
const int N = 1e5 + 9;
int n,m;
double a[N];
double sq(double x){
	return x * x;
}
struct node{
	double sum,sq_sum;//区间和,区间平方和 
	double tag;//加法标记 
} t[N << 2];
int len(int l,int r){
	return r - l + 1;
}
bool in_range(int l,int r,int L,int R){
	return L <= l && r <= R;
}
bool out_range(int l,int r,int L,int R){
	return r < L || l > R;
} 
void push_up(int root){
	t[root].sum = t[lchild].sum + t[rchild].sum;
	t[root].sq_sum = t[lchild].sq_sum + t[rchild].sq_sum;
}
void make_tag(int root,int len,double v){
	t[root].tag += v;
	t[root].sq_sum += (sq(v) * len) + (t[root].sum * v * 2);
	t[root].sum += v * len;
}
void push_down(int root,int l,int r){
	make_tag(lchild,len(l,mid),t[root].tag);
	make_tag(rchild,len(mid + 1,r),t[root].tag);
	t[root].tag = 0;
}
void build(int root,int l,int r){
	if(l == r){
		t[root].sum = a[l];
		t[root].sq_sum = sq(a[l]);
		return;
	}
	build(lchild,l,mid);
	build(rchild,mid + 1,r);
	push_up(root);
}
void update(int root,int l,int r,int L,int R,int v){
	if(out_range(l,r,L,R))
		return;
	if(in_range(l,r,L,R)){
		make_tag(root,len(l,r),v);
		return;
	}
	push_down(root,l,r);
	update(lchild,l,mid,L,R,v);
	update(rchild,mid + 1,r,L,R,v);
	push_up(root);
}
double query_sum(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return 0;
	if(in_range(l,r,L,R))
		return t[root].sum;
	push_down(root,l,r);
	return query_sum(lchild,l,mid,L,R) + query_sum(rchild,mid + 1,r,L,R);
}
double query_sq_sum(int root,int l,int r,int L,int R){
	if(out_range(l,r,L,R))
		return 0;
	if(in_range(l,r,L,R))
		return t[root].sq_sum;
	push_down(root,l,r);
	return query_sq_sum(lchild,l,mid,L,R) + query_sq_sum(rchild,mid + 1,r,L,R);
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1;i <= n;i++)
		scanf("%lf", &a[i]);
	build(1,1,n);
	while(m--){
		int op,l,r;
		scanf("%d%d%d", &op, &l, &r);
		if(op == 1){
			double k;
			scanf("%lf", &k);
			update(1,1,n,l,r,k);
		}
		else if(op == 2){
			double aver = query_sum(1,1,n,l,r) / len(l,r);
			printf("%.4lf\n",aver);
		}
		else if(op == 3){
			double aver = query_sum(1,1,n,l,r) / len(l,r);
			double sq_sum = query_sq_sum(1,1,n,l,r) / len(l,r);
			printf("%.4lf\n",sq_sum - sq(aver));
		}
	}
	return 0;
} 
2024/7/9 15:23
加载中...