inversion_number_of_permutation

関数 · 転倒数

template <class T>
std::int64_t inversion_number_of_permutation(const std::vector<T> &v);

概要

順列の転倒数

座標圧縮を省くので inversion_number より定数倍が軽い。

パラメータ

戻り値

i < j かつ v[i] > v[j] となる添字対の個数

事前条件

• v は 0 以上 n 未満の整数の順列

計算量

• 要素数を $n$ として $O(n\log n)$

関連項目

• inversion_number — 転倒数
• adjacent_swap_distance — 隣接スワップの最小回数