CF2172J Sliding Tiles

你有一个特殊的滑动谜题，棋盘为 $n \times n$ 的方格。这种谜题与标准滑动谜题略有不同：每对相邻的两列之间，在底部有一根高度为 $h_i$（对于 $1 \leq i < n$）的竖直阻挡条。每个 $h_i$ 表示该阻挡条从底部向上延伸 $h_i$ 行，在这些行中阻挡两个列之间瓷砖的移动。 棋盘上有若干瓷砖，每个瓷砖恰好占据一个格子。这些瓷砖可以在棋盘上自由滑动，除非被棋盘边界、竖直阻挡条（取决于其高度）或其他瓷砖所阻挡。 该谜题允许两种类型的倾斜操作： - 向右倾斜：所有瓷砖尽可能向右滑动。 - 向下倾斜：所有瓷砖尽可能向下滑动。 在这两种操作中，所有瓷砖同时移动，只有当被棋盘边界、阻挡条或其他瓷砖阻挡时才会停止。  图 1：样例输入 1 的说明图。定义一个“组合操作”为：先将棋盘向右倾斜，再向下倾斜。 最初，第 $i$ 列从底部开始堆有 $a_i$ 个瓷砖。你恰好对棋盘执行一次组合操作。操作结束后，求每一列最终剩余的瓷砖数。

第一行包含一个整数 $n$，表示棋盘的大小。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，其中 $a_i$ 表示第 $i$ 列最初的瓷砖数量。 第三行包含 $n-1$ 个整数 $h_1,h_2,\ldots,h_{n-1}$，其中 $h_i$ 表示第 $i$ 列和第 $i+1$ 列之间的阻挡条高度。 - $2 \leq n \leq 5 \times 10^5$ - $0 \leq a_i \leq n$ - $0 \leq h_i \leq n-1$

输出一行 $n$ 个数字，表示恰好执行一次组合操作后每一列的瓷砖数量。

由 ChatGPT 5 翻译