Lutece 2156 数理统计

题目链接: https://acm.uestc.edu.cn/problem/shu-li-tong-ji/description

分析:

线段树模板题。

最简单的方法,找三个板子,写三棵树。但是这样子写,应该不会爆内存,但是可能会超时。所以应该写在同一棵树里。

结点数要开区间数的四倍。这道题的初始值为0,当初始值不为0时,只需要修改st[o] = 0为st[o] = a[l] (a为输入数据存储数组)即可达到初始化赋值的效果。

pushup,即该结点的区间和为两个子结点的区间和和的和,最大值为两结点最大值的最大值,最小值为两结点最小值的最小值。

pushdown,首先检查该结点上有没有更新信息,如果有,先把更新信息传递到子结点。然后修改两个结点的区间和。由于是区间内的所有数同加一个数,所以最大最小值的修改只需要加一遍就行了。

更新也没什么好说的,先更新自己,然后更新左右子结点,最后向上更新状态。因为最后需要返回三个值,所以定义了一个结构体。

查询左边,查询右边,然后综合一下信息,返回就行了。

总的来说,这道题是一道再明显不过的模板题。如果以后需要用其中的某些功能(求和、最值),只要把一些代码注释掉,就可以用了。

最终的复杂度为O(N+QlogN)。

代码:

#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000001
long long add[MAXN << 2], st[MAXN << 2], maxnum[MAXN << 2], minnum[MAXN << 2];
void build(long long o, long long l, long long r)
{
	if (l == r)st[o] = 0;
	else
	{
		long long m = l + ((r - l) >> 1);
		build(o << 1, l, m);
		build((o << 1) | 1, m + 1, r);
		st[o] = st[o << 1] + st[(o << 1) | 1];
	}
}
void pushup(long long o)
{
	st[o] = st[o << 1] + st[o << 1 | 1];
	maxnum[o] = max(maxnum[o << 1], maxnum[o << 1 | 1]);
	minnum[o] = min(minnum[o << 1], minnum[o << 1 | 1]);
}

void pushdown(long long o, long long l, long long r)
{
	if (add[o])
	{
		add[o << 1] += add[o];
		add[o << 1 | 1] += add[o];
		long long m = l + ((r - l) >> 1);
		st[o << 1] += add[o] * (m - l + 1);
		st[o << 1 | 1] += add[o] * (r - m);
		maxnum[o << 1] += add[o];
		maxnum[o << 1 | 1] += add[o];
		minnum[o << 1] += add[o];
		minnum[o << 1 | 1] += add[o];
		add[o] = 0;
	}
}

void update(long long o, long long l, long long r, long long ql, long long qr, long long addv)
{
	if (ql <= l && qr >= r)
	{
		add[o] += addv;
		st[o] += addv * (r - l + 1);
		maxnum[o] += addv;
		minnum[o] += addv;
		return;
	}

	pushdown(o, l, r);
	long long m = l + ((r - l) >> 1);
	if (ql <= m)update(o << 1, l, m, ql, qr, addv);
	if (qr >= m + 1)update(o << 1 | 1, m + 1, r, ql, qr, addv);
	pushup(o);
}
struct returnvalue
{
	long long ans, maxs, mins;
	returnvalue operator=(const returnvalue& a)
	{
		this->ans = a.ans;
		this->maxs = a.maxs;
		this->mins = a.mins;
		return *this;
	}
};
returnvalue query(long long o, long long l, long long r, long long ql, long long qr)
{
	returnvalue qwe;
	qwe.ans = 0;
	qwe.maxs = -999999999999;
	qwe.mins = 999999999999;
	if (ql <= l && qr >= r)
	{
		qwe.ans = st[o];
		qwe.maxs = maxnum[o];
		qwe.mins = minnum[o];
		return qwe;
	}
	pushdown(o, l, r);
	long long m = l + ((r - l) >> 1);
	if (ql <= m)
	{
		returnvalue asd = query(o << 1, l, m, ql, qr);
		qwe.ans += asd.ans;
		qwe.maxs = max(asd.maxs, qwe.maxs);
		qwe.mins = min(asd.mins, qwe.mins);
	}
	if (qr >= m + 1)
	{
		returnvalue asd = query(o << 1 | 1, m + 1, r, ql, qr);
		qwe.ans += asd.ans;
		qwe.maxs = max(asd.maxs, qwe.maxs);
		qwe.mins = min(asd.mins, qwe.mins);
	}
	return qwe;
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	long long n, q,o,a,s,d;
	returnvalue poi;
	cin >> n >> q;
	build(1,1,n);
	for (long long i = 0; i < q; ++i)
	{
		cin >> o;
		if (o == 1)
		{
			cin >> a >> s >> d;
			update(1,1,n,a,s,d);
		}
		else if (o == 2)
		{
			cin >> a >> s;
			poi=query(1,1,n,a,s);
			cout << poi.ans << endl;
		}
		else if (o == 3)
		{
			cin >> a >> s;
			poi = query(1, 1, n, a, s);
			cout << poi.maxs-poi.mins << endl;
		}
	}
	return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注