P4352 [CERC2015] Greenhouse Growth

你正在从计算机科学转向农业，你的新工作涉及在地下温室中种植向日葵。温室中有 n 株向日葵，按从左到右的顺序排列并编号为 1 到 n。两盏灯为向日葵提供生长所需的光和热：灯 A 位于左端，而灯 B 位于右端。 每天，只有一盏灯亮着，导致所有向日葵都朝向光源，并且其中一些会生长。向日葵只有在其正前方（朝向光源）的向日葵比它高时才会生长。生长是连续的，速率为每天正好 1 厘米。注意，当一株向日葵开始生长时，它可能会立即导致其正后方的向日葵开始生长。 你被给定了向日葵的初始高度和接下来 m 天的灯光计划，找出所有向日葵的最终高度。

第一行包含两个整数 n 和 m (1≤n, m≤300000)——向日葵的数量和周期内的天数。接下来的一行包含 n 个整数 h1, h2, ..., hn (1≤ hk ≤$10^9$)——从左到右的向日葵的初始高度（以厘米为单位）。 接下来的一行包含一个由恰好 m 个字符 A 或 B 组成的字符串——从周期的第一天开始的灯光计划。

输出一行包含 n 个整数——从左到右的向日葵的最终高度。

Central Europe Regional Contest 2015 Problem G。 题面翻译由 ChatGPT-4o 提供。