← 返回题目列表

Codeforces · 1476/D

D. 旅程

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

有 $$$n + 1$$$ 个城市,编号从 $$$0$$$ 到 $$$n$$$。 $$$n$$$ 道路连接这些城市,第 $$$i$$$ 条道路连接城市 $$$i - 1$$$ 和 $$$i$$$ ($$$i \in [1, n]$$$)。

每条路都有一个方向。方向由 $$$n$$$ 字符组成的字符串给出,每个字符要么是 L 要么是 R。如果第 $$$i$$$ 个字符是 L,则意味着第 $$$i$$$ 条路最初从城市 $$$i$$$ 到城市 $$$i - 1$$$;否则,它将从城市 $$$i - 1$$$ 前往城市 $$$i$$$。

旅行者想要访问这个国家尽可能多的城市。最初,他们会选择某个城市作为旅程的起点。每天,旅行者必须从当前所在的城市出发,使用其中一条道路前往邻近的城市,并且只有当这条道路的方向与他们要去的方向相同时,他们才能沿着这条路走;我。例如,如果一条道路从城市 $$$i$$$ 指向城市 $$$i + 1$$$,则可以从 $$$i$$$ 行驶至 $$$i + 1$$$,但不能从 $$$i + 1$$$ 行驶至 $$$i$$$。当旅行者移动到邻近城市后,所有道路的方向都会改变为相反的方向。如果旅行者无法从当前城市前往邻近城市,则旅程结束;旅行者也可以随时结束旅程。

旅行者的目标是访问尽可能多的不同城市(他们可以多次访问一个城市,但只计算第一次访问)。对于每个城市 $$$i$$$,计算旅行者在一次旅程中可以访问的不同城市的最大数量(如果他们从城市 $$$i$$$ 出发)。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由两行组成。第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$)。第二行包含字符串 $$$s$$$,由 $$$n$$$ 个字符组成,每个字符要么是 L 要么是 R。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印 $$$n + 1$$$ 整数。如果该旅程从第 $$$i$$$ 个城市开始,则第 $$$i$$$ 个整数应等于旅行者在一次旅程中可以访问的不同城市的最大数量。

示例

输入 #1

2
6
LRRRLL
3
LRL

输出 #1

1 3 2 3 1 3 2
1 4 1 4