Codeforces Round #622 (Div. 2) C2. Skyscrapers (hard version)(单调栈)

题目

n(n<=5e5)个数的数列，第i个数为ai(1<=ai<=1e9)

你需要构造一个新的序列b[]，使得bi<=ai，且b数列满足以下三个条件之一：

①非严格单增 ②非严格单减 ③开口向下的单峰数列(有最大值，其左侧非严格增，其右侧非严格减)

最大化b[]数组所有元素的和，输出最后构造的b数列，多解输出其一即可

题解

单调栈，开二维pair，代表（取的值，取该值的个数）

l[i]和r[i]分别记录当枚举i为最大值点时左侧及右侧的贡献(均含本身)，实时更新当前贡献和now

如果i左侧的值大于当前值a[i]，就将其弹栈，记录个数，同化成当前值，最后向栈中加入(当前值，当前个数）

a[i]被重复计数，所以以i为最大值轴的总元素和为l[i]+r[i]-a[i]，

取好轴之后，分别向两侧模拟还原即可

代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
typedef pair<int,int> P;
typedef long long ll;
#define fi first
#define se second
#define sci(x) scanf("%d",&(x))
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
int n,c,pos;
ll a[N],l[N],r[N],res[N],now,ans;
P stk[N];//(v,num)
bool upd(ll &x,ll y){
	if(x<y){
		x=y;
		return 1;
	}
	return 0;
}
int main(){
	sci(n);
	rep(i,1,n){
		scanf("%lld",&a[i]);
	}
	now=c=0;
	rep(i,1,n){
		int add=1;
		while(c && stk[c].fi>a[i]){
			add+=stk[c].se;
			now-=1ll*stk[c].se*stk[c].fi;
			c--;
		}
		now+=1ll*a[i]*add;
		stk[++c]=P(a[i],add);
		l[i]=now;
	}
	now=c=0;
	per(i,n,1){
		int add=1;
		while(c && stk[c].fi>a[i]){
			add+=stk[c].se;
			now-=1ll*stk[c].se*stk[c].fi;
			c--;
		}
		now+=1ll*a[i]*add;
		stk[++c]=P(a[i],add);
		r[i]=now;
	}
	rep(i,1,n){
		if(upd(ans,l[i]+r[i]-a[i])){
			pos=i;
		}
	}
	now=a[pos];
	rep(i,pos,n){
		now=min(now,a[i]);
		res[i]=now;
	}
	now=a[pos];
	per(i,pos,1){
		now=min(now,a[i]);
		res[i]=now;
	}
	rep(i,1,n){
		printf("%lld%c",res[i]," \n"[i==n]);
	}
	return 0;
}