题目描述

有 $n$ 个人站成一排，每个人要么朝左看，要么朝右看。每个人会数出自己所看方向上有多少人。整排的价值定义为所有人的计数之和。

例如，在排列 LRRLL 中，L 表示该人朝左看，R 表示该人朝右看，每个人的计数分别为 $[0, 3, 2, 3, 4]$，总价值为 $0+3+2+3+4=12$。

现在给定初始排列。对于每个 $k$，$1 \leq k \leq n$，你可以改变至多 $k$ 个人的朝向，求整排的最大价值。

输入格式

输入包含多组测试数据。第一行包含一个整数 $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）。

输出格式

对于每个测试用例，输出 $n$ 个用空格分隔的非负整数，第 $i$ 个数表示最多可以改变 $i$ 个人朝向时，整排的最大价值。

说明/提示

在第一个测试用例中：

• $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$ 个人的朝向。

在第二个测试用例中，最优策略是始终只改变第一个人的朝向，对于所有 $k=1$ 到 $5$，排列变为 RRRLL。

由 ChatGPT 4.1 翻译

样例

6
3
LLR
5
LRRLL
1
L
12
LRRRLLLRLLRL
10
LLLLLRRRRR
9
LRLRLRLRL

3 5 5 
16 16 16 16 16 
0 
86 95 98 101 102 102 102 102 102 102 102 102 
29 38 45 52 57 62 65 68 69 70 
44 50 54 56 56 56 56 56 56