40 st表 TLE 求剪枝

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int a[N], st[20][N], lg[N];
int n;
void init() {
    lg[1] = 0;
    for (int i = 2; i <= N; i++) lg[i] = lg[i / 2] + 1;
    for (int i = 1; i <= n; i++) st[0][i] = a[i];
    for (int k = 1; (1 << k) <= n; k++) {
        for (int i = 1; i + (1 << k) - 1 <= n; i++) {
            st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
        }
    }
}
int RMQ(int l, int r) {
    int k = lg[r - l + 1];
    return min(st[k][l], st[k][r - (1 << k) + 1]);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    init();
    int maxx = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            int minn = RMQ(i, j);
            maxx = max((j - i + 1) * minn ,maxx);
        }
    }
    cout << maxx;
    return 0;
}