inversion_number

関数 · 転倒数

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

概要

転倒数

パラメータ

戻り値

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

計算量

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

関連項目

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