問題原案：admin

まず、以下の定理1を仮定して解法を立てます。

定理1.
各整数 \(i\) ( \(1 \le i \le N\) ) について、以下が成り立つ整数 \(l,r\) が存在する。

• \(l \le k \le r\) について、 \(i\) は左から \(k\) 番目に存在しうる。
• \(k<l\) または \(r<k\) について、 \(i\) は左から \(k\) 番目に存在しえない。

わかりやすく言い換えると、どの整数 \(i\) についても、 \(i\) が存在しうる範囲はひとつの区間を成すという内容です。

例えば \(S=\) LRRLLLR について、 \(4\) が存在しうる範囲を考えてみましょう。

• まず、 \(S\) の \(3\) 文字目が R なので、 \(3\) の右に \(4\) が存在します。
• 更に、 \(S\) の \(2\) 文字目も R なので、 \(2\) の右に \(3\) が存在します。
• また、 \(S\) の \(4\) 文字目が L なので、 \(4\) の左に \(5\) が存在します。
• 更に、 \(S\) の \(5\) 文字目も L なので、 \(5\) の左に \(6\) が存在します。
• 更に、 \(S\) の \(6\) 文字目も L なので、 \(6\) の左に \(7\) が存在します。

これらを統合すると、

• \(2,3,4\) がこの順に左から並ぶ。
• \(7,6,5,4\) がこの順に左から並ぶ。

なので、 \(4\) が左から \(1,2,3,4,5\) 番目に来ることはありません。

残った \(1,8\) の処遇については以下が分かります。

• \(S\) の \(1\) 文字目が L なので、 \(2\) が \(1\) の左にありさえすればよいです。 \(4\) より左にも、 \(4\) より右にも自由に置くことができます。
• \(S\) の \(7\) 文字目が R なので、 \(8\) が \(7\) の右にありさえすればよいです。 \(4\) より左にも、 \(4\) より右にも自由に置くことができます。

よって、 \(4\) がありうる範囲は左から \(6,7,8\) 番目となります。

この過程を拡張すると、以下の定理2が予想できます。

定理2.
\(i\) が存在しうる範囲は左から \(l,l+1,\dots,r\) 番目である。ただし、

• \(l\) は ( \(S\) の \(i-1\) 文字目から左に連続する R の個数 ) \(+\) ( \(S\) の \(i\) 文字目から右に連続する L の個数 ) \(+1\)
• \(r\) は \(N-\) ( \(S\) の \(i-1\) 文字目から左に連続する L の個数 ) \(-\) ( \(S\) の \(i\) 文字目から右に連続する R の個数 )

実際、この定理2は正しいです。
以下に定理2の略証を行うことで、定理1,2の証明とします。

定理2の略証
\(k<l\) ないし \(r<k\) について、左から \(k\) 番目に \(i\) が存在しえないことは、 \(S\) の文字の連続の条件から (例と同様に辿ることで)示せる。
\(i-1\) 文字目から始めて左への文字の連続が途切れる箇所を \(l'\) 文字目 、 \(i\) 文字目から始めて右への文字の連続が途切れる箇所を \(r'\) 文字目とする。
数を並べる際に以下のように区切ることを考える。

• \(1,2,\dots,l'\) を、 \(S\) の \(1,2,\dots,l'-1\) 文字目の制約に従って並べた列 \(A\)
• \(l'+1,l'+2,\dots,r'\) を、 \(S\) の \(l'+1,l'+2,\dots,r'-1\) 文字目の制約に従って並べた列 \(B\)
• \(r'+1,r'+2,\dots,N\) を、 \(S\) の \(r'+1,r'+2,\dots,N-1\) 文字目の制約に従って並べた列 \(C\)

考慮すべき残りの事項は、 \(S\) の \(l'\) 文字目、 \(r'\) 文字目と上記の \(3\) つの列のマージです。

\(S\) の \(l'\) 文字目の制約は \(S\) の \(l'+1\) 文字目以降で連続する制約と異なります。なので、 \(l',l'+1\) の位置関係さえ適切にしておけば、 \(i\) の左と右の好きな側に \(A\) の任意の個数を振り分けて \(B\) に挿入することができます。 また、 \(C\) の任意の個数を \(i\) の左右に振り分けて \(B\) に挿入することもできます。
この自由な挿入を利用することで、 \(l\) 番目から \(r\) 番目までの任意の位置に \(i\) を位置させることができます。

定理2を利用すると、適切な予計算と累積和の利用でこの問題を時間計算量 \(O(N)\) で正解できます。

実装例 (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;
}