← 返回题目列表

Codeforces · 1722/D

D. 线

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

水平线上有 $$$n$$$ 个人,每个人要么向左看,要么向右看。每个人都数着自己看向的方向有多少人。该行的值是每个人的计数之和。

例如,在 LRRLL 排列中,L 代表向左看的人,R 代表向右看的人,每个人的计数为 $$$[0, 3, 2, 3, 4]$$$,值为 $$$0+3+2+3+4=12$$$。

您将获得排队人员的初步排列。对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$k$$$,如果您可以改变最多 $$$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$$$ 以空格分隔的非负整数 - 如果您可以将每个 $$$k$$$ 的最多 $$$k$$$ 人的方向从 $$$1$$$ 更改为 $$$n$$$(含),则该线的最大值。

示例

输入 #1

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

输出 #1

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

注意

在第一个测试用例中:

- $$$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)。