問題概要
長さ 
の文字列 
が与えられる. ある長さ 
を選び, 長さ の部分列を反転させる操作を の双方に行う( index はそれぞれで選んで良いが, 必ず同じ長さを反転させる必要がある).
を一致させることができるか？
問題へのリンク
制約
解法
まず, 構成している文字が違う場合は明らかに NO なので, そのような場合は最初に除きます.
を 
に一致できるか？ という問題を解く代わりに, 双方に操作をすることによって両方を同じ文字列にできるか？という問題を考えましょう.
操作の性質上隣接要素についての swap が可能なので, のどちらかはソートすることができます. もし, (及び )が重複する文字を持っていれば, 隣接 swap を偶数回・奇数回のどちらを行うことでも文字列をソートできるので, 必然的に答えは YES になります.
逆に重複する文字がない場合, ソートするために必要な swap 回数の偶奇は文字列の転倒数の偶奇に一致することを思い出せば, の転倒数の偶奇が一致しているかどうかが YES と NO を分けることがわかります.
実装
転倒数は BIT などを用いることにより効率的に計算することができますが, この問題においては転倒数を計算する必要がある文字列の長さは最大でも 
なので, 愚直に計算すれば良いです.
Submission #147843509 - Codeforces
