Journey
Contest: Educational Codeforces Round 103 (Rated for Div. 2)
Difficulty rating: 1700
Tags: dfs and similar, dp, dsu, implementation

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$$$.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Example input:
2
6
LRRRLL
3
LRL

Example output:
1 3 2 3 1 3 2
1 4 1 4

Editorial:
There are two key observations to this problem:
• after each pair of moves, the directions go back to the original ones;
• after each move, we can immediately go back (and combining these observations, we can derive that if we go from city $$$i$$$ to some other city $$$j$$$, we can always go back).
One of the solutions we can write using these observations is to build an undirected graph on $$$2n+2$$$ vertices. Each vertex represents a pair $$$(v, k)$$$, where $$$v$$$ is the city we are currently staying in, and $$$k$$$ is the number of moves we made, modulo $$$2$$$. Since each move is to a neighboring city, each vertex $$$(v, 0)$$$ is unreachable from $$$(v, 1)$$$, and vice versa. And since we can always go back, and each pair of steps doesn't change the directions, this graph is actually an undirected one. So, we can find the connected components of this graph using DFS/BFS/DSU, and for each city $$$v$$$, print the size of the component the vertex $$$(v, 0)$$$ belongs to.
Another solution is to find the leftmost and the rightmost city reachable from each city. For example, finding the leftmost reachable city can be done with the following dynamic programming: let $$$dp_i$$$ be the leftmost city reachable from $$$i$$$. Then, if we can't go left from $$$i$$$, $$$dp_i = i$$$; if we can make only one step to the left from $$$i$$$, $$$dp_i = i - 1$$$; and if we can make two steps, we can take the answer from the city $$$i - 2$$$: $$$dp_i = dp_{i - 2}$$$. The same approach can be used to calculate the rightmost reachable city.