転倒数
(util/inversionnumber.hpp)

• View this file on GitHub
• Last update: 2020-08-24 21:21:29+09:00
• Include: #include "util/inversionnumber.hpp"

概要

転倒数. $i < j$ かつ $a_i > a_j$ となる組$(i, j)$の個数. バブルソートのスワップ回数と等しい.

計算量

$O(n\log n)$

使用例

• inversion_number(v) : vの転倒数.

Verified with

• test/yukicoder/1115.test.cpp

Code

/**
* @brief 転倒数
* @docs docs/util/inversionnumber.md
*/

template <typename T>
long long inversion_number(vector<T> &v) {
    int sz = v.size();
    vector<T> rev, v_cp(v);
    sort(v_cp.begin(), v_cp.end());
    for (auto &e : v) rev.emplace_back(lower_bound(v_cp.begin(), v_cp.end(), e) - v_cp.begin());
    BinaryIndexedTree<T> bit(sz);
    long long ret = 0;
    for (int i = 0; i < sz; ++i) {
        ret += i - bit.sum(rev[i]);
        bit.add(rev[i], 1);
    }
    return ret;
}

#line 1 "util/inversionnumber.hpp"
/**
* @brief 転倒数
* @docs docs/util/inversionnumber.md
*/

template <typename T>
long long inversion_number(vector<T> &v) {
    int sz = v.size();
    vector<T> rev, v_cp(v);
    sort(v_cp.begin(), v_cp.end());
    for (auto &e : v) rev.emplace_back(lower_bound(v_cp.begin(), v_cp.end(), e) - v_cp.begin());
    BinaryIndexedTree<T> bit(sz);
    long long ret = 0;
    for (int i = 0; i < sz; ++i) {
        ret += i - bit.sum(rev[i]);
        bit.add(rev[i], 1);
    }
    return ret;
}

Back to top page