题目传送门
题解
分析
分类讨论。
记第 i i i 个答案为 a n s i + 1 ans_i+1 ansi+1。
- 第
i
i
i 个数就是目前的最大值。
显然, a n s i = h i × i ans_i=h_i \times i ansi=hi×i。 - 第
i
i
i 个数就是目前的最大值。
记 l a s t i last_i lasti 为 i i i 前面,从后往前数第一个比 h i h_i hi 大的 j j j。
所以,填满第 l a s t i last_i lasti 个前面的答案为 a n s j ans_j ansj。
而第 l a s t i + 1 last_i+1 lasti+1 至 i − 1 i-1 i−1,显然要用 [ ( i − 1 ) − ( l a s t i + 1 ) + 1 ] × h i = ( i − l a s t i − 1 ) × h i [(i - 1) - (last_i + 1) + 1] \times h_i=(i-last_i-1) \times h_i [(i−1)−(lasti+1)+1]×hi=(i−lasti−1)×hi 个格子才能填满。
所以,这时的 a n s i = ( i − l a s t i − 1 ) × h i ans_i=(i-last_i-1) \times h_i ansi=(i−lasti−1)×hi。
最后的答案输出: a n s i + 1 ans_i+1 ansi+1。
完成!
Code
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N = 2e5 + 10;
int n,a[N],maxn[N],ans[N],last[N];
int F(int x,int y)
{
if(a[x] >= y) return x;
if(x == last[x]) return x;
return F(last[x],y);
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin >> n;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
maxn[i] = max(maxn[i - 1],a[i]);
if(a[i] == maxn[i])
last[i] = i;
else if(a[i] > a[i - 1])
last[i] = F(i - 1,a[i]);
else
last[i] = i - 1;
}
for(int i = 1;i <= n;i++)
{
if(a[i] == maxn[i])
{
cout << ((ans[i] = a[i] * i) + 1) << " ";
}
else
{
ans[i] = ans[last[i]] + a[i] * (i - last[i]);
cout << ans[i] + 1 << " ";
}
}
return 0;
}