library/util/InversionNumber.hpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Include: #include "library/util/InversionNumber.hpp"

Depends on

Required by

library/util/BubbleNumber.hpp

Verified with

test/AOJ/ALDS1_5_D.test.cpp

Code

#include <atcoder/fenwicktree>

#include "library/util/Compress.hpp"

template <typename T> long long inversion_number(const std::vector<T> &v) {
    Compress cmp(v);
    atcoder::fenwick_tree<int> ft(cmp.size());
    long long res = 0;
    for (int i = int(v.size()) - 1; i >= 0; i--) {
        int j = cmp[v[i]];
        res += ft.sum(0, j);
        ft.add(j, 1);
    }
    return res;
}

#line 1 "library/util/InversionNumber.hpp"
#include <atcoder/fenwicktree>

#line 2 "library/util/Compress.hpp"
template <typename T, bool Sentinel = false> class Compress {
    std::vector<T> v;
    bool prepared;

  public:
    Compress() : prepared(false) {
        if constexpr (Sentinel) {
            static_assert(std::numeric_limits<T>::is_specialized,
                          "cannot use Sentinel");
            v = {std::numeric_limits<T>::min(), std::numeric_limits<T>::max()};
        }
    }
    Compress(const std::vector<T> &w) : v(w), prepared(false) {
        if constexpr (Sentinel) {
            static_assert(std::numeric_limits<T>::is_specialized,
                          "cannot use Sentinel");
            v.push_back(std::numeric_limits<T>::min());
            v.push_back(std::numeric_limits<T>::max());
        }
        build();
    }

    void add(T a) {
        assert(!prepared);
        v.push_back(a);
    }
    void build() {
        assert(!prepared);
        prepared = true;
        std::ranges::sort(v);
        auto result = std::ranges::unique(v);
        v.erase(result.begin(), result.end());
    }

    bool is_prepared() const { return prepared; }

    int operator[](const T &a) const {
        assert(prepared);
        auto it = std::ranges::lower_bound(v, a);
        assert(*it == a);
        return std::distance(v.begin(), it);
    }
    int geq(const T &a) const {
        assert(prepared);
        auto it = std::ranges::lower_bound(v, a);
        return std::distance(v.begin(), it);
    }
    int gt(const T &a) const {
        assert(prepared);
        auto it = std::ranges::upper_bound(v, a);
        return std::distance(v.begin(), it);
    }
    int leq(const T &a) const {
        assert(prepared);
        auto it = --std::ranges::upper_bound(v, a);
        return std::distance(v.begin(), it);
    }
    int lt(const T &a) const {
        assert(prepared);
        auto it = --std::ranges::lower_bound(v, a);
        return std::distance(v.begin(), it);
    }
    T r(int id) const {
        assert(prepared);
        return v[id];
    }
    bool exist(const T &a) const {
        assert(prepared);
        return (*std::ranges::lower_bound(v, a)) == a;
    }
    int size() const { return v.size(); }
    T max() const { return v.back(); }
    T min() const { return v[0]; }

    friend std::ostream &operator<<(std::ostream &os, const Compress &C) {
        for (int i = 0; i < C.v.size(); i++)
            os << C.v[i] << ":" << i << " ";
        return os;
    }
};
#line 4 "library/util/InversionNumber.hpp"

template <typename T> long long inversion_number(const std::vector<T> &v) {
    Compress cmp(v);
    atcoder::fenwick_tree<int> ft(cmp.size());
    long long res = 0;
    for (int i = int(v.size()) - 1; i >= 0; i--) {
        int j = cmp[v[i]];
        res += ft.sum(0, j);
        ft.add(j, 1);
    }
    return res;
}