【原题】
This is a harder version of the problem. In this version n≤500000n≤500000
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 nn plots along the highway and is preparing to build nn 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 11 to nn. Then if the skyscraper on the ii-th plot has aiai floors, it must hold that aiai is at most mimi (1≤ai≤mi1≤ai≤mi). Also there mustn't be integers jj and kk such that j<i<kj<i<k and aj>ai<akaj>ai<ak. Plots jj and kk are not required to be adjacent to ii.
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.
The first line contains a single integer nn (1≤n≤5000001≤n≤500000) — the number of plots.
The second line contains the integers m1,m2,…,mnm1,m2,…,mn (1≤mi≤1091≤mi≤109) — the limit on the number of floors for every possible number of floors for a skyscraper on each plot.
Print nn integers aiai — 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
5
1 2 3 2 1
1 2 3 2 1
3
10 6 8
10 6 6
【思路】单调栈
1 #include <algorithm> 2 #include <cmath> 3 #include <cstdio> 4 #include <cstring> 5 #include <list> 6 #include <map> 7 #include <iostream> 8 #include <queue> 9 #include <set> 10 #include <stack> 11 #include <string> 12 #include <vector> 13 #include <iomanip> 14 #define LL long long 15 #define inf 0x3f3f3f3f 16 #define INF 0x3f3f3f3f3f3f 17 #define F first 18 #define S second 19 #define lson rt << 1 20 #define rson rt << 1 | 1 21 using namespace std; 22 23 const int maxn = 5e5 + 7; 24 int n; 25 LL a[maxn], l[maxn], r[maxn]; 26 27 int main() 28 { 29 ios::sync_with_stdio(false); 30 cin.tie(0); 31 cin >> n; 32 for (int i = 1; i <= n; i++) cin >> a[i]; 33 stack<pair<LL, LL>> s; 34 for (int i = 1; i <= n; i++) 35 { 36 l[i] = l[i - 1]; 37 LL len = 1; 38 while (!s.empty() && a[s.top().F] >= a[i]) 39 { 40 if (len == 1) 41 { 42 l[i] += (i - s.top().F + s.top().S - 1) * (a[s.top().F] - a[i]); 43 len = i - s.top().F + s.top().S; 44 } 45 else 46 { 47 l[i] += s.top().S * (a[s.top().F] - a[i]); 48 len += s.top().S; 49 } 50 s.pop(); 51 } 52 s.push({ i, len }); 53 } 54 while (!s.empty()) s.pop(); 55 for (int i = n; i >= 1; i--) 56 { 57 r[i] = r[i + 1]; 58 LL len = 1; 59 while (!s.empty() && a[s.top().F] >= a[i]) 60 { 61 if (len == 1) 62 { 63 r[i] += (s.top().F - i + s.top().S - 1) * (a[s.top().F] - a[i]); 64 len = s.top().F - i + s.top().S; 65 } 66 else 67 { 68 r[i] += s.top().S * (a[s.top().F] - a[i]); 69 len += s.top().S; 70 } 71 s.pop(); 72 } 73 s.push({i, len}); 74 } 75 LL ans = l[1] + r[1]; 76 int p = 1; 77 for (int i = 1; i <= n; i++) 78 { 79 if (l[i] + r[i] < ans) 80 { 81 ans = l[i] + r[i]; 82 p = i; 83 } 84 } 85 LL mn = a[p]; 86 for (int i = p; i >= 1; i--) 87 { 88 mn = min(a[i], mn); 89 if (a[i] > mn) a[i] = mn; 90 } 91 mn = a[p]; 92 for (int i = p; i <= n; i++) 93 { 94 mn = min(a[i], mn); 95 if (a[i] > mn) a[i] = mn; 96 } 97 for (int i = 1; i <= n; i++) cout << a[i] << " "; 98 }