Lutece 2143 方差

题目链接:https://acm.uestc.edu.cn/problem/fang-chai/description

题目大意:给你一段区间,让你加上一个值或者乘上一个值或者变为一个值,或者询问方差

分析:

这道题,题目要求有三种操作,很容易让人想到三个懒标记。

但实际上,三个懒标记是错的,或者说是很难实现的。在多次打标记之后,不同标记之间的前后顺序是无法确定的。我甚至不懂是否能实现,也许用队列能实现吧。

改值的操作,其实用先乘0后加值的方式就能实现。

乘与加的叠加顺序,自然是先乘后加,具体过程可以自己思考一下。

接下里就是维护方差的事情了。

方差的公式推导很简单,特别在乘了区间长度的平方之后。最后的结果是 区间平方和 × 区间长度 – 区间和的平方。

换句话说,我们只要维护区间平方和与区间和即可。

区间平方和同时加上一个值,= 原平方和 + 2 × 区间和 × 加的值 + 加的值 × 加的值 × 区间长度。同时乘一个数只要乘那个数的平方。

区间和就不用说了。

注意两个的顺序为,区间平方和-乘,区间和-乘,区间平方和-加,区间和-加。

代码:

#include<bits/stdc++.h>
using namespace std;
const long long MAXN = 100001ll;
const long long MODNUM = 1000000007ll;
long long a[MAXN];
struct node
{
	long long l, r, sum, squsum, mul, add;
	node *left, *right;
	node()
	{
		sum = 0ll; squsum = 0ll; mul = 1ll; add = 0ll;
		left = NULL; right = NULL;
	}
};
node *root = new node();
void build(node *aroot, long long l, long long r)
{
	aroot->l = l;
	aroot->r = r;
	if (l == r)
	{
		aroot->sum = a[l];
		aroot->squsum = a[l] * a[l] % MODNUM;
	}
	else
	{
		aroot->left = new node();
		aroot->right = new node();
		build(aroot->left, l, (l + r) >> 1ll);
		build(aroot->right, ((l + r) >> 1ll) + 1ll, r);
		aroot->sum = (aroot->left->sum + aroot->right->sum) % MODNUM;
		aroot->squsum = (aroot->left->squsum + aroot->right->squsum) % MODNUM;
	}
}
void pushup(node *aroot)
{
	if (aroot->left != NULL && aroot->right != NULL)
	{
		aroot->sum = (aroot->left->sum + aroot->right->sum) % MODNUM;
		aroot->squsum = (aroot->left->squsum + aroot->right->squsum) % MODNUM;
	}
}
void refresh(node *aroot, long long mulv, long long addv)
{
	aroot->squsum = (aroot->squsum * mulv% MODNUM) * mulv% MODNUM;
	aroot->sum = aroot->sum * mulv% MODNUM;
	aroot->squsum = (aroot->squsum% MODNUM + addv * aroot->sum% MODNUM + addv * aroot->sum% MODNUM + ((aroot->r - aroot->l + 1ll) * addv % MODNUM) * addv% MODNUM) % MODNUM;
	aroot->sum = (aroot->sum % MODNUM + addv * (aroot->r - aroot->l + 1ll) % MODNUM) % MODNUM;
	aroot->mul = (aroot->mul * mulv) % MODNUM;
	aroot->add = (aroot->add * mulv% MODNUM + addv) % MODNUM;
}
void pushdown(node *aroot)
{
	if (aroot->add != 0ll || aroot->mul != 1ll)
	{
		if (aroot->left != NULL && aroot->right != NULL)
		{
			refresh(aroot->left, aroot->mul, aroot->add);
			refresh(aroot->right, aroot->mul, aroot->add);
		}
		aroot->add = 0ll; aroot->mul = 1ll;
	}
}
void update(node *aroot, long long l, long long r, long long mulv, long long addv)
{
	if (aroot == NULL)
	{
		return;
	}
	if (l == aroot->l && aroot->r == r)
	{
		refresh(aroot, mulv, addv);
		return;
	}
	pushdown(aroot);
	long long m = (aroot->l + aroot->r) >> 1ll;
	if (r <= m)
	{
		update(aroot->left, l, r, mulv, addv);
	}
	else if (l > m)
	{
		update(aroot->right, l, r, mulv, addv);
	}
	else
	{
		update(aroot->left, l, m, mulv, addv);
		update(aroot->right, m + 1ll, r, mulv, addv);
	}
	pushup(aroot);
}
struct returnvalue
{
	long long ans, squans;
	returnvalue()
	{
		ans = 0ll; squans = 0ll;
	}
};
returnvalue query(node *aroot, long long l, long long r)
{
	returnvalue linshi;
	if (aroot == NULL)
	{
		return linshi;
	}
	if (l == aroot->l && aroot->r == r)
	{
		linshi.ans = aroot->sum;
		linshi.squans = aroot->squsum;
		return linshi;
	}
	pushdown(aroot);
	long long m = (aroot->l + aroot->r) >> 1ll;
	if (r <= m)
	{
		return query(aroot->left, l, r);
	}
	else if (l > m)
	{
		return query(aroot->right, l, r);
	}
	else
	{
		returnvalue asd;
		asd = query(aroot->left, l, m);
		linshi.ans = (linshi.ans + asd.ans) % MODNUM;
		linshi.squans = (linshi.squans + asd.squans) % MODNUM;
		asd = query(aroot->right, m + 1ll, r);
		linshi.ans = (linshi.ans + asd.ans) % MODNUM;
		linshi.squans = (linshi.squans + asd.squans) % MODNUM;
		return linshi;
	}
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	long long n, q, o, L, R, K;
	cin >> n >> q;
	for (long long i = 1ll; i <= n; ++i)
	{
		cin >> a[i];
	}
	build(root, 1ll, n);
	for (long long i = 1ll; i <= q; ++i)
	{
		cin >> o;
		if (o == 1ll)
		{
			cin >> L >> R >> K;
			update(root, L, R, 1, K);
		}
		else if (o == 2ll)
		{
			cin >> L >> R >> K;
			update(root, L, R, K, 0);
		}
		else if (o == 3ll)
		{
			cin >> L >> R >> K;
			update(root, L, R, 0, K);
		}
		else if (o == 4ll)
		{
			cin >> L >> R;
			returnvalue qwe = query(root, L, R);
			long long poi = qwe.squans*(R - L + 1ll) % MODNUM - qwe.ans*qwe.ans % MODNUM;
			cout << ((poi < 0ll) ? (poi + MODNUM) : poi) << endl;
		}
	}
	return 0;
}

发表评论

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