ST表求条悬3关

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int LOG = 20;
int n;
int a[MAXN], sum[MAXN];
struct ST {
	int St[MAXN][LOG], t;
	int LOG2(int x) {
		return 31 - __builtin_clz(x);
	}
	void build() {
		t = LOG2(n);
		for (int i = 1; i <= n; i++) {
			St[i][0] = a[i];
		}
		for (int j = 1; j <= t; j++) {
			for (int i = 1; i + (1 << j) - 1 <= n; i++) {
				St[i][j] = min(St[i][j - 1], St[i + (1 << (j - 1))][j - 1]);
			}
		}
	}
	int query(int l, int r) {
		int k = LOG2(r - l  + 1);
		return min(St[l][k], St[r - (1 << k) + 1][k]);
	} 
}st;
signed main(){
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sum[i] = sum[i - 1] + a[i];
	}
	st.build();
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		int l = 1, r = i - 1, le = i;//左边界，le - i
		while (l <= r) {
			int mid = (l + r) / 2;
			if (st.query(mid, i) == a[i]) {
				r = mid - 1;
				le = mid;
			} else {
				l = mid + 1;
			}
		}
		l = i + 1, r = n;
		int ri = i;//右边界，i - ri
		while (l <= r) {
			int mid = (l + r) / 2;
			if (st.query(i, mid) == a[i]) {
				l = mid + 1;
				ri = mid;
			} else {
				r = mid - 1;
			}
		}
		ans = max(ans, st.query(le, ri) * (sum[ri] - sum[le - 1]));
	}
	cout << ans;
	return 0;
}