CF1722D.Line

There are $n$ people in a horizontal line, each looking either to the left or the right. Each person counts the number of people in the direction they are looking. The value of the line is the sum of each person's count.

For example, in the arrangement LRRLL, where L stands for a person looking left and R stands for a person looking right, the counts for each person are $[0, 3, 2, 3, 4]$, and the value is $0+3+2+3+4=12$.

You are given the initial arrangement of people in the line. For each $k$ from $1$ to $n$, determine the maximum value of the line if you can change the direction of at most $k$ people.

水平线上有 $n$ 个人，每人朝左（L）或朝右（R）看。每个人统计其视线方向上的人数。该排列的“值”定义为所有人统计结果的总和。

例如，在排列 LRRLL 中（L 表示朝左看，R 表示朝右看），每个人的统计结果分别为 $[0, 3, 2, 3, 4]$，因此该排列的值为 $0+3+2+3+4=12$。

给定初始排列。对每个 $k = 1$ 到 $n$，求在最多改变 $k$ 个人朝向的前提下，该排列所能达到的最大值。

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 100$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1 \leq n \leq 2\cdot10^5$) — the length of the line.

The following line contains a string consisting of $n$ characters, each of which is either L or R, representing a person facing left or right, respectively — the description of the line.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.

Please note that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2\cdot10^5$），表示队列的长度。

接下来的一行包含一个由 $n$ 个字符组成的字符串，每个字符为 L 或 R，分别表示该位置的人面朝左或面朝右——即队列的描述。

保证所有测试用例的 $n$ 值之和不超过 $2\cdot10^5$。

请注意，某些测试用例的答案无法用 32 位整数类型表示，因此在编程语言中应至少使用 64 位整数类型（例如 C++ 中的 long long）。

For each test case, output $n$ space-separated non-negative integers — the maximum value of the line if you can change the direction of at most $k$ people for each $k$ from $1$ to $n$, inclusive.

对于每个测试用例，输出 $n$ 个以空格分隔的非负整数——即对每个从 $1$ 到 $n$（含）的 $k$，在最多改变 $k$ 个人朝向的前提下，该队列所能达到的最大值。

In the first test case:

• $k=1$: change the direction of $1$ person to make the line RLR. The total value is $2+1+0=3$.
• $k=2$: change the direction of $2$ people to make the line RLL. The total value is $2+1+2=5$.
• $k=3$: change the direction of $2$ people to make the line RLL. The total value is $2+1+2=5$. Note that you have to change the direction of at most $k$ people.

In the second test case, it is optimal to only change the direction of the first person for all $k$ from $1$ to $5$ (that is, make the line RRRLL).

在第一个测试用例中：

• $k=1$：改变 $1$ 个人的方向，使队列为 RLR。总价值为 $2+1+0=3$。
• $k=2$：改变 $2$ 个人的方向，使队列为 RLL。总价值为 $2+1+2=5$。
• $k=3$：改变 $2$ 个人的方向，使队列为 RLL。总价值为 $2+1+2=5$。注意，你最多只能改变 $k$ 个人的方向。

在第二个测试用例中，对所有从 $1$ 到 $5$ 的 $k$ 值，最优策略均为仅改变第一个人的方向（即构造队列 RRRLL）。