ferinの競プロ帳

競プロについてのメモ

2018-10-30から1日間の記事一覧

ARC097 E - Sorted and Sorted

問題ページ 解法 転倒数が答えになるので転倒数の定義を考える。最初の数列をA、最終状態の数列をBとする。(転倒数) = (A[ia]=B[ib]=x,A[ja]=B[jb]=yとしたときにia<jaかつib>jbとなるペア(x,y) (x</jaかつib>