全WA求助,样例也过不了
  • 板块P1471 方差
  • 楼主Bodhi
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/1/1 23:34
  • 上次更新2023/10/24 05:51:25
查看原帖
全WA求助,样例也过不了
364848
Bodhi楼主2023/1/1 23:34

我的代码:

#include <bits/stdc++.h>
using namespace std;

using db = double;
const int R = 1e5 + 10;
db a[R];
#define lc k << 1
#define rc k << 1 | 1
struct Node
{
	int l, r;
	db sum, sum1, tag; // 一个维护a1+a2+...+an,一个维护a1^2+a2^2+...+an^2
} s[R << 2];
void pushup(int k)
{
	s[k].sum = s[lc].sum + s[rc].sum;
	s[k].sum1 = s[lc].sum1 + s[rc].sum1;
}
void add(int k, db val)
{
	s[k].tag += val;
	s[k].sum1 += 2 * val * s[k].sum + db(s[k].r - s[k].l + 1) * val * val; // 有依赖,所以先处理平方和
	s[k].sum += val * db(s[k].r - s[k].l + 1);
}
void pushdown(int k)
{ // 为什么lazytag的值和已经加上的值要同时存在?思考一下叶子结点就行了。如果update到了叶子结点,那么叶子结点的值就永远不会被更新
	// 试验后发现,如果对叶子结点进行过add,那么它的tag就不会被清零,但是也不会影响结果
	if (s[k].tag)
	{
		add(lc, s[k].tag);
		add(rc, s[k].tag);
		s[k].tag = 0;
	}
}
void build(int k, int l, int r)
{
	s[k].l = l;
	s[k].r = r;
	if (l == r)
	{
		s[k].sum = a[l];
		s[k].sum1 = a[l] * a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(lc, l, mid);
	build(rc, mid + 1, r);
	pushup(k);
}
void update(int k, int x, int y, db val)
{
	// if (s[k].l < x || s[k].r > y)
	// 	return;
	if (s[k].l >= x && s[k].r <= y)
	{
		add(k, val);
		return;
	}
	pushdown(k);
	int mid = (s[k].l + s[k].r) >> 1;
	// update(lc, x, y, val);
	// update(rc, x, y, val);
	if (x <= s[k].l)
		update(lc, x, y, val);
	if (y > s[k].r)
		update(rc, x, y, val);
	pushup(k);
}
db query1(int k, int x, int y)
{
	// if (s[k].l < x || s[k].r > y)
	// 	return 0;
	if (s[k].l >= x && s[k].r <= y)
		return s[k].sum;
	int mid = (s[k].l + s[k].r) >> 1;
	pushdown(k);
	db res = 0;
	// res = query1(lc, x, y) + query1(rc, x, y);
	if (x <= mid)
		res = query1(lc, x, y);
	if (y > mid)
		res += query1(rc, x, y);
	return res;
}
db query2(int k, int x, int y)
{
	// if (s[k].l < x || s[k].r > y)
	// 	return 0;
	if (s[k].l >= x && s[k].r <= y)
		return s[k].sum1;
	int mid = (s[k].l + s[k].r) >> 1;
	pushdown(k);
	db res = 0;
	if (x <= mid)
		res = query2(lc, x, y);
	if (y > mid)
		res += query2(rc, x, y);
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m, l, r, t;
	cin >> n >> m;
	int j;
	for (j = 1; j <= n; ++j)
	{
		cin >> a[j];
	}
	build(1, 1, n);
	db tmp, avg, k;
	for (j = 1; j <= m; ++j)
	{
		cin >> t;
		if (t == 1)
		{
			cin >> l >> r >> k;
			update(1, l, r, k);
		}
		else if (t == 2)
		{
			cin >> l >> r;
			avg = query1(1, l, r) / db(r - l + 1);
			cout << fixed << setprecision(4) << avg << '\n';
		}
		else
		{
			cin >> l >> r;
			// cout << query1(1, l, r) << ' ' << query2(1, l, r) << '\n';
			avg = query1(1, l, r) / db(r - l + 1);
			tmp = query2(1, l, r) / db(r - l + 1) - avg * avg;
			cout << fixed << setprecision(4) << tmp << '\n';
		}
	}
	// for (j = 1; j <= n * 4; ++j)
	// {
	// 	cout << s[j].tag << '\n';
	// }
	return 0;
}

看的别人的代码:

#include <iostream>
#include <iomanip>
using namespace std;
const int N = 100005;
double a[N], sum[4 * N], sum2[4 * N];
double tag[4 * N];

void pushup(int k)
{
	sum[k] = sum[k * 2] + sum[k * 2 + 1];	 // 区间和
	sum2[k] = sum2[k * 2] + sum2[k * 2 + 1]; // 区间平方和
	return;
}

void Add(int k, int lt, int rt, double val)
{ // 打懒标记
	tag[k] += val;
	sum2[k] += 2 * val * sum[k] + val * val * (rt - lt + 1);
	sum[k] += (rt - lt + 1) * val;
	return;
}

void pushdown(int k, int lt, int rt)
{
	if (tag[k] == 0)
		return;
	int mid = lt + (rt - lt) / 2;
	Add(k * 2, lt, mid, tag[k]);
	Add(k * 2 + 1, mid + 1, rt, tag[k]);
	tag[k] = 0; // 将标记传给子节点后,父节点的标记要清零,否则会加重复
	return;
}

void build(int k, int lt, int rt)
{ // 第k个结点, lt rt为要询问的区间范围
	if (lt == rt)
	{
		sum[k] = a[lt];			 // a为原始数组,sum[k]为第k个结点的区间和
		sum2[k] = a[lt] * a[lt]; // 平方
		return;
	}
	int mid = (lt + rt) >> 1;
	build(k * 2, lt, mid);
	build(k * 2 + 1, mid + 1, rt);
	pushup(k);
	return;
}
// 在qx, qy区间每个数加上val
void update(int k, int lt, int rt, int qx, int qy, double val)
{
	if (lt > qy || rt < qx)
		return;
	else if (lt >= qx && rt <= qy)
	{
		Add(k, lt, rt, val);
		return;
	}
	int mid = lt + (rt - lt) / 2;
	pushdown(k, lt, rt);
	update(k * 2, lt, mid, qx, qy, val);
	update(k * 2 + 1, mid + 1, rt, qx, qy, val);
	pushup(k);
	return;
}

double query(int k, int lt, int rt, int qx, int qy)
{
	if (lt > qy || rt < qx)
		return 0;
	else if (lt >= qx && rt <= qy)
		return sum[k];
	int mid = lt + (rt - lt) / 2;
	pushdown(k, lt, rt); // 询问时才下传标记,因为需要知道子区间要加的值
	return query(k * 2, lt, mid, qx, qy) + query(k * 2 + 1, mid + 1, rt, qx, qy);
}

double query2(int k, int lt, int rt, int qx, int qy)
{
	if (lt > qy || rt < qx)
		return 0;
	else if (lt >= qx && rt <= qy)
		return sum2[k];
	int mid = lt + (rt - lt) / 2;
	pushdown(k, lt, rt); // 询问时才下传标记,因为需要知道子区间要加的值
	return query2(k * 2, lt, mid, qx, qy) + query2(k * 2 + 1, mid + 1, rt, qx, qy);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	build(1, 1, n); // 建树
	for (int i = 1; i <= m; i++)
	{
		int option, x, y;
		double v;
		cin >> option;
		if (option == 1)
		{
			cin >> x >> y >> v;
			update(1, 1, n, x, y, v);
		}
		else if (option == 2)
		{
			cin >> x >> y;
			cout << fixed << setprecision(4) << query(1, 1, n, x, y) / (y - x + 1) << "\n";
		}
		else
		{
			cin >> x >> y;
			cout << query(1, 1, n, x, y) << ' ' << query2(1, 1, n, x, y) << '\n';
			double avg = query(1, 1, n, x, y) / (y - x + 1);
			// cout << fixed << setprecision(4) << -avg * avg + query2(1, 1, n, x, y) / (y - x + 1) << "\n";
		}
	}
	// for (int j = 1; j <= n * 4; ++j)
	// {
	// 	cout << tag[j] << '\n';
	// }
	return 0;
}

样例的操作5始终过不去,被卡好久了,能救救孩子吗QAQ

2023/1/1 23:34
加载中...