転倒数
(library/math/inversion.hpp)

• View this file on GitHub
• Last update: 2025-03-03 00:33:48+09:00
• Include: #include "library/math/inversion.hpp"

転倒数を分割統治法で求める。

時間計算量: $O(n \log n)$
空間計算量: $O(n \log n)$ たぶん

使い方

asalib::math::inversion<T, U>(const vector<U>& A, bool eq)

• T: 転倒数の型。整数とか modint とか。

• U: 配列の要素型

• vector<U>& A: 転倒数を求めたい配列
• bool eq: 等号も含めるか。 デフォルトは false。
  • false: $#\lbrace (A_i, A_j) \mid i < j \land A_i > A_j \rbrace$
  • true: $#\lbrace (A_i, A_j) \mid i < j \land A_i \ge A_j \rbrace$

Depends on

• library/_internal/math/inversion.hpp
• library/_internal/modint-base.hpp
• 内部型 (library/_internal/types.hpp)

Verified with

• tests/math/inversion/abc264-d.test.cpp
• tests/math/inversion/abc296-f.test.cpp
• tests/math/inversion/abc332-d.test.cpp
• tests/math/inversion/alds1-5d.test.cpp
• tests/math/inversion/arc136-b.test.cpp
• tests/math/inversion/arc168-a.test.cpp

Code

#pragma once

#include <vector>
using namespace std;

#include "../_internal/math/inversion.hpp"
#include "../_internal/types.hpp"

namespace asalib {
  namespace math {
    template<_internal::integral_like T, typename U>
    T inversion(const vector<U>& a, const bool eq = false) {
      vector<U> t(a.begin(), a.end());
      if (eq) return _internal::math::inversion<T, true, U>(t.begin(), t.end());
      return _internal::math::inversion<T, false, U>(t.begin(), t.end());
    }
  }  // namespace math
}  // namespace asalib

#line 2 "library/math/inversion.hpp"

#include <vector>
using namespace std;

#line 2 "library/_internal/math/inversion.hpp"

#include <iterator>
using namespace std;

#line 2 "library/_internal/types.hpp"

#include <concepts>
#include <type_traits>
using namespace std;

#line 2 "library/_internal/modint-base.hpp"

#line 5 "library/_internal/modint-base.hpp"
using namespace std;

namespace asalib {
  namespace _internal {
    class modint_base {};

    template<typename T>
    concept is_modint = is_base_of_v<modint_base, T>;
  }  // namespace _internal
}  // namespace asalib
#line 8 "library/_internal/types.hpp"

namespace asalib {
  namespace _internal {
    // ---------- concept definition ---------- //
    template<class T>
    concept integral_like = integral<T> || is_modint<T>;

    template<class T>
    concept floating_like = floating_point<T>;

    template<class T>
    concept numeric_like = integral_like<T> || floating_like<T>;

    // ---------- function definition ---------- //
    template<class T>
    T plus(T a, T b) { return a + b; }

    template<class T>
    T minus(T a, T b) { return a - b; }

    // ---------- constant definition ---------- //
    template<class T>
    T zero() { return 0; }
  }  // namespace _internal
}  // namespace asalib
#line 7 "library/_internal/math/inversion.hpp"

namespace asalib {
  namespace _internal {
    namespace math {
      template<integral_like T, bool eq, typename U, random_access_iterator iter>
      T inversion(iter first, iter last) {
        const size_t n = distance(first, last);
        if (n <= 1) return 0;
        const size_t mid = n >> 1;
        auto left = inversion<T, eq, U>(first, first + mid);
        auto right = inversion<T, eq, U>(first + mid, last);
        T inv = left + right;
        iter l = first, r = first + mid, l_end = first + mid, r_end = last;
        vector<U> tmp;
        tmp.reserve(n);
        while (l < l_end && r < r_end) {
          if constexpr (eq) {
            if (*l < *r) tmp.push_back(*l++);
            else {
              tmp.push_back(*r++);
              inv += mid - (l - first);
            }
          }
          else {
            if (*l <= *r) tmp.push_back(*l++);
            else {
              tmp.push_back(*r++);
              inv += mid - (l - first);
            }
          }
        }
        while (l < l_end) tmp.push_back(*l++);
        while (r < r_end) tmp.push_back(*r++);
        copy(tmp.begin(), tmp.end(), first);
        return inv;
      }
    }  // namespace math
  }  // namespace _internal
}  // namespace asalib
#line 8 "library/math/inversion.hpp"

namespace asalib {
  namespace math {
    template<_internal::integral_like T, typename U>
    T inversion(const vector<U>& a, const bool eq = false) {
      vector<U> t(a.begin(), a.end());
      if (eq) return _internal::math::inversion<T, true, U>(t.begin(), t.end());
      return _internal::math::inversion<T, false, U>(t.begin(), t.end());
    }
  }  // namespace math
}  // namespace asalib

Back to top page