求助
  • 板块P1471 方差
  • 楼主Kevinx
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/12/1 13:15
  • 上次更新2023/10/27 00:51:42
查看原帖
求助
126972
Kevinx楼主2022/12/1 13:15

样例过了,但是爆0。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5 + 20;
ll n, m, opt;
double tag[N], k, a[N];
struct data {
	double sum, nul;
}tree[4 * N];
inline ll ls(ll x) {return x << 1;}
inline ll rs(ll x) {return x << 1 | 1;}

data build(ll p, ll l, ll r) {
	data tmp;
	tmp.nul = tmp.sum = 0.0;
	if(l == r) {
		tmp.sum = tree[p].sum = a[l];
		tmp.nul = tree[p].nul = a[l] * a[l];
		return tmp;
	}
	ll mid = (l + r) / 2;
	data tmpl = build(ls(p), l, mid), tmpr = build(rs(p), mid + 1, r);
	tree[p].sum = tmpl.sum + tmpr.sum;
	tree[p].nul = tmpl.nul + tmpr.nul;
	return tree[p];
}
void up(ll p) {
	tree[p].sum = tree[ls(p)].sum + tree[rs(p)].sum;
	tree[p].nul = tree[ls(p)].nul + tree[rs(p)].nul;
	return;
}

void down(ll p, ll l, ll r) {
/*
        tree[p].sum += (r - l + 1) * k;
		tree[p].nul += n * k * k + 2 * k * query_sum(1, 1, n, l, r);
		tag[p] += k;
*/
    if(tag[p] == 0.0) return;
    
	ll mid = (l + r) / 2;
	
	tag[ls(p)] += tag[p];
	tag[rs(p)] += tag[p];
	
	
	tree[ls(p)].nul += (mid - l + 1) * tag[p] * tag[p] + 2.0 * tag[p] * tree[p].sum;
	tree[rs(p)].nul += (r - mid) * tag[p] * tag[p] + 2.0 * tag[p] * tree[p].sum;
	
	tree[ls(p)].sum += (mid - l + 1) * tag[p];
	tree[rs(p)].sum += (r - mid) * tag[p];
	
	
	
//	tag[ls(p)] += tag[p];
//	tag[rs(p)] += tag[p];
	
	tag[p] = 0.0;
	return;
}

double query_sum(ll p, ll l, ll r, ll L, ll R) {
	double res = 0;
	if(L <= l && r <= R) {
		return tree[p].sum;
	} 
	down(p, l, r);
    ll mid = (l + r) / 2;
	if(L <= mid)     res += query_sum(ls(p), l, mid, L, R);
    if(R > mid)      res += query_sum(rs(p), mid + 1, r, L, R);
    up(p);
    
	return res;
}

double query_nul(ll p, ll l, ll r, ll L, ll R) {
	double res = 0;
	if(L <= l && r <= R) {
		return tree[p].nul;
	} 
	down(p, l, r);
    ll mid = (l + r) / 2;
	if(L <= mid)     res += query_nul(ls(p), l, mid, L, R);
    if(R > mid)      res += query_nul(rs(p), mid + 1, r, L, R);
    up(p);
    
	return res;
}

void add(ll p, ll l, ll r, ll L, ll R, double k) {
	if(L <= l && r <= R) {
		tree[p].nul += (r - l + 1) * k * k + 2 * k * tree[p].sum;
		tree[p].sum += (r - l + 1) * k;
		tag[p] += k;
		return;
	}
	down(p, l, r);
	ll mid = (l + r) / 2;
	if(L <= mid)     add(ls(p), l, mid, L, R, k);
    if(R > mid)      add(rs(p), mid + 1, r, L, R, k);
    up(p);
    
    return;
}
int main(){
//	freopen("a.in", "r", stdin);
//	freopen("a.out", "w", stdout);
	
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
    	cin >> a[i];
	}
	build(1, 1, n);

    for(int i = 1; i <= m; i++) {
    	double x, y;
    	cin >> opt >> x >> y;
    	if(opt == 1) {
    		cin >> k;
    		add(1, 1, n, x, y, k);
		}
		if(opt == 2) {
			if(x > y) swap(x, y);
    		printf("%.4lf\n",query_sum(1, 1, n, x, y) / (y - x + 1));
		}
		if(opt == 3) {
			if(x > y) swap(x, y);
            double S = query_sum(1, 1, n, x, y) / (y - x + 1), NUL = query_nul(1, 1, n, x, y) / (y - x + 1);
            double ANS = NUL - (S * S);
    		printf("%.4lf\n",ANS);
		}
		
	}
	return 0;
}
//2 250  P
2022/12/1 13:15
加载中...