AT_abc430_f.[ABC430F] Back and Forth Filling

给定一个整数 $N$，以及一个由 $N-1$ 个 L 和 R 组成的字符串 $S$。

请考虑将整数写入 $N$ 个按一排排列的格子，满足以下条件：

• 每个格子上写一个整数。
• 每个整数 $1,2,\dots,N$ 恰好出现一次。
• 当 $S$ 的第 $i$ 个字符为 L 时，$i+1$ 被写在 $i$ 的左边。
• 当 $S$ 的第 $i$ 个字符为 R 时，$i+1$ 被写在 $i$ 的右边。

记 $C_i$ 为可以写在从左往右第 $i$ 个格子的整数的数量。求 $C_1,C_2,\dots,C_N$。

有 $T$ 组测试数据，请你对每组数据输出答案。

输入从标准输入读入，格式如下：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每一组测试数据包含一行：

$N$ $S$

输出共 $T$ 行。

第 $i$ 行输出第 $i$ 组测试数据的答案，格式为：

$C_1$ $C_2$ $\dots$ $C_N$

样例解释 1

本输入包含五组测试数据。

• 第一组数据，共有 $11$ 种填法，具体如下：
  • $(1,4,3,2,5)$
  • $(1,4,3,5,2)$
  • $(1,4,5,3,2)$
  • $(4,1,3,2,5)$
  • $(4,1,3,5,2)$
  • $(4,1,5,3,2)$
  • $(4,3,1,2,5)$
  • $(4,3,1,5,2)$
  • $(4,3,5,1,2)$
  • $(4,5,1,3,2)$
  • $(4,5,3,1,2)$
• 由此可得每个 $C_i$ 的值如下：
  • 第 $1$ 个格子可以放 $1,4$，共 $2$ 个整数。
  • 第 $2$ 个格子可以放 $1,3,4,5$，共 $4$ 个整数。
  • 第 $3$ 个格子可以放 $1,3,5$，共 $3$ 个整数。
  • 第 $4$ 个格子可以放 $1,2,3,5$，共 $4$ 个整数。
  • 第 $5$ 个格子可以放 $2,5$，共 $2$ 个整数。
• 第二组数据，共有 2 种填法如下：
  • $(1,3,2)$
  • $(3,1,2)$
• 第三组数据，只有 1 种填法 $(2,1)$。
• 第四组数据，只有 1 种填法 $(1,2,3)$。

数据范围

• $1 \le T \le 20000$
• $2 \le N \le 3 \times 10^5$
• $S$ 是长度为 $N-1$、只包含字符 L 和 R 的字符串。
• 对于所有测试数据，所有 $N$ 的总和不超过 $3 \times 10^5$。

由 ChatGPT 5 翻译