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

输入 #1

5
3 1 4 1 5

输出 #1

4 5 13 14 26

输入输出样例 #2

输入 #2

6
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

输出 #2

1000000001 2000000001 3000000001 4000000001 5000000001 6000000001

输入输出样例 #3

输入 #3

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

输出 #3

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 完成