Solution to 情景剧。

A. 情景剧

https://www.becoder.com.cn/contest/4273/problem/1

给定序列，求任取一段区间，区间最大值、区间最小值、区间长度之积的最大值。

\(N\le 2\times 10^6\)，值域为 \(10^9\)。

对于 \(a_i\)，假设它是 \([X_i, Y_i]\) 内的最大值，且 \([X_i, Y_i]\) 是该条件下的极大区间；

相似地，对于 \(a_j\)，假设它是 \([P_j, Q_j]\) 内的最小值，且 \([P_j, Q_j]\) 是该条件下的极大区间；

则对于 \(a_i\) 作为区间内最大值，\(a_j\) 作为区间内最小值的情况，满足该条件的区间为 \([\max(X_i, P_j), \min(Y_i, Q_j)]\)，答案为 \(k=a_i \times a_j \times [\min(Y_i, Q_j) - \max(X_i, P_j) + 1]\)。我们的目标就是最大化 \(k\)。

两个不固定的值，并且不能拆给斜优做，所以考虑将其中一个变得「固定」。

观察数组，我们发现，对于数组中的最大值 \(a_m\)，有 \(X_m = 1,Y_m=n\)。那么此时选取 \(a_m\) 作为区间最大值，选取任意数 \(a_j\) 作为最小值。这样做可以保证由 \(i\) 带来的影响都是最优的，只用枚举 \(j\) 并求解即可。此时的答案就是 \(a_m\times a_j\times (Q_j-P_j + 1)\)。

我们上述条件成立的前提是 \(i\) 在 \([P_j, Q_j]\) 内且 \(j\) 在 \([X_i, Y_i]\) 内。当 \(i\) 取 \(m\) 时后者显然成立，但很容易构造出来情况让前者不成立。比如说 15 1 5，当 \(j=3\) 时就会得到错误的答案。

受刚才的思考启发，取 \([P_j, Q_j]\) 内的最大值作为 \(i\)。此时有 \(X_i\le P_j\le Q_j \le Y_j\)，答案为区间内最优。

接下来需要求解 \(P_j\) 和 \(Q_j\)。观察数据范围，应该是 \(\mathcal O(n)\) 做法。不难想到单调栈，可惜我不会，所以采用同样是 \(\mathcal O(n)\) 的悬线法（我的博客：有关悬线法的介绍）。

那么怎么求 \([P_j,Q_j]\) 内的最大值呢？当遇到这种求解区间与左右端点一致，并且待求满足可加性的情况时，我们可以在悬线的时候一起求解。当悬线跨越一个区间时，我们直接用这个已求解区间的最大值更新当前求的最大值。

左右分别求最大值（注意要用两个数组分别记录，防止错误更新），最后取两者较大作为最终区间内最大值即可。

最终时间复杂度 \(\mathcal O(n)\)。

说起来这是我头一次用悬线解决不在矩阵上，还要维护信息的题，之前并没有细想过单调栈和悬线可维护的信息差异，这次算是误打误撞做对了。

注意到数据范围，应该要开 __int128 吧。

#define int __int128
namespace XSC062 {
using namespace fastIO;
const int maxn = 2e6 + 5;
int a[maxn];
int n, mx, res;
int l[maxn], r[maxn];
int mxl[maxn], mxr[maxn];
int max(int x, int y) { return x > y ? x : y; }
int main() {
	read(n), l[0] = 1;
	for (int i = 1; i <= n; ++i) {
		read(a[i]), l[i] = i;
		mxl[i] = mxr[i] = a[i];
		while (l[i] > 1 && a[l[i] - 1] >= a[i]) {
			mxl[i] = max(mxl[i], mxl[l[i] - 1]);
			l[i] = l[l[i] - 1];
		}
	}
	r[n + 1] = n;
	for (int i = n; i; --i) {
		r[i] = i;
		while (r[i] < n && a[r[i] + 1] >= a[i]) {
			mxr[i] = max(mxr[i], mxr[r[i] + 1]);
			r[i] = r[r[i] + 1];
		}
		res = max(res, max(mxl[i], mxr[i]) * a[i] * (r[i] - l[i] + 1));
	}
	print(res, '\n');
	return 0;
}
} // namespace XSC062
#undef int

upd on 240704

我们在 这篇博客 中提到了悬线的本质是笛卡尔树，而本题就是其链上爬山维护数据的一个优秀体现，也是因为这一点，应该更加深切地认识到悬线包含式的访问顺序使之维护的数据类型应和倍增 / 树状数组等类似。

所以说到可维护数据的复杂程度，笛卡尔树严格大于悬线严格大于单调栈好吧 😎

虽然现在全世界都知道我是悬线魔怔人了 😎