區間合并綫段樹求調
  • 板块P1471 方差
  • 楼主ST_AS_IS_ZHY
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/17 15:39
  • 上次更新2024/4/17 18:51:27
查看原帖
區間合并綫段樹求調
235839
ST_AS_IS_ZHY楼主2024/4/17 15:39
// Problem: P1471 方差
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1471
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

struct Tree
{
	int l, r;
	double sum, len, tag, sum2;
}tr[4 * N];

int n, m;
double s[N];

void pushup(int x)
{
	tr[x].sum = tr[2 * x].sum + tr[2 * x + 1].sum;
	tr[x].len = tr[2 * x].len + tr[2 * x + 1].len;	
	tr[x].sum2 = tr[2 * x].sum2 + tr[2 * x + 1].sum2;
}

void pushdown(int x)
{
	tr[2 * x].sum2 += tr[x].tag * (2 * tr[x].tag * tr[2 * x].sum) + tr[x].tag * tr[x].tag * tr[2 * x].len;  
	tr[2 * x + 1].sum2 += tr[x].tag * (2 * tr[x].tag * tr[2 * x + 1].sum) +  tr[x].tag * tr[x].tag * tr[2 * x + 1].len;  
	tr[2 * x].sum += tr[x].tag * tr[2 * x].len;
	tr[2 * x + 1].sum += tr[x].tag * tr[2 * x + 1].len;
	tr[2 * x].tag += tr[x].tag, tr[2 * x + 1].tag += tr[x].tag;
	tr[x].tag = 0; 
}

Tree merge(Tree a, Tree b)
{
	Tree now;
	now.sum = a.sum + b.sum;
	now.sum2 = a.sum2 + b.sum2;
	now.len = a.len + b.len;
	return now;
}

void build(int x, int l, int r)
{
	tr[x].l = l, tr[x].r = r;
	if(l == r)
	{
		tr[x].sum = s[l];
		tr[x].len = 1;
		tr[x].sum2 = s[l] * s[l];
		return;
	}
	int mid = l + r >> 1;
	build(2 * x, l, mid);
	build(2 * x + 1, mid + 1, r);
	pushup(x);
}

void change(int x, int l, int r, double k)
{
	if(tr[x].l >= l && tr[x].r <= r)
	{
		tr[x].sum2 += 2 * k * tr[x].sum + k * k * tr[x].len;  
		tr[x].sum += k * tr[x].len;
		tr[x].tag += k;
		return;
	}
	pushdown(x);
	int mid = tr[x].l + tr[x].r >> 1;
	if(l <= mid) change(2 * x, l, r, k);
	if(r > mid) change(2 * x + 1, l, r, k);
	pushup(x);
}

Tree find(int x, int l, int r)
{
	if(tr[x].l >= l && tr[x].r <= r) return tr[x];
	pushdown(x);
	int mid = tr[x].l + tr[x].r >> 1;
	if(l > mid) return tr[2 * x + 1];
	if(r <= mid) return tr[2 * x];
	return merge(find(2 * x + 1, l, r), find(2 * x, l, r));
}

int main()
{
	//ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i ++) cin >> s[i];
	build(1, 1, n);
	while(m --)
	{
		int op, x, y; cin >> op >> x >> y;
		if(op == 1) 
		{
			double k; cin >> k;
			change(1, x, y, k);
		}
		else if(op == 2)
		{
			Tree ans = find(1, x, y);
			double now = ans.sum / ans.len;
			//cout << ans.l << "-->" << ans.r << " sum = " << ans.sum << " pf = " << ans.sum2 << '\n';
			printf("%.4lf\n", now);
		}
		else
		{
			Tree ans = find(1, x, y);
			//cout << ans.l << "-->" << ans.r << " sum = " << ans.sum << " pf = " << ans.sum2 << '\n';
			double now = ans.sum2 / ans.len - (ans.sum / ans.len) * (ans.sum / ans.len);
			printf("%.4lf\n", now);
		}
	}
	return 0;
}
2024/4/17 15:39
加载中...