自动搬运

查看原文

来自洛谷，原作者为

	伟大的王夫子 hanser忠实粉丝，爱好ACG、古风

搬运于2025-08-24 22:15:09，当前版本为作者最后更新于2021-02-20 16:50:17，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

线段树题一遍就A了，写偏题解纪念一下

首先，假设$ans,mul$分别是区间的答案，以及所有$X$值的乘积

那么容易得出转移方程 首先， $\max\limits_{l \le i \le r}{(\prod_{i=l}^r Y_i})\times X_i =\max(\max\limits_{l \le i \le mid}{(\prod_{i=l}^r Y_i})\times X_i,\max\limits_{mid +1\le i \le r}{(\prod_{i=l}^r Y_i})\times X_i)$

而$\max\limits_{mid \le i \le r}{(\prod_{i=l}^r Y_i})\times X_i) =\max\limits_{mid +1\le i \le r}{(\prod_{i=mid+1}^r Y_i})\times X_i \times \prod_{i=l}^{mid} X_i$

那么转移就很好转移了

由于结果过大，而且取了模会影响比大小，所以我们取对数，乘法变为加法。

询问便直接返回根节点的值

这样写法比许多人写的维护一堆值方便的多，而且代码简洁易懂，目前最优解。

总之，这道题说白了就是道线段树模板题，一定要好好掌握

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N = 5e5 + 5; 
int n, m;
ll X[N], Y[N];

const ll P = 1e9 + 7;
struct {
	int l, r;
	db sum, mx;
	ll mul, ans;
} t[N << 2];
inline void push_up(int p) {
	t[p].sum = t[p << 1].sum + t[p << 1 | 1].sum;
	t[p].mx = max(t[p << 1].mx, t[p << 1].sum + t[p << 1 | 1].mx);
	t[p].mul = t[p << 1].mul * t[p << 1 | 1].mul % P;
	if (t[p << 1].mx >= t[p << 1].sum + t[p << 1 | 1].mx) 
		t[p].ans = t[p << 1].ans;
	else t[p].ans = t[p << 1 | 1].ans * t[p << 1].mul % P; 
}
void build(int p, int l, int r) {
	t[p].l = l, t[p].r = r;
	if (l == r) {
		t[p].mx = log(1.0 * X[l] * Y[l]);
		t[p].sum = log(1.0 * X[l]);
		t[p].ans = X[l] % P * Y[l] % P;
		t[p].mul = X[l] % P;
		return; 
	}
	int mid = (l + r) >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
	push_up(p); 
}
void change(int p, int x) {
	if (t[p].l == t[p].r) {
		t[p].mx = log(1.0 * X[x] * Y[x]);
		t[p].sum = log(1.0 * X[x]);
		t[p].ans = X[x] % P * Y[x] % P;
		t[p].mul = X[x] % P; 
		return;
	}
	int mid = (t[p].l + t[p].r) >> 1;
	if (x <= mid) change(p << 1, x);
	else change(p << 1 | 1, x);
	push_up(p);
}
main() {
	cin >> n;
	for (register int i = 1; i <= n; ++i) scanf("%lld", X + i);
	for (register int i = 1; i <= n; ++i) scanf("%lld", Y + i);
	build(1, 1, n);
	printf("%lld\n", t[1].ans);
	cin >> m;
	while (m--) {
		int type, pos;
		ll val;
		scanf("%d%d%lld", &type, &pos, &val);
		if (type == 1) X[pos + 1] = val;
		else Y[pos + 1] = val;
		change(1, pos + 1);
		printf("%lld\n", t[1].ans); 
	}
}