cf 662c2

cf div2 c2

题目链接

自闭了

这个题题意: 给一个数组，让构造一个左边跟右边不能同时有大于这个数的（左边右边不一定是挨着的）、给出的数组是当前位置的最大值。构造出来的数组的和尽可能大
很明显 要么递增、要么递减、要么找个峰值左边递增，右边递减。
第一二种情况可以归为第三种情况。
比赛时候想到了遍历一遍想办法弄出左边递增的最大值跟右边递减的最大值
要找出i位置从1~i是递增的最大值，怎么找？ 比赛的时候想到了记录前一个比当前数小的数。然后再记录后一个比当前小的数。
设他前面比它小离他最近的这个数是x于是得到1到 i 位置上的最大值就是1~x的最大值加（i - x）* a[i]。
但是比赛的时候死活想不到单调栈这个东西 。。。。
于是最后十分钟想到了。。 然后脑子像短路了一样 啥都不会了
这就很简单了，，，，上代码吧

#include<stdio.h>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 5e5+5;
ll a[maxn];
int c[maxn];
int d[maxn];
ll s1[maxn];
ll s2[maxn];
vector<int> vv;
int main()
{
   
	int n;
	scanf("%d",&n);
	for (int i = 1; i <= n; i ++ )
	{
   
		scanf("%lld",&a[i]);
		d[i] = n + 1;
		c[i] = 0;
	}
	stack<int> ss;
	for (int i = n; i >= 1; i -- )
	{
   
			while(!ss.empty() && a[ss.top()] >= a[i])
			{
   
				int x = ss.top();
				ss.pop();
			}
		if(ss.empty())
			d[i] = n + 1;
		else
			d[i] = ss.top();
		ss.push(i);
	}
	while(!ss.empty())
	{
   
		ss.pop();
	}
	for (int i = 1; i <= n; i ++ )
	{
   
			while(!ss.empty() && a[ss.top()] > a[i])
			{
   
				int x = ss.top();
				ss.pop();
			}
			if(ss.empty())
				c[i] = 0;
			else
				c[i] = ss.top();
			ss.push(i);
	}
// for (int i = 1; i <= n; i ++ )
// {
   
// printf("%d ",d[i]);
// }
// printf("\n");
// for (int i = 1; i <= n; i ++ )
// {
   
// printf("%d ",c[i]);
// }
// printf("\n");
	s1[1] = a[1];
	for (int i = 2; i <= n; i ++ )
	{
   
		if(a[i] >= a[i - 1])
		{
   
			s1[i] = s1[i - 1] + a[i];
		}
		else
		{
   
			int x = c[i];
			s1[i] = s1[x] + (i - x) * a[i];
		}
	}
	
	s2[n] = a[n];
	for (int i = n - 1; i >= 1; i -- )
	{
   
		if(a[i] >= a[i + 1])
		{
   
			s2[i] = s2[i + 1] + a[i];
		}
		else
		{
   
			int x = d[i];
			s2[i] = s2[x] + (x - i) * a[i];
		}
	}
// for (int i= 1; i <= n; i ++ )
// {
   
// printf("%lld ",s1[i]);
// }
// printf("\n");
// for (int i= 1; i <= n; i ++ )
// {
   
// printf("%lld ",s2[i]);
// }
// printf("\n");
	ll ans =0 ;
	int k = 0;
	for (int i = 1; i <= n; i ++ )
	{
   
		if(ans < s1[i] + s2[i] - a[i])
		{
   
			ans = s1[i] + s2[i] - a[i];
			k = i;
// printf("%d %lld\n",i,ans);
		}
	}
// printf("%d %lld\n",k,ans);
	ll temp = a[k];
	for (int i = k - 1; i >= 1; i -- )
	{
   
		temp = min(temp,a[i]);
		vv.push_back(temp);
	}
	reverse(vv.begin(),vv.end());
	vv.push_back(a[k]);
	temp = a[k];
	for (int i = k + 1; i <= n; i ++ )
	{
   
		temp = min(temp,a[i]);
		vv.push_back(temp);
	}
	for (int i = 0; i < vv.size(); i ++ )
	{
   
		printf("%d ",vv[i]);
	}
	printf("\n");

}