CF1722D Line

有 $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 翻译