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"

最初は deque が空で、反転していない状態である。

各文字を処理した後の状態は次のようになる。

最後は通常状態なので、deque 全体を反転する必要はない。
したがって、答えは 5 2 1 3 4 となる。

注意点

特になし。

別解

特になし。