自动搬运

查看原文

来自洛谷，原作者为

	浮尘ii **

搬运于2025-08-24 21:59:09，当前版本为作者最后更新于2019-03-19 17:31:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

注意到有贡献的一定是开始的一段乘法段，因为后面的段一定又有 + 又有 -。

设 $S_n=\prod_{i=1}^na_i$，于是答案就为

$$\sum_{i=1}^{n-1}S_i\times2\times3^{n-i-1}+S_n$$

组合意义即为枚举第一个连续的乘法段的最后一个数在哪里，那么下一个位置必须填 + 或 -，其余的随便填。

对于 $a_i$ 的单点修改，有一个显然的想法是对于 $S_i$ 的一段后缀做乘法，于是用线段树区间乘法，维护区间和即可。

但是以上的做法是错误的！

由于 $0$ 不存在逆元，而题目中说是非负整数没有保证不为 $0$，所以该做法可以被以下数据轻松卡掉：

1 1
0
1 1

但是由于该题数据比较水，所以可以通过。

正确的维护方法应该是：仍然是单点修改，在向上回溯的过程中维护区间积 $\rm mul$ 和答案 $\rm ans$。则

$$\begin{aligned}\rm mul&=\rm mul_{lc}\cdot mul_{rc}\\\rm ans&=\rm ans_{lc}+mul_{lc}\cdot ans_{rc}\end{aligned} $$

#include <cstdio>

typedef unsigned long long ull;
const int Mod = 1000000007;
const int maxN = 100005, maxL = 1 << 18 | 1;

int N, Q, A[maxN], Pow[maxN];

#define lc i << 1
#define rc i << 1 | 1
int Mul[maxL], Ans[maxL];
void build(int i, int l, int r)
{
	if (l == r)
	{
		Mul[i] = A[l];
		if (l == N)
			Ans[i] = A[l];
		else
			Ans[i] = A[l] * 2ULL * Pow[N - l - 1] % Mod;
		return;
	}
	int m = (l + r) >> 1;
	build(lc, l, m);
	build(rc, m + 1, r);
	Mul[i] = (ull)Mul[lc] * Mul[rc] % Mod;
	Ans[i] = ((ull)Mul[lc] * Ans[rc] + Ans[lc]) % Mod;
}
void modify(int i, int l, int r, int pos, int v)
{
	if (l == r)
	{
		A[l] = v;
		Mul[i] = A[l];
		if (l == N)
			Ans[i] = A[l];
		else
			Ans[i] = A[l] * 2ULL * Pow[N - l - 1] % Mod;
		return;
	}
	int m = (l + r) >> 1;
	if (pos <= m)
		modify(lc, l, m, pos, v);
	else
		modify(rc, m + 1, r, pos, v);
	Mul[i] = (ull)Mul[lc] * Mul[rc] % Mod;
	Ans[i] = ((ull)Mul[lc] * Ans[rc] + Ans[lc]) % Mod;
}
#undef lc
#undef rc

int main()
{
	scanf("%d%d", &N, &Q);
	for (int i = 1; i <= N; ++i)
		scanf("%d", A + i);
	Pow[0] = 1;
	for (int i = 1; i <= N; ++i)
		Pow[i] = 3U * Pow[i - 1] % Mod;

	build(1, 1, N);

	for (int t, v; Q--;)
	{
		scanf("%d%d", &t, &v);
		modify(1, 1, N, t, v);
		printf("%d\n", Ans[1]);
	}

	return 0;
}