題目傳送門

題解

分析

分類討論。

記第 $i$ 個答案為 $an{s}_i+1$。

1. 第 $i$ 個數就是目前的最大值。
   顯然，$an{s}_i=h_i\times i$。
2. 第 $i$ 個數就是目前的最大值。
   記 $las{t}_i$ 為 $i$ 前面，從后往前數第一個比 $h_i$ 大的 $j$。
   所以，填滿第 $las{t}_i$ 個前面的答案為 $an{s}_j$。
   而第 $las{t}_i+1$ 至 $i?1$，顯然要用 $[(i?1)?(las{t}_i+1)+1]\times h_i=(i?las{t}_i?1)\times h_i$ 個格子才能填滿。
   所以，這時的 $an{s}_i=(i?las{t}_i?1)\times h_i$。

最后的答案輸出： $an{s}_i+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]);elselast[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;
}