单调栈是指一个栈内部的元素具有严格单调性的一种数据结构，分为单调递增栈和单调递减栈。

Codeforces Round 622 (Div. 2) C. Skyscrapers

Link:Codeforces Round 622 (Div. 2) C. Skyscrapers

Description

The outskirts of the capital are being actively built up in Berland. The company "Kernel Panic" manages the construction of a residential complex of skyscrapers in New Berlskva. All skyscrapers are built along the highway. It is known that the company has already bought n plots along the highway and is preparing to build n skyscrapers, one skyscraper per plot.

Architects must consider several requirements when planning a skyscraper. Firstly, since the land on each plot has different properties, each skyscraper has a limit on the largest number of floors it can have. Secondly, according to the design code of the city, it is unacceptable for a skyscraper to simultaneously have higher skyscrapers both to the left and to the right of it.

Formally, let's number the plots from 1 to n. Then if the skyscraper on the i-th plot has floors, it must hold that is at most (). Also there mustn't be integers j and k such that and . Plots j and k are not required to be adjacent to i.

The company wants the total number of floors in the built skyscrapers to be as large as possible. Help it to choose the number of floors for each skyscraper in an optimal way, i.e. in such a way that all requirements are fulfilled, and among all such construction plans choose any plan with the maximum possible total number of floors.

Input
The first line contains a single integer n () — the number of plots.

The second line contains the integers () — the limit on the number of floors for every possible number of floors for a skyscraper on each plot.

Output
Print n integers — the number of floors in the plan for each skyscraper, such that all requirements are met, and the total number of floors in all skyscrapers is the maximum possible.

If there are multiple answers possible, print any of them.

Examples
input
5
1 2 3 2 1
output
1 2 3 2 1
input
3
10 6 8
output
10 6 6
Note
In the first example, you can build all skyscrapers with the highest possible height.

In the second test example, you cannot give the maximum height to all skyscrapers as this violates the design code restriction. The answer [10,6,6] is optimal. Note that the answer of [6,6,8] also satisfies all restrictions, but is not optimal.

Problem solving

这道题的意思就是给你一个序列，序列中每个值的初始值代表的就是这个数能达到的最大值，现在让你随意修改这些数（只要不超过最大值）。问你修改成什么样的情况可以使每个数的两边都没有大于它的数，并且序列和是最大的。
由题意我们可以知道最终的答案序列要么是单调递增的，要么是单调递减的，要么就是先单调递增，再单调递减。也就是说一定会存在一个极大值。我们只需要枚举极大值的位置，就可以得到答案了。
在c1里面，n只有1000，所以我们可以直接暴力枚举，计算当第i位看为是极大值时，此时达到的最大的序列和，更新使序列和最大的极大值的位置，最后输出即可，时间复杂度。
但是c2里面，我们显然是不可以暴力计算的。当然我们仍然可以采用c1的思路去写，不过当第i位看为最大值时，此时的序列和我们需要使用单调栈处理。
我们定义四个数组，pre和nxt分别代表第i位左右两边第一个小于它的数的位置。spre和snxt分别代表第i为看为最大值时，1-i和i-n的和。
所以现在只要我们计算出spre和snxt数组的值，就可以很快的按照c1的思路进行处理。
在计算spre得时候，我们遍历这个序列，每次使用单调栈得到左边第一个小于他的数，假如当前遍历到i，则spre[i]=spre[pre[i]]+(i-pre[i])*a[i],意思就是以第i位为极大值的时候左边的和，等于比i小的第一个数为极大值时左边的和加上从第一个比i小的数到i都变成a[i]之后的和。这里有中前缀和的感觉。
在计算snxt得时候，跟spre是差不多的就不说了。
至此我们就计算出了spre和snxt，所以这道题也就可以了。
单调栈挺好用的，下次一定会。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 10;
ll a[maxn], ans[maxn], pre[maxn], nxt[maxn], spre[maxn], snxt[maxn];
int main()
{
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    stack<ll> sta;
    spre[1] = a[1];
    sta.push(1);
    for (int i = 2; i <= n; i++) {
        while (!sta.empty() && a[sta.top()] >= a[i]) sta.pop();
        if (!sta.empty()) pre[i] = sta.top();//单调栈找出左边第一个小于a[i]的位置
        spre[i] = spre[pre[i]] + (i - pre[i]) * a[i];//计算spre
        sta.push(i);
    }
    while (!sta.empty()) sta.pop();
    for (int i = 1; i <= n; i++) nxt[i] = n + 1;//初始化nxt数组，上面因为pre数组初值本就是0所以不需要初始化。
    sta.push(n);
    snxt[n] = a[n];
    for (int i = n - 1; i >= 1; i--) {
        while (!sta.empty() && a[sta.top()] >= a[i]) sta.pop();
        if (!sta.empty()) nxt[i] = sta.top();//单调栈找出右边第一个小于a[i]的位置
        snxt[i] = snxt[nxt[i]] + (nxt[i] - i) * a[i];//计算snxt，类似于spre
        sta.push(i);
    }
    ll pos = 1, maxx = 0;
    for (int i = 1; i <= n; i++) {
        if (spre[i] + snxt[i] - a[i] > maxx) {
            maxx = spre[i] + snxt[i] - a[i];
            pos = i;//找到以pos为极值点的时候序列和最大
        }
    }
    ll cur = a[pos]; ans[pos] = a[pos];
    for (int i = pos + 1; i <= n; i++) {
        cur = min(cur, a[i]);
        ans[i] = cur;
    }
    cur = a[pos];
    for (int i = pos - 1; i >= 1; i--) {
        cur = min(cur, a[i]);
        ans[i] = cur;
    }//通过a[pos]为极值点，左右两边确定每个数的取值
    for (int i = 1; i <= n; i++) cout << ans[i] << " ";

    return 0;
}
赏