40pts qz
查看原帖
40pts qz
577241
违规用户名577241楼主2024/5/17 20:06
#include <iostream>
#include <cstdio>
using namespace std;
double n, m;
const int N = 1E5 + 5;
double a[N];
struct segment_tree
{
	int l, r;
	double sum1= 0.0, sum2 = 0.0;
	double tag = 0.0;
};
segment_tree tree[N << 2];
void pushup(int u)
{
	tree[u].sum1 = tree[u * 2].sum1 + tree[u * 2 + 1].sum1;
	tree[u].sum2 = tree[u * 2].sum2 + tree[u * 2 + 1].sum2;
}
void build(int u, int l, int r)
{
	tree[u].l = l, tree[u].r = r;
	if (l == r)
	{
		tree[u].sum1 = a[l];
		tree[u].sum2 = a[l] * a[l];
		return;
	}
	int mid = (l + r) / 2;
	build(u * 2, l, mid);
	build(u * 2 + 1, mid + 1, r);
	pushup(u);
}
void pushdown(int u)//
{
	tree[u * 2].sum2 += (tree[u * 2].r - tree[u * 2].l + 1) * tree[u].tag * tree[u].tag;
	tree[u * 2].sum2 += 2 * tree[u].tag * tree[u * 2].sum1;
	tree[u * 2 + 1].sum2 += (tree[u * 2 + 1].r - tree[u * 2 + 1].l + 1) * tree[u].tag * tree[u].tag;
	tree[u * 2 + 1].sum2 += 2 * tree[u].tag * tree[u * 2 + 1].sum1;
	tree[u * 2].sum1 += (tree[u * 2].r - tree[u * 2].l + 1) * tree[u].tag;
	tree[u * 2 + 1].sum1 += (tree[u * 2 + 1].r - tree[u * 2 + 1].l + 1) * tree[u].tag;
	tree[u * 2].tag += tree[u].tag;
	tree[u * 2 + 1].tag += tree[u].tag;
	tree[u].tag = 0.0;
}
void update(int u, int L, int R, double k)
{
	int l = tree[u].l, r = tree[u].r;
	if (L <= l && r <= R)
	{
		tree[u].tag += k;
		tree[u].sum2 += (r - l + 1) * 1.00  * k * k + 2 * k * tree[u].sum1; 
		tree[u].sum1 += (r - l + 1) * 1.00  * k;
		return;
	}
	pushdown(u);
	int mid = (l + r) / 2;
	if (L <= mid) update(u * 2, L, R, k);
	if (R > mid) update(u * 2 + 1, L, R, k);
	pushup(u);
}
double query_sum1(int u, int L, int R)
{
	int l = tree[u].l, r = tree[u].r;
	if (L <= l && r <= R) return tree[u].sum1;
	pushdown(u);
	int mid = (l + r) / 2;
	double res = 0.00;
	if (L <= mid) res += query_sum1(u * 2, L, R);
	if (R > mid) res += query_sum1(u * 2 + 1, L, R);
	return res;
}
double query_sum2(int u, int L, int R)
{
	int l = tree[u].l, r = tree[u].r;
	if (L <= l && r <= R) return tree[u].sum2;
	pushdown(u);
	int mid = (l + r) / 2;
	double res = 0.00;
	if (L <= mid) res += query_sum2(u * 2, L, R);
	if (R > mid) res += query_sum2(u * 2 + 1, L, R);
	return res;
}
int main()
{
	scanf("%lf%lf", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%lf", &a[i]);
	build(1, 1, n);
	for (int i = 1; i <= m; i++) 
	{
		int opt;
		scanf("%d", &opt);
		int x, y;
		scanf("%d%d", &x, &y);
		if (opt == 1)
		{
			double k;
			scanf("%lf", &k);
			update(1, x, y, k);
		}
		if (opt == 2)
		{
			double ans = query_sum1(1, x, y) / (y - x + 1) * 1.00;
			printf("%.4lf\n", ans);
		}
		if (opt == 3)
		{
			double cnt = query_sum1(1, x, y) / (y - x + 1) * 1.00;
			double cnt1 = query_sum2(1, x, y) / n * 1.00;
			printf("%.4lf\n", cnt1 - cnt * cnt);
		}
	}
	return 0;
}
2024/5/17 20:06
加载中...