math/inversion_number.hpp

• View this file on GitHub
• Last update: 2025-02-27 06:13:46+09:00
• Include: #include "math/inversion_number.hpp"

Depends on

• data_structure/fenwick_tree.hpp

Verified with

• verify/aoj/aoj_alds1_5_d.test.cpp

Code

#include "../data_structure/fenwick_tree.hpp"

template<typename T>
long long inversion_number(const vector<T>& A) {
    vector<T> B = A;
    sort(B.begin(), B.end());
    B.erase(unique(B.begin(), B.end()), B.end());

    FenwickTree<T> bit(B.size());

    long long ret = 0;
    for(int i = 0; i < (int)A.size(); i++) {
        int rank = lower_bound(B.begin(), B.end(), A[i]) - B.begin() + 1;
        ret += i - bit.sum(rank);
        bit.add(rank, 1);
    }
    return ret;
}

#line 1 "data_structure/fenwick_tree.hpp"
template <typename T=int>
struct FenwickTree {
    int n;
    vector<T> data;
    FenwickTree(int n) : n(n), data(n, 0) {}

    void add(int p, T x) {
        for(p++; p <= n; p += p & -p) data[p - 1] += x;
    }

    T sum(int r) {
        T s = 0;
        for(; r; r -= r & -r) s += data[r - 1];
        return s;
    }
    
    T sum(int l, int r) {
        return sum(r) - sum(l);
    }
};
#line 2 "math/inversion_number.hpp"

template<typename T>
long long inversion_number(const vector<T>& A) {
    vector<T> B = A;
    sort(B.begin(), B.end());
    B.erase(unique(B.begin(), B.end()), B.end());

    FenwickTree<T> bit(B.size());

    long long ret = 0;
    for(int i = 0; i < (int)A.size(); i++) {
        int rank = lower_bound(B.begin(), B.end(), A[i]) - B.begin() + 1;
        ret += i - bit.sum(rank);
        bit.add(rank, 1);
    }
    return ret;
}

Back to top page