転倒数 (inversion number)
(include/emthrm/misc/inversion_number.hpp)

• View this file on GitHub
• Last update: 2023-02-25 16:35:06+09:00
• Include: #include "emthrm/misc/inversion_number.hpp"

数列 $A$ に対して $A_i > A_j$ を満たす組 $(i, j)$ ($i < j$) の個数である。

バブルソートに必要な交換回数に等しい。

時間計算量

$O(N\log{N})$

仕様

名前	戻り値
template <typename T> long long inversion_number(const std::vector<T>& a);	$A$ の転倒数

参考文献

• 秋葉拓哉，岩田陽一，北川宜稔：プログラミングコンテストチャレンジブック [第2版]，pp.162-163，マイナビ出版（2012）

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/ALDS1_5_D/review/4087800/emthrm/C++14

Depends on

• Fenwick tree (binary indexed tree) (include/emthrm/data_structure/fenwick_tree/fenwick_tree.hpp)

Verified with

• その他/転倒数 (test/misc/inversion_number.test.cpp)

Code

#ifndef EMTHRM_MISC_INVERSION_NUMBER_HPP_
#define EMTHRM_MISC_INVERSION_NUMBER_HPP_

#include <algorithm>
#include <iterator>
#include <vector>

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

namespace emthrm {

template <typename T>
long long inversion_number(const std::vector<T>& a) {
  const int n = a.size();
  std::vector<T> b = a;
  std::sort(b.begin(), b.end());
  b.erase(std::unique(b.begin(), b.end()), b.end());
  FenwickTree<int> bit(b.size());
  long long res = 0;
  for (int i = 0; i < n; ++i) {
    const int idx = std::distance(
        b.begin(), std::lower_bound(b.begin(), b.end(), a[i]));
    res += i - bit.sum(idx + 1);
    bit.add(idx, 1);
  }
  return res;
}

}  // namespace emthrm

#endif  // EMTHRM_MISC_INVERSION_NUMBER_HPP_

#line 1 "include/emthrm/misc/inversion_number.hpp"



#include <algorithm>
#include <iterator>
#include <vector>

#line 1 "include/emthrm/data_structure/fenwick_tree/fenwick_tree.hpp"



#include <bit>
#line 6 "include/emthrm/data_structure/fenwick_tree/fenwick_tree.hpp"

namespace emthrm {

template <typename Abelian>
struct FenwickTree {
  explicit FenwickTree(const int n, const Abelian ID = 0)
      : n(n), ID(ID), data(n, ID) {}

  void add(int idx, const Abelian val) {
    for (; idx < n; idx |= idx + 1) {
      data[idx] += val;
    }
  }

  Abelian sum(int idx) const {
    Abelian res = ID;
    for (--idx; idx >= 0; idx = (idx & (idx + 1)) - 1) {
      res += data[idx];
    }
    return res;
  }

  Abelian sum(const int left, const int right) const {
    return left < right ? sum(right) - sum(left) : ID;
  }

  Abelian operator[](const int idx) const { return sum(idx, idx + 1); }

  int lower_bound(Abelian val) const {
    if (val <= ID) [[unlikely]] return 0;
    int res = 0;
    for (int mask = std::bit_ceil(static_cast<unsigned int>(n + 1)) >> 1;
         mask > 0; mask >>= 1) {
      const int idx = res + mask - 1;
      if (idx < n && data[idx] < val) {
        val -= data[idx];
        res += mask;
      }
    }
    return res;
  }

 private:
  const int n;
  const Abelian ID;
  std::vector<Abelian> data;
};

}  // namespace emthrm


#line 9 "include/emthrm/misc/inversion_number.hpp"

namespace emthrm {

template <typename T>
long long inversion_number(const std::vector<T>& a) {
  const int n = a.size();
  std::vector<T> b = a;
  std::sort(b.begin(), b.end());
  b.erase(std::unique(b.begin(), b.end()), b.end());
  FenwickTree<int> bit(b.size());
  long long res = 0;
  for (int i = 0; i < n; ++i) {
    const int idx = std::distance(
        b.begin(), std::lower_bound(b.begin(), b.end(), a[i]));
    res += i - bit.sum(idx + 1);
    bit.add(idx, 1);
  }
  return res;
}

}  // namespace emthrm

Back to top page