分数: 500 点
问题陈述
给你一个整数 N 和一个字符串 S 长度 N-1 组成 L 和 R.
考虑将整数写入 N 单元格排列成一行,以满足以下条件:
- 每个单元格上都写有一个整数。
- 每个整数 1,2,\dots,N 恰好出现在一个单元格中。
- 当 i- 第一个字符 S is
L, i+1 写在左侧 i. - 当 i- 第一个字符 S is
R, i+1 写在右侧 i.
让 C_i 是可以写入的整数个数 i左侧第一个单元格。 查找 C_1,C_2,\dots,C_N.
你被给予 T 测试用例;为他们每个人找到答案。
约束
- 1 \le T \le 20000
- 2 \le N \le 3 \times 10^5
- S 是一个长度为 N-1 组成
L和R. - 对于单个输入,总和 N 不超过 3 \times 10^5.
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N S
输出
打印 T 行。
的 i- 第行应包含以下问题的答案 i-第一个测试用例,格式如下:
C_1 C_2 \dots C_N
示例输入 1
5 5 RLLR 3 RL 2 L 3 RR 20 RLLLLLLLLRLRRLLLRLR
示例输出 1
2 4 3 4 2 2 2 1 1 1 1 1 1 5 9 13 14 15 17 18 19 19 20 20 19 19 18 17 16 14 12 9 5
此输入包含五个测试用例。
- 对于第一个测试用例,有 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- 从左边起第一个单元格是 1,3,4,5,这是四个整数。
- 可以写入的整数 3- 从左边起第一个单元格是 1,3,5,这是三个整数。
- 可以写入的整数 4从左边算起第一个单元格是 1,2,3,5,这是四个整数。
- 可以写入的整数 5从左边算起第一个单元格是 2,5,这是两个整数。
- 对于第二个测试用例,有两种可能的方法来填充单元格,如下所示:
- (1,3,2)
- (3,1,2)
- 对于第三个测试用例,有一种可能的方法来填充单元格,如下所示:
- (2,1)
- 对于第四个测试用例,有一种可能的方法来填充单元格,如下所示:
- (1,2,3)