転倒数
(misc/inversion-number.hpp)

• View this file on GitHub
• Last update: 2023-02-25 23:57:16+09:00
• Include: #include "misc/inversion-number.hpp"

Depends on

• data-structure/BIT.hpp

Verified with

• test/aoj/aoj-ALDS1-5-D.test.cpp

Code

#pragma once

#include "../data-structure/BIT.hpp"

template<class T>
T inversion_number(const std::vector<int>& v) {
    int N = (int)v.size();
    BIT<int> bt(N);
    T res = 0;
    for(int i = 0; i < N; i++) {
        res += i - bt.sum(v[i]+1);
        bt.add(v[i], 1);
    }
    return res;
}

#line 2 "misc/inversion-number.hpp"

#line 2 "data-structure/BIT.hpp"

#include <cassert>
#include <vector>

template <typename T> class BIT {
  public:
    BIT() = default;
    explicit BIT(int N) : N(N), dat(N + 1, 0) {}
    T sum(int r) {
        T ret = 0;
        for(; r >= 1; r -= lsb(r)) ret += dat[r];
        return ret;
    }
    T sum(int l, int r) {
        assert(l <= r);
        if(l == r) return T(0);
        return (sum(r) - sum(l));
    }
    void add(int pos, T val) {
        for(int i = pos + 1; i <= N; i += lsb(i)) dat[i] += val;
    }
    int lower_bound(T val) {
        int pos = 0;
        int k = 1;
        while(2 * k <= N) k <<= 1;
        for(; k >= 1; k >>= 1) {
            if(pos + k <= N and dat[pos + k] < val) {
                pos += k;
                val -= dat[pos];
            }
        }
        return pos + 1;
    }

  private:
    int N;
    std::vector<T> dat;

    inline int lsb(int i) { return i & (-i); }
};
#line 4 "misc/inversion-number.hpp"

template<class T>
T inversion_number(const std::vector<int>& v) {
    int N = (int)v.size();
    BIT<int> bt(N);
    T res = 0;
    for(int i = 0; i < N; i++) {
        res += i - bt.sum(v[i]+1);
        bt.add(v[i], 1);
    }
    return res;
}

Back to top page