长乐集训 Day 11

The twelfth day in Changle.
在长乐的第十二天
今天讲了状压DP和单调队列
又是啥都不会的一天
每日贴题
题目
代码如下：

#include 
using namespace std;
int n, a[101010], head = 1, tail = 0, v[101010], t[101010];
int main() {
    cin >> n;
    for (int i = 1; i > a[i];
    }
    v[1] = 0;
    for (int i = 2; i <= n; i++) {
        int h = i - 1;
        while (a[i]  0) h = v[h];
        v[i] = h;
    }
    t[n] = n + 1;
    for (int i = n - 1; i >= 1; i--) {
        int h = i + 1;
        while (a[i] <= a[h] && h <= n) h = t[h];
        t[i] = h;
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, 1LL * (t[i] - v[i] - 1) * a[i]);
    }
    cout << ans;
    return 0;
}

ps.无