library/_internal/math/inversion.hpp

• View this file on GitHub
• Last update: 2025-08-17 00:21:01+09:00
• Include: #include "library/_internal/math/inversion.hpp"

Depends on

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

Required by

• 転倒数 (library/math/inversion.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 <algorithm>
#include <cstddef>
#include <iterator>
#include <vector>
using namespace std;

#include "../types.hpp"

namespace asalib::_internal::math {
  template<integral_like T, bool eq, typename U, random_access_iterator iter>
  constexpr 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.emplace_back(*l++);
        else {
          tmp.emplace_back(*r++);
          inv += mid - (l - first);
        }
      }
      else {
        if (*l <= *r) tmp.emplace_back(*l++);
        else {
          tmp.emplace_back(*r++);
          inv += mid - (l - first);
        }
      }
    }
    while (l < l_end) tmp.emplace_back(*l++);
    while (r < r_end) tmp.emplace_back(*r++);
    copy(tmp.begin(), tmp.end(), first);
    return inv;
  }
}  // namespace asalib::_internal::math

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

#include <algorithm>
#include <cstddef>
#include <iterator>
#include <vector>
using namespace std;

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

#include <concepts>
using namespace std;

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

#include <type_traits>
using namespace std;

namespace asalib::_internal {
  class modint_base {};

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

namespace asalib::_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 asalib::_internal
#line 10 "library/_internal/math/inversion.hpp"

namespace asalib::_internal::math {
  template<integral_like T, bool eq, typename U, random_access_iterator iter>
  constexpr 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.emplace_back(*l++);
        else {
          tmp.emplace_back(*r++);
          inv += mid - (l - first);
        }
      }
      else {
        if (*l <= *r) tmp.emplace_back(*l++);
        else {
          tmp.emplace_back(*r++);
          inv += mid - (l - first);
        }
      }
    }
    while (l < l_end) tmp.emplace_back(*l++);
    while (r < r_end) tmp.emplace_back(*r++);
    copy(tmp.begin(), tmp.end(), first);
    return inv;
  }
}  // namespace asalib::_internal::math

Back to top page