CodeForces - 1313C2 Skyscrapers (hard version) 單調棧

CodeForces - 1313C2 Skyscrapers (hard version)

原題位址：

http://codeforces.com/contest/1313/problem/C2

題意：

給出每個位置能設定的大小的上限，要你給每個位置設定實際大小滿足 j < i < k 并且 aj > ai < ak （ j 和 k 不要求和 i 相鄰）。

也就是說找到一個中心點，滿足這個點左邊非遞減，右邊非遞增的來構造每一個點的實際大小，使它們的和最大。

基本思路：

單調棧先從左邊維護在每個位置 i 時維持區間 [ 1 - i ] 非遞減所能得到的最大值記錄在 l [i] 中；同理從右邊維護區間 [ N - i ] 非遞減能得到的最大值記錄在 r [i] 中 。

那麼位置 i 作為中心點時所能得到的實際和就為 r[i] + l [i] - a[i] ，取最大值所在的位置為中心，按照條件往兩邊構造答案就可以了。

參考代碼：

#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define INF 0x3f3f3f3f

const int maxn = 5e5+10;
int n,a[maxn],l[maxn],r[maxn],res[maxn];
signed main() {
    IO;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<int> q;
    q.push_back(0);
    for (int i = 1; i <= n; i++) {
        while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();
        int t = q.back();
        l[i] = l[t] + a[i] * (i - t);
        q.push_back(i);
    }
    q.clear();
    q.push_back(n+1);
    for (int i = n; i >= 1; i--) {
        while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();
        int t = q.back();
        r[i] = r[t] + a[i] * (t - i);
        q.push_back(i);
    }
    int ans = 0, pos = 0;
    for (int i = 1; i <= n; i++) {
        int temp = l[i] + r[i] - a[i];
        if (temp > ans) {
            ans = temp, pos = i;
        }
    }
    res[pos] = a[pos];
    for (int i = pos - 1; i >= 1; i--) res[i] = min(a[i], res[i + 1]);
    for (int i = pos + 1; i <= n; i++) res[i] = min(a[i], res[i - 1]);
    for (int i = 1; i <= n; i++) cout << res[i] << " ";
    cout << endl;
    return 0;
}