Thingmemo
実装一覧へ戻る

組合せ

置換の符号

Fenwick木で0〜n−1の順列の転倒数と偶奇を求め、置換の符号を返します。

TIME
O(n log n)
SPACE
O(n)

n = 順列サイズ / 上限: 0〜10,000要素、各値は0〜n−1を重複なく1回ずつ

順列の符号と反転数を求めます。

関連するアルゴリズム