← 返回题目列表

AtCoder · abc430_f

I. 来回填充

中文机器翻译题面 查看原题

分数: 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)