公式解説では後ろから解いていますが、前から解くこともできます。

\(i\) 番目の操作が終わった時点で \(i\) より左側の要素からなる数列を \(L\)、右側の要素からなる数列を \(R\) とします。

例えばサンプル \(1\) であれば

• 初期状態では、\(A=(0)\) であり、\(L=(),R=()\)
• \(i=1\) のとき、\(s_1=\)L なので \(A=(1,0)\) であり、\(L=(),R=(0)\)
• \(i=2\) のとき、\(s_2=\)R なので \(A=(1,2,0)\) であり、\(L=(1),R=(0)\)
• \(i=3\) のとき、\(s_3=\)R なので \(A=(1,2,3,0)\) であり、\(L=(1,2),R=(0)\)
• \(i=4\) のとき、\(s_4=\)L なので \(A=(1,2,4,3,0)\) であり、\(L=(1,2),R=(3,0)\)
• \(i=5\) のとき、\(s_5=\)R なので \(A=(1,2,4,5,3,0)\) であり、\(L=(1,2,4),R=(3,0)\)

というようになります。一連の操作をよく観察すると、\(s_i=\)L のとき \(R\) の先頭に \(i-1\) を挿入し、\(s_i=\)R のとき \(L\) の末尾に \(i-1\) を挿入していることがわかります。

したがって、「両端 queue を使う」「\(R\) を reverse した状態で持つ」などにより、操作は \(O(1)\) で行えます。

実装例(Python)

L=[]
R=[]
N=int(input())
S=input()
for i,c in enumerate(S):
	if c=='L': R.append(i)
	else: L.append(i)
print(*(L+[N]+R[::-1]))

公式解説では「真ん中」を持っていたのに対し、こちらの解法では「両端」を持っていたとみなすことができます。