転倒数
(library/sequence/inversion_number.hpp)

• View this file on GitHub
• Last update: 2026-01-20 20:11:22+09:00
• Include: #include "library/sequence/inversion_number.hpp"

転倒数

できること

• 右に倒れる$A_i > A_j (i < j)$の回数を求める
• 座標圧縮したFenwick Treeで求めている

計算量

$O(NlogN)$

使い方

long long inv = inversion_number(A);

Depends on

• Fenwick Tree (library/segtree/fenwick_tree.hpp)
• 座標圧縮 (library/sequence/compressor.hpp)

Verified with

• 転倒数・座標圧縮・FenwickTreeのテスト (tests/sequence.inversion_number.test.cpp)

Code

#pragma once
#include "library/segtree/fenwick_tree.hpp"
#include "library/sequence/compressor.hpp"
template <typename T> long long inversion_number(const vector<T> &A) {
    if (A.empty()) return 0ll;
    Compressor<T> zip(A);
    vector<int> compressed_a = zip.get_all();
    int N = A.size(), sz = zip.size();
    FenwickTree fwk(sz);
    long long inv = 0;
    for (int i = 0; i < N; ++i) {
        inv += i - fwk.sum(compressed_a[i]);
        fwk.add(compressed_a[i], 1);
    }
    return inv;
}

#line 2 "library/segtree/fenwick_tree.hpp"
struct FenwickTree {
  private:
    int N;
    vector<int> fwk;

  public:
    FenwickTree(int N) : N(N) { fwk.assign(N + 1, 0); }
    FenwickTree(const vector<int> &A) : N(A.size()) {
        fwk.assign(N + 1, 0);
        for (int i = 1; i <= N; ++i) {
            fwk[i] += A[i - 1];
            if (i + (i & -i) <= N) fwk[i + (i & -i)] += fwk[i];
        }
    }
    void add(int i, const int &x) {
        for (++i; i <= N; i += i & -i) fwk[i] += x;
    }
    int sum(int i) {
        int ans = 0;
        for (++i; i; i -= i & -i) ans += fwk[i];
        return ans;
    }
};
#line 2 "library/sequence/compressor.hpp"
template <typename T> struct Compressor {
    vector<T> origin, dict;
    Compressor(const vector<T> &v) : origin(v), dict(v) {
        sort(dict.begin(), dict.end());
        dict.erase(unique(dict.begin(), dict.end()), dict.end());
    }
    int size() const { return dict.size(); }
    // 値 -> ID (圧縮)
    int get_id(T x) const {
        return lower_bound(dict.begin(), dict.end(), x) - dict.begin();
    }
    // 値 -> ID (upper_bound版)
    int get_upper_id(T x) const {
        return upper_bound(dict.begin(), dict.end(), x) - dict.begin();
    }
    // ID -> 値 (復元)
    T get_val(int id) const { return dict[id]; }
    // すべて圧縮
    vector<int> get_all() {
        vector<int> res;
        for (auto &&x : origin) res.emplace_back(get_id(x));
        return res;
    }
};
#line 4 "library/sequence/inversion_number.hpp"
template <typename T> long long inversion_number(const vector<T> &A) {
    if (A.empty()) return 0ll;
    Compressor<T> zip(A);
    vector<int> compressed_a = zip.get_all();
    int N = A.size(), sz = zip.size();
    FenwickTree fwk(sz);
    long long inv = 0;
    for (int i = 0; i < N; ++i) {
        inv += i - fwk.sum(compressed_a[i]);
        fwk.add(compressed_a[i], 1);
    }
    return inv;
}

Back to top page