← 返回题目列表

AtCoder · abc407_f

I. 滑动窗口最大值之和

中文机器翻译题面 查看原题

分数: 550 点

问题陈述

给你一个非负整数序列 A = (A_1,\dots,A_N) 长度 N.

对于每个 k = 1,\dots,N,解决以下问题:

  • A 有 正面写有 N-k+1 (连续)长度子数组 k。取其中每个最大值,并输出这些最大值的总和。

约束

  • 1 \le N \le 2 \times 10^{5}
  • 0 \le A_i \le 10^{7} (1 \le i \le N)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N

输出

输出 N 行。的 i- 第行 (1 \le i \le N) 应包含以下问题的答案 k = i.


示例输入 1

4
5 3 4 2

示例输出 1

14
13
9
5

对于 k = 1,有四个长度的子数组 k=1:

  • (5),其最大值为 5;
  • (3),其最大值为 3;
  • (4),其最大值为 4;
  • (2),其最大值为 2.

总和是 5 + 3 + 4 + 2 = 14.

对于 k = 2,有三个长度的子数组 k=2:

  • (5,3),其最大值为 5;
  • (3,4),其最大值为 4;
  • (4,2),其最大值为 4.

总和是 5 + 4 + 4 = 13.

对于 k = 3,有两个长度为的子数组 k=3:

  • (5,3,4),其最大值为 5;
  • (3,4,2),其最大值为 4.

总和是 5 + 4 = 9.

对于 k = 4,有一个长度为 1 的子数组 k=4:

  • (5,3,4,2),其最大值为 5.

总和是 5.


示例输入 2

8
2 0 2 5 0 5 2 4

示例输出 2

20
28
27
25
20
15
10
5

示例输入 3

11
9203973 9141294 9444773 9292472 5507634 9599162 497764 430010 4152216 3574307 430010

示例输出 3

61273615
68960818
69588453
65590626
61592799
57594972
47995810
38396648
28797486
19198324
9599162