AT_abc359_e [ABC359E] Water Tank

题目描述

给定一个长度为 $N$ 的正整数序列 $H=(H_1,H_2,\dotsc,H_N)$。

存在一个长度为 $N+1$ 的非负整数序列 $A=(A_0,A_1,\dotsc,A_N)$。初始时，$A_0=A_1=\dotsb=A_N=0$。

对 $A$ 重复执行以下操作：

1. 将 $A_0$ 的值增加 $1$。
2. 按顺序对 $i=1,2,\ldots,N$ 执行以下操作：
   • 如果 $A_{i-1}>A_i$ 且 $A_{i-1}>H_i$，则将 $A_{i-1}$ 的值减少 $1$，并将 $A_i$ 的值增加 $1$。

对于每个 $i=1,2,\ldots,N$，求首次满足 $A_i>0$ 时的操作次数。

输入格式

输入通过标准输入给出，格式如下：

$N$
$H_1$ $H_2$ $\dotsc$ $H_N$

输出格式

在一行中输出 $i=1,2,\ldots,N$ 对应的答案，以空格分隔。

样例 1

输入

5
3 1 4 1 5

输出

4 5 13 14 26

样例 2

输入

6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

输出

1000000001 2000000001 3000000001 4000000001 5000000001 6000000001

样例 3

输入

15
748 169 586 329 972 529 432 519 408 587 138 249 656 114 632

输出

749 918 1921 2250 4861 5390 5822 6428 6836 7796 7934 8294 10109 10223 11373

说明/提示

背景故事

有一个长长的水箱，内部等间距地放置了高度不同的隔板。高桥君想知道，当他从水箱的一端持续注水时，水首次到达每个隔板分隔的区域的具体时刻。

约束条件

• $1\leq N\leq2\times10^5$
• $1\leq H_i\leq10^9\ (1\leq i\leq N)$
• 输入均为整数

样例解释 #1

初始的 $5$ 次操作如下所示。每一行对应一次操作，最左侧为第 $1$ 步操作，其余为第 $2$ 步操作。

从图中可以看出，$A_1>0$ 首次成立是在第 $4$ 次操作后，$A_2>0$ 首次成立是在第 $5$ 次操作后。类似地，$A_3,A_4,A_5$ 对应的答案分别为 $13,14,26$。因此，输出 4 5 13 14 26。

样例解释 #2

请注意，输出的值可能超出 $32\operatorname{bit}$ 整数的范围。

翻译由 DeepSeek V3 完成