The Preliminary Contest for ICPC China Nanchang National Invitational I题 Max answer

Alice has a magic array. She suggests that the value of a interval is equal to the sum of the values in the interval, multiplied by the smallest value in the interval.

Now she is planning to find the max value of the intervals in her array. Can you help her?

Input
First line contains an integer n(1≤n≤5×10^5).

Second line contains nn integers represent the array a(−10^5≤ai≤10 ^5).
Output
One line contains an integer represent the answer of the array.
题意：定义一个区间的值为：一个区间的和*区间的最小值，然后求出最大值区间值
ans = max(sum(l,r)*min(l,r))

思路：使用单调栈维护以当前位置为最小值得左右边界。最后使用RMQ求出答案（时间复杂度O（n））
正解：使用单调栈（时间复杂度O(n)）然而不不会

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 5;
ll a[maxn];
ll L[maxn], R[maxn];
ll dp1[maxn][20];
ll dp2[maxn][20];
ll lg[maxn];
ll sum[maxn];
stack<int> s;

int Min(int x, int y) {
	if (sum[x] < sum[y]) {
		return x;
	}
	return y;
}

int Max(int x, int y) {
	if (sum[x] < sum[y]) {
		return y;
	}
	return x;
}

void RMQ(int n) {
	for (int j = 1; j <= lg[n]; j++) {
		for (int i = 1; i + (1 << j) - 1 <= n; i++) {
			dp1[i][j] = Min(dp1[i][j - 1], dp1[i + (1 << (j - 1))][j - 1]);
			dp2[i][j] = Max(dp2[i][j - 1], dp2[i + (1 << (j - 1))][j - 1]);
		}
	}
}
/* 10 0 2 5 -1 -6 -7 -3 0 9 -8 */
int main() {
	int n;
	scanf("%d", &n);
	lg[0] = -1;
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		sum[i] = sum[i - 1] + a[i];
		dp1[i][0] = dp2[i][0] = i;
		lg[i] = lg[i >> 1] + 1;
	}
	
	RMQ(n);
	a[n + 1] = -1e18;
	a[0] = -1e18; 
	for (int i = 1; i <= n + 1; i++) {
		while (!s.empty() && a[s.top()] > a[i]) {
			L[s.top()] = i - 1;
			s.pop();
		}
		s.push(i);
	}
	while (!s.empty()) {
		s.pop();
	}
	for (int i = n; i >= 0; i--) {
		while (!s.empty() && a[s.top()] > a[i]) {
			R[s.top()] = i + 1;
			s.pop();
		}
		s.push(i);
	}
	ll ans = -1e18;
	ll k1, k2, t1, t2;
	for (int i = 1; i <= n; i++) {
		if (a[i] < 0) {
			k1 = lg[i - R[i] + 1];
			k2 = lg[L[i] - i + 1];
			t1 = Max(dp2[R[i]][k1], dp2[i - (1 << k1) + 1][k1]) + 1;
			t2 = Min(dp1[i][k2], dp1[L[i] - (1 << k2) + 1][k2]);
			ans = max(ans, 1LL * (sum[t2] - sum[t1 - 1]) * a[i]);
		} else {
			k1 = lg[i - R[i] + 1];
			k2 = lg[L[i] - i + 1];
			t1 = Min(dp1[R[i]][k1], dp1[i - (1 << k1) + 1][k1]);
			t2 = Max(dp2[i][k2], dp2[L[i] - (1 << k2) + 1][k2]);
			ans = max(ans, 1LL * (sum[t2] - sum[t1 - 1]) * a[i]);
		}

	}
	printf("%lld\n", ans);
	return 0;
}