脳log[20221013]

2022年10月13日 (木) [AtCoder] 精進。第三回 PAST 過去問-N「入れ替えと並び替え」。どこかのブログで転倒している位置を管理することでソート全体を QlogQ で抑えられると読んだ。愚直にソートすると QNlogN になるところ。■提出 #35609961 (AC / 777 Byte / 1174 ms)。Ruby に平衡二分探索木はないし BIT でやったら TLE 間違いなしだったので配列を酷使する運任せの解答。ローカルでは５秒越えのケースもあったけどジャッジサーバーは速かった。