Coordinate compression (tools/compressed.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-01-01 20:09:34+09:00
• Include: #include "tools/compressed.hpp"

(1)
template <tools::integral T, std::ranges::input_range R>
requires std::totally_ordered<std::ranges::range_value_t<R>>
std::vector<T> compressed(R&& a);

(2)
template <std::ranges::input_range R>
requires std::totally_ordered<std::ranges::range_value_t<R>>
std::vector<std::conditional_t<tools::integral<std::ranges::range_value_t<R>>, std::ranges::range_value_t<R>, int>> compressed(R&& a);

• (1)
  • Given a sequence $(a_0, a_1, \ldots, a_{n - 1})$, it returns $(b_0, b_1, \ldots, b_{n - 1})$ where $b_i$ is the number of distinct elements in $a$ less than $a_i$.
• (2)
  • It is almost equivalent to (1), but returns std::vector<std::conditional_t<tools::integral<std::ranges::range_value_t<R>>, std::ranges::range_value_t<R>, int>>.

Constraints

• None

Time Complexity

• $O(n \log n)$

License

• CC0

Author

• anqooqie

Depends on

• Concept for integral types including tools::int128_t and tools::uint128_t (tools/integral.hpp)
• std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
• std::ranges::lower_bound, but returns index (tools/lower_bound.hpp)

Required by

• The number of inversions (tools/inversion_number.hpp)
• Range count distinct (tools/range_count_distinct.hpp)

Verified with

• tests/inversion_number.test.cpp
• tests/lazy_segtree/lazy_segtree/binary_search.test.cpp
• tests/lazy_sparse_segtree/binary_search.test.cpp
• tests/persistent_lazy_segtree/binary_search.test.cpp
• tests/range_count_distinct.test.cpp

Code

#ifndef TOOLS_COMPRESSED_HPP
#define TOOLS_COMPRESSED_HPP

#include <algorithm>
#include <concepts>
#include <ranges>
#include <type_traits>
#include <utility>
#include <vector>
#include "tools/integral.hpp"
#include "tools/lower_bound.hpp"

namespace tools {
  template <tools::integral T, std::ranges::input_range R>
  requires std::totally_ordered<std::ranges::range_value_t<R>>
  std::vector<T> compressed(R&& a) {
    if constexpr (std::ranges::forward_range<R>) {
      auto sorted = a | std::ranges::to<std::vector>();
      std::ranges::sort(sorted);
      sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
      return std::forward<R>(a) | std::views::transform([&](const auto& a_i) { return tools::lower_bound(sorted, a_i); }) | std::ranges::to<std::vector<T>>();
    } else {
      return tools::compressed<T>(std::forward<R>(a) | std::ranges::to<std::vector>());
    }
  }

  template <std::ranges::input_range R>
  requires std::totally_ordered<std::ranges::range_value_t<R>>
  std::vector<std::conditional_t<tools::integral<std::ranges::range_value_t<R>>, std::ranges::range_value_t<R>, int>> compressed(R&& a) {
    return tools::compressed<std::conditional_t<tools::integral<std::ranges::range_value_t<R>>, std::ranges::range_value_t<R>, int>>(std::forward<R>(a));
  }
}

#endif

#line 1 "tools/compressed.hpp"



#include <algorithm>
#include <concepts>
#include <ranges>
#include <type_traits>
#include <utility>
#include <vector>
#line 1 "tools/integral.hpp"



#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = tools::is_integral<T>::value;
}


#line 5 "tools/integral.hpp"

namespace tools {
  template <typename T>
  concept integral = tools::is_integral_v<T>;
}


#line 1 "tools/lower_bound.hpp"



#line 5 "tools/lower_bound.hpp"
#include <functional>
#include <iterator>
#line 8 "tools/lower_bound.hpp"

namespace tools {

  template <
    std::random_access_iterator I,
    std::sentinel_for<I> S,
    typename Proj = std::identity,
    typename T = std::remove_cvref_t<std::invoke_result_t<Proj&, std::iter_value_t<I>&>>,
    std::indirect_strict_weak_order<const T*, std::projected<I, Proj>> Comp = std::ranges::less
  >
  constexpr std::iter_difference_t<I> lower_bound(const I first, const S last, const T& value, const Comp comp = {}, const Proj proj = {}) {
    return std::ranges::distance(first, std::ranges::lower_bound(first, last, value, comp, proj));
  }

  template <
    std::ranges::random_access_range R,
    typename Proj = std::identity,
    typename T = std::remove_cvref_t<std::invoke_result_t<Proj&, std::ranges::range_value_t<R>&>>,
    std::indirect_strict_weak_order<const T*, std::projected<std::ranges::iterator_t<R>, Proj>> Comp = std::ranges::less
  >
  constexpr std::ranges::range_difference_t<R> lower_bound(R&& r, const T& value, const Comp comp = {}, const Proj proj = {}) {
    return std::ranges::distance(std::ranges::begin(r), std::ranges::lower_bound(r, value, comp, proj));
  }
}


#line 12 "tools/compressed.hpp"

namespace tools {
  template <tools::integral T, std::ranges::input_range R>
  requires std::totally_ordered<std::ranges::range_value_t<R>>
  std::vector<T> compressed(R&& a) {
    if constexpr (std::ranges::forward_range<R>) {
      auto sorted = a | std::ranges::to<std::vector>();
      std::ranges::sort(sorted);
      sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
      return std::forward<R>(a) | std::views::transform([&](const auto& a_i) { return tools::lower_bound(sorted, a_i); }) | std::ranges::to<std::vector<T>>();
    } else {
      return tools::compressed<T>(std::forward<R>(a) | std::ranges::to<std::vector>());
    }
  }

  template <std::ranges::input_range R>
  requires std::totally_ordered<std::ranges::range_value_t<R>>
  std::vector<std::conditional_t<tools::integral<std::ranges::range_value_t<R>>, std::ranges::range_value_t<R>, int>> compressed(R&& a) {
    return tools::compressed<std::conditional_t<tools::integral<std::ranges::range_value_t<R>>, std::ranges::range_value_t<R>, int>>(std::forward<R>(a));
  }
}

Back to top page