Original proposer: admin

First, we assume that the following Theorem 1 and design a solution.

Theorem 1.
For each integer \(i\) (\(1 \le i \le N\)), there exist integer \(l\) and \(r\) such that:

• For all \(l \le k \le r\), the integer \(i\) can be written in the \(k\)-th cell from the left.
• For all \(k<l\) or \(r<k\), the integer \(i\) cannot be written in the \(k\)-th cell from the left.

Simply put, we claim that for every integer \(i\), the positions where \(i\) can be located form a single run.

For example, when \(S=\) LRRLLLR, where can \(4\) be written?

• First, the \(3\)-th character of \(S\) is R, so \(3\) is to the right of \(4\).
• Moreover, the \(2\)-th character of \(S\) is R too, so \(2\) is to the right of \(3\).
• First, the \(4\)-th character of \(S\) is L, so \(4\) is to the left of \(5\).
• Moreover, the \(5\)-th character of \(S\) is L too, so \(5\) is to the left of \(6\).
• Moreover, the \(6\)-th character of \(S\) is L too, so \(6\) is to the left of \(7\).

Together, it turns out that:

• \(2,3,4\) are arranged in this order from left to right.
• \(7,6,5,4\) are arranged in this order from left to right.

Therefore, \(4\) cannot be written in the \(1,2,3,4,5\)-th cells from the left.

For the remaining integers \(1,8\), we can observe the following facts:

• Since the \(1\)-st character of \(S\) is L, it is sufficient as long as \(2\) is to the left of \(1\). So \(1\) can be placed either to the left or right of \(4\).
• Since the \(7\)-st character of \(S\) is R, it is sufficient as long as \(8\) is to the right of \(7\). So \(8\) can be placed either to the left or right of \(4\).

Hence, \(4\) can be placed in the \(6,7,8\)-th cells from the left.

This process helps us to come up with the following Theorem 2:

Theorem 2.
\(i\) can be written in either the \(l,l+1,\dots,r\)-th cell from the left, where

• \(l\) is (the length of the run of Rs extending from the \((i-1)\)-th character of \(S\) to the left) \(+\) (the length of the run of Ls extending from the \(i\)-th character of \(S\) to the right) \(+1\);
• \(r\) is \(N-\) (the length of the run of Ls extending from the \((i-1)\)-th character of \(S\) to the left) \(+\) (the length of the run of Rs extending from the \(i\)-th character of \(S\) to the right).

Indeed, this Theorem 2 is correct.
We demonstrate an outline of a proof of Theorem 2 to present the proofs of Theorem 1 and 2.

Proof outline of Theorem 2

One can show that \(i\) cannot be written in the \(k\)-th cell from the left for \(k<l\) or \(r<k\) because of the runs specified above (by traversing them in the same way as the example).
Suppose that the run extending from the \((i-1)\)-th character stops at the \(l'\)-th character, and the run from the \(i\)-th stop at the \(r'\)-th.
Consider the following three disjoint subsequences of an arrangement:

• arrangement \(A\) of \(1,2,\dots,l'\) according to the constraints specified as the \(1,2,\dots,(l'-1)\)-th characters of \(S\)
• arrangement \(B\) of \(l'+1,l'+2,\dots,r'\) according to the constraints specified as the \(l'+1,l'+2,\dots,r'-1\)-th characters of \(S\)
• arrangement \(C\) of \(r'+1,r'+2,\dots,N\) according to the constraints specified as the \(r'+1,r'+2,\dots,N-1\)-th characters of \(S\)

The only factors left are the \(l'\)-th and \(r'\)-th characters of \(S\), and how to merge those three subsequences. The constraint by the \(l'\)-th character of \(S\) is different from those by the consecutive constraints starting from the \((l'+1)\)-th character of \(S\). Thus, as long as the relative positions of \(l'\) and \((l'+1)\) are appropriate, we can distribute any number of elements of \(A\) to the left and right of \(i\) and insert them into \(B\). Similarly, one can distribute any number of elements of \(C\) to the both sides of \(i\) in \(B\).
With this free insertions, \(i\) can be located at any positions from the \(l\)-th through \(r\)-th cell.

By Theorem 2, the problem can be solved in \(O(N)\) time using an appropriate precalculation and cumulative sums.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int t;
  cin >> t;
  for(int tr=0;tr<t;tr++){
    int n;
    string s;
    cin >> n >> s;
    
    s="."+s+".";
    vector<int> lp(n+1,0),rp(n+1,0);
    for(int i=1;i<n;i++){
      if(s[i]=='L'){
        lp[i]=lp[i-1]+1;
      }
      if(s[i]=='R'){
        rp[i]=rp[i-1]+1;
      }
    }
    vector<int> ls(n+1,0),rs(n+1,0);
    for(int i=n-1;i>=1;i--){
      if(s[i]=='L'){
        ls[i]=ls[i+1]+1;
      }
      if(s[i]=='R'){
        rs[i]=rs[i+1]+1;
      }
    }

    vector<int> bk(n+1,0);
    for(int i=0;i<n;i++){
      int l=0,r=n-1;
      l+=(rp[i]+ls[i+1]);
      r-=(lp[i]+rs[i+1]);
      bk[l]++;
      bk[r+1]--;
    }
    for(int i=0;i<n;i++){
      if(i){
        cout << " ";
        bk[i]+=bk[i-1];
      }
      cout << bk[i];
    }cout << "\n";
  }
 return 0;
}