Journey

题意翻译

### 题目描述 有 $n$ 条道路连接着 $n + 1$ 座编号从 $0$ 到 $n$ 的城市，第 $i$ 条道路连接了编号为 $i - 1$ 和 $i$ 的城市，其中 $i\in[1,n]$。 每条道路都有初始方向，初始方向用一个字符串表示。如果第 $i$ 个字符为 $\texttt{L}$，则第 $i$ 条道路一开始从城市 $i$ 连向 $i - 1$；$\texttt R$ 则表示该道路一开始从城市 $i$ 连向 $i+1$。 一个旅行者会从某个城市开始旅行，每次旅行只能沿着道路的方向去到一个相邻的城市，**每走过一次道路之后所有道路的方向都会发生改变**。 对于每个城市，求旅行者从该城市出发最多能到达城市的数量（同一城市可以经过多次，但是只计算一次）。 ### 输入格式 第一行一个正整数 $t$ 表示数据组数。 每组数据有两行。第一行一个正整数 $n$，第二行一个长度为 $n$ 且只含字母 $\texttt L$ 和 $\texttt R$ 的字符串。 ### 输出格式 对于每组数据，输出一行 $n + 1$ 个整数，第 $i$ 个整数表示旅行者从编号为 $i - 1$ 的城市出发最多到达的城市个数。 ### 数据范围 $1\le t\le 1\times 10^4$，对于每组数据 $1\le n\le 3\times 10^5$，且同一测试点内有 $1\le \sum n\le 3\times 10^5$。

题目描述

There are $ n + 1 $ cities, numbered from $ 0 $ to $ n $ . $ n $ roads connect these cities, the $ i $ -th road connects cities $ i - 1 $ and $ i $ ( $ i \in [1, n] $ ). Each road has a direction. The directions are given by a string of $ n $ characters such that each character is either L or R. If the $ i $ -th character is L, it means that the $ i $ -th road initially goes from the city $ i $ to the city $ i - 1 $ ; otherwise it goes from the city $ i - 1 $ to the city $ i $ . A traveler would like to visit as many cities of this country as possible. Initially, they will choose some city to start their journey from. Each day, the traveler must go from the city where they currently are to a neighboring city using one of the roads, and they can go along a road only if it is directed in the same direction they are going; i. e., if a road is directed from city $ i $ to the city $ i + 1 $ , it is possible to travel from $ i $ to $ i + 1 $ , but not from $ i + 1 $ to $ i $ . After the traveler moves to a neighboring city, all roads change their directions to the opposite ones. If the traveler cannot go from their current city to a neighboring city, their journey ends; it is also possible to end the journey whenever the traveler wants to. The goal of the traveler is to visit as many different cities as possible (they can visit a city multiple times, but only the first visit is counted). For each city $ i $ , calculate the maximum number of different cities the traveler can visit during exactly one journey if they start in the city $ i $ .

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. Each test case consists of two lines. The first line contains one integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ). The second line contains the string $ s $ consisting of exactly $ n $ characters, each character is either L or R. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3 \cdot 10^5 $ .

输出格式

For each test case, print $ n + 1 $ integers. The $ i $ -th integer should be equal to the maximum number of different cities the traveler can visit during one journey if this journey starts in the $ i $ -th city.

输入输出样例

输入样例 #1

2
6
LRRRLL
3
LRL

输出样例 #1

1 3 2 3 1 3 2
1 4 1 4