ABC465 C - Reverse Permutation

考え方

一見、reverse() を多用して解けそうに見える。
しかし、reverse() は $O(N)$ かかる関数であり、$S$ の中身が 'o' だらけだと全体で $O(N^2)$ かかる。
$N$ が最大 $500000$ まで対応しなければならないので、これでは間に合わずTLE。
そこで高速化を考える。

データをひっくり返すのに時間がかかるなら、代わりにデータを見ている自分がひっくり返ればよい。
つまり、反転が発生したら、実際の前を今後は後ろだと思い、実際の後ろを今後は前だと思えばよい。

それだけだと一部だけ反転というのは不可能であるように思えるが、そこは工夫次第で回避できる。
例えば $1$ から $3$ までを反転する操作は、$4$ 以上が存在しないものとして、全体反転すればよい。

すなわち、以下を実行すればよい。

• 空のデータを用意する
• $1$ を「後ろ」に追加する
• $1$ から $1$ まで反転があるなら、自分がひっくり返る
• $2$ を「後ろ」に追加する
• $1$ から $2$ まで反転があるなら、自分がひっくり返る
• $3$ を「後ろ」に追加する
• $1$ から $3$ まで反転があるなら、自分がひっくり返る
• $\dots$

これなら、毎回反転があっても $O(N)$ で処理が終わる。
値を（実際の）前からも後ろからも追加するので、データ構造は deque の出番。

あとは、最後に自分がひっくり返ったまま終わった場合は、最後だけ本当に反転させれば答え。

入力例1での動作

入力を受け取る。

n: 5
s: "ooxoo"

答え用の変数 que を空の状態で用意する。
また、反転状態を表す変数 reversed を false で初期化する。

que: {}
reversed: false

$0$ 文字目を処理する。
reversed は false なので、1 を後ろに追加する。
s[0] は o なので、reversed を反転する。

que: {1}
reversed: true

$1$ 文字目を処理する。
reversed は true なので、2 を前に追加する。
s[1] は o なので、reversed を反転する。

que: {2, 1}
reversed: false

$2$ 文字目を処理する。
reversed は false なので、3 を後ろに追加する。
s[2] は x なので、reversed はそのままである。

que: {2, 1, 3}
reversed: false

$3$ 文字目を処理する。
reversed は false なので、4 を後ろに追加する。
s[3] は o なので、reversed を反転する。

que: {2, 1, 3, 4}
reversed: true

$4$ 文字目を処理する。
reversed は true なので、5 を前に追加する。
s[4] は o なので、reversed を反転する。

que: {5, 2, 1, 3, 4}
reversed: false

最後に、reversed は false なので、que を反転しない。

よって、5 2 1 3 4 を出力する。

注意点

特になし。

別解

特になし。