Skyscrapers (hard version)（1900/单调栈）

题目：http://codeforces.com/contest/1313/problem/C2 参考：http://codeforces.com/blog/entry/74146 题意：给定n个数 a i a_i ai​，要求构造一个序列 b i b_i bi​，使得 b i < = a i b_i= a[i]) { st.pop(); } if(st.empty()) r[i] = 1LL*(n-i+1)*a[i]; else r[i] = r[st.top()]+1LL*(st.top()-i)*a[i]; st.push(i); } int pos = 1; ll res = l[1]+r[1]-a[1]; for(int i = 2;i res) { res = l[i]+r[i]-a[i]; pos = i; } } for(int i = pos-1;i >= 1;i--) a[i] = min(a[i],a[i+1]); for(int i = pos+1;i