library/_internal/math/inversion.hpp

• View this file on GitHub
• Last update: 2025-03-03 00:33:48+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 <iterator>
using namespace std;

#include "../types.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 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

Back to top page