40pts,死活找不到错的地方
  • 板块P1471 方差
  • 楼主tidongCrazy
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/6/11 20:54
  • 上次更新2023/11/7 00:50:08
查看原帖
40pts,死活找不到错的地方
178519
tidongCrazy楼主2020/6/11 20:54

rtrt

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define leftson (p<<1)
#define Mid ((l+r)>>1)
#define mid ((tree[p].l+tree[p].r)>>1)
#define rightson (p<<1|1)

const int N = 2e6+5;

int n,m;
double arr[N];

struct node { int l,r; double ans,power,tag; }tree[N];

inline void build(int p,int l,int r) {
	
	tree[p].l = l; tree[p].r = r;
	if(l == r) { tree[p].ans = arr[l]; tree[p].power = arr[l] * arr[l]; return; }
	build(leftson,l,Mid); build(rightson,Mid+1,r);
	tree[p].ans = tree[leftson].ans + tree[rightson].ans;
	tree[p].power = tree[leftson].power + tree[rightson].power;
	
}

inline void push_down(int p) {
	
	if(tree[p].tag) {
		tree[leftson].power += 2 * tree[p].tag * tree[leftson].ans + (tree[leftson].r-tree[leftson].l+1) * tree[p].tag * tree[p].tag;
		tree[rightson].power += 2 * tree[p].tag * tree[rightson].ans + (tree[rightson].r-tree[rightson].l+1) * tree[p].tag * tree[p].tag;
		tree[leftson].ans += tree[p].tag * (tree[leftson].r - tree[leftson].l + 1);
		tree[rightson].ans += tree[p].tag * (tree[rightson].r - tree[rightson].l + 1);
		tree[leftson].tag += tree[p].tag;
		tree[rightson].tag += tree[p].tag;
		tree[p].tag = 0;
	}
	
}

inline void update(int p,int nl,int nr,double k) {
	
	if(nl <= tree[p].l && tree[p].r <= nr) {
		tree[p].tag += k;
		tree[p].power += 2 * k * tree[p].ans+(tree[p].r-tree[p].l+1)*k*k;
		tree[p].ans += (tree[p].r - tree[p].l + 1) * k;
		return;
	} push_down(p);
	if(nl <= mid) update(leftson,nl,nr,k);
	if(nr > mid) update(rightson,nl,nr,k);
	tree[p].ans = tree[leftson].ans + tree[rightson].ans;
	tree[p].power = tree[leftson].power + tree[rightson].power;
	
}

inline double query_sum(int p,int nl,int nr) {
	
	if(nl <= tree[p].l && tree[p].r <= nr) return tree[p].ans;
	push_down(p);
	double res = 0;
	if(nl <= mid) res += query_sum(leftson,nl,nr);
	if(nr > mid) res += query_sum(rightson,nl,nr);
	return res;
	
}

inline double query_power(int p,int nl,int nr) {
	
	if(tree[p].l <= nl && nr <= tree[p].r) return tree[p].power;
	push_down(p);
	double res = 0;
	if(nl <= mid) res += query_power(leftson,nl,nr);
	if(nr > mid) res += query_power(rightson,nl,nr);
	return res;
	
}

int main() {
	
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i++) scanf("%lf",&arr[i]);
	build(1,1,n);
	for(int i = 1;i <= m;i++) {
		int opt,l,r;
		scanf("%d%d%d",&opt,&l,&r);
		if(opt == 1) {
			double k;
			scanf("%lf",&k);
			update(1,l,r,k);
		} else {
			double pjs = query_sum(1,l,r)/(r-l+1);
			if(opt == 2) printf("%.4lf\n",pjs);
			else {
				double ans = query_power(1,l,r)/(r-l+1);
				double k = ans - pjs * pjs;
				printf("%.4lf\n",ans);
			}
		}
	}
	
}
2020/6/11 20:54
加载中...