/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
整数 N と長さ N-1 の L, R からなる文字列 S が与えられます。
横一列に並んだ N 個のマス目に、以下の条件を全て満たすように整数を書き込むことを考えます。
- 全てのマスに整数が 1 つ書かれている。
- 整数 1,2,\dots,N が書かれているマスが 1 つずつ存在する。
- S の i 文字目 が
Lであるとき、 i+1 は i より左に書き込まれている。 - S の i 文字目 が
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
この入力には 5 個のテストケースが含まれます。
- 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 番目のテストケースにおいて、マス目の埋め方として考えられるものは以下の 2 通りです。
- (1,3,2)
- (3,1,2)
- 3 番目のテストケースにおいて、マス目の埋め方として考えられるものは以下の 1 通りです。
- (2,1)
- 4 番目のテストケースにおいて、マス目の埋め方として考えられるものは以下の 1 通りです。
- (1,2,3)
Score : 500 points
Problem Statement
You are given an integer N and a string S of length N-1 consisting of L and R.
Consider writing integers into N cells arranged in a row so that the following conditions are satisfied:
- Every cell has one integer written on it.
- Every integer 1,2,\dots,N appears in exactly one cell.
- When the i-th character of S is
L, i+1 is written to the left of i. - When the i-th character of S is
R, i+1 is written to the right of i.
Let C_i be the number of integers that can be written in the i-th cell from the left. Find C_1,C_2,\dots,C_N.
You are given T test cases; find the answer for each of them.
Constraints
- 1 \le T \le 20000
- 2 \le N \le 3 \times 10^5
- S is a string of length N-1 consisting of
LandR. - For a single input, the sum of N does not exceed 3 \times 10^5.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N S
Output
Print T lines.
The i-th line should contain the answer for the i-th test case in the following format:
C_1 C_2 \dots C_N
Sample Input 1
5 5 RLLR 3 RL 2 L 3 RR 20 RLLLLLLLLRLRRLLLRLR
Sample Output 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
This input contains five test cases.
- For the first test case, there are 11 possible ways to fill the cells as follows:
- (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)
- From this, each value of C_i is determined as follows:
- The integers that can be written in the 1-st cell from the left are 1,4, which is two integers.
- The integers that can be written in the 2-nd cell from the left are 1,3,4,5, which is four integers.
- The integers that can be written in the 3-rd cell from the left are 1,3,5, which is three integers.
- The integers that can be written in the 4-th cell from the left are 1,2,3,5, which is four integers.
- The integers that can be written in the 5-th cell from the left are 2,5, which is two integers.
- For the second test case, there are two possible ways to fill the cells as follows:
- (1,3,2)
- (3,1,2)
- For the third test case, there is one possible way to fill the cells as follows:
- (2,1)
- For the fourth test case, there is one possible way to fill the cells as follows:
- (1,2,3)