rt

自己脑补了一个做法，但是 T 了

$i$ 枚举峰顶

find 函数：如果 $k=0$，处理峰顶左边的区间；否则处理右边

以处理左边为例：找到 $[l,r]$ 中最小的数 $x$，其下标为 $y$，那么 $[l,y]$ 的贡献可以直接算，然后递归处理 $[y+1,r]$

显然能被卡成 $O(n^2)$

但如果在随机数据下的复杂度大概是多少呢？ （ swap 在 c++11 下交换 vector 大概是 $O(1)$ 的）

#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5;
int n,id;
long long ans;
int m[N];
pair<int,int> st[N][25];
vector<pair<int,int> > color(N),a(N);

inline void RMQ(void)
{
	for(register int i=1;i<=n;++i)
		st[i][0]=make_pair(m[i],i);
	register int t=log2(n);
	for(register int j=1;j<=t;++j)
		for(register int i=1;i+(1<<j)-1<=n;++i)
			st[i][j]=min(st[i][j-1],st[i+(1<<j-1)][j-1]);
}

inline pair<int,int> query(int l,int r)
{
	register int t=log2(r-l+1);
	return min(st[l][t],st[r-(1<<t)+1][t]);
}

long long find(int id,int l,int r,bool k)
{
	if(l>r) return 0;
	pair<int,int> t=query(l,r);
	color[t.second]=make_pair(t.first,id);
	if(k) return 1ll*t.first*(r-t.second+1)+find(id,l,t.second-1,k);
	else return 1ll*t.first*(t.second-l+1)+find(id,t.second+1,r,k);
}

int main(void)
{
	scanf("%d",&n);
	for(register int i=1;i<=n;++i)
		scanf("%d",m+i);
	RMQ();
	for(register int i=1;i<=n;++i)
	{
		register long long res=find(i,1,i,0)+find(i,i,n,1)-m[i];
		if(res>ans)
		{
			ans=res,id=i;
			swap(a,color);
		}
	}
	for(register int i=id-1;i>=1;--i)
		if(a[i].second!=id||!a[i].first) a[i].first=a[i+1].first;
	for(register int i=id+1;i<=n;++i)
		if(a[i].second!=id||!a[i].first) a[i].first=a[i-1].first;
	for(register int i=1;i<=n;++i)
		printf("%d ",a[i].first);
	return 0;
}