P2422 良好的感觉 题解

· · 题解

另一种不一样的解法，ST 表套二分。

首先，枚举最小值 a_i。

那么最优方案一定是两边一直用比 a_i 大的数。

由于数组是静态的，可以使用 ST 表维护区间最小值。

然后在数组上二分，找到最左边的值和最右边的值，前缀和计算答案即可。

时间复杂度虽然不如单调队列，但是过 10^5 还是没有问题的。

时空复杂度均为 \mathcal{O(n\log n)}。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 100010; int dp[N][20], a[N], lg[N], n, sum[N];
void RMQ() {
    for(int i = 1; i <= n; i++) dp[i][0] = a[i];
    for(int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for(int i = 1; i < 20; i++)
        for(int j = 1; j + (1 << i) <= n + 1; j++)
            dp[j][i] = min(dp[j][i - 1], dp[j + (1 << i - 1)][i - 1]);
}
int ask(int l, int r) {int k = lg[r - l + 1]; return min(dp[l][k], dp[r - (1 << k) + 1][k]);}
signed main() {
    cin >> n; for(int i = 1; i <= n; i++) scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i]; RMQ(); int mx = 0;
    for(int i = 1; i <= n; i++) {
        int l = 1, r = i - 1, L = i;
        while(l <= r) {
            int mid = l + r >> 1;
            if(ask(mid, i) == a[i]) L = mid, r = mid - 1;
            else l = mid + 1;
        }
        l = i + 1, r = n; int R = i;
        while(l <= r) {
            int mid = l + r >> 1;
            if(ask(i, mid) == a[i]) R = mid, l = mid + 1;
            else r = mid - 1;
        }
        mx = max(mx, a[i] * (sum[R] - sum[L - 1]));
    }
    cout << mx;
    return 0;
}