Compress values (tools/compress.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-02-11 20:40:34+09:00
• Include: #include "tools/compress.hpp"

template <::std::ranges::range R, typename OutputIterator>
void compress(R&& a, OutputIterator result);

Given a sequence $(a_0, a_1, \ldots, a_{n - 1})$, it stores the integer sequence $(b_0, b_1, \ldots, b_{n - 1})$ to result where $b_i$ is the number of distinct elements in $a$ less than $a_i$.

Constraints

• For any integer pairs $(l, r)$ such that $0 \leq l < r < n$, $a_i < a_j$ is defined.

Time Complexity

• $O(n \log n)$

License

• CC0

Author

• anqooqie

Depends on

• std::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_COMPRESS_HPP
#define TOOLS_COMPRESS_HPP

#include <algorithm>
#include <ranges>
#include <vector>
#include "tools/lower_bound.hpp"

namespace tools {
  template <::std::ranges::range R, typename OutputIterator>
  void compress(R&& a, OutputIterator result) {
    using T = typename ::std::ranges::range_value_t<R>;
    if constexpr (::std::ranges::forward_range<R>) {
      ::std::vector<T> sorted(::std::ranges::begin(a), ::std::ranges::end(a));
      ::std::ranges::sort(sorted);
      sorted.erase(::std::unique(sorted.begin(), sorted.end()), sorted.end());
      for (auto it = ::std::ranges::begin(a); it != ::std::ranges::end(a); ++it, ++result) {
        *result = ::tools::lower_bound(sorted.begin(), sorted.end(), *it);
      }
    } else {
      ::tools::compress(::std::vector<T>(::std::ranges::begin(a), ::std::ranges::end(a)), result);
    }
  }
}

#endif

#line 1 "tools/compress.hpp"



#include <algorithm>
#include <ranges>
#include <vector>
#line 1 "tools/lower_bound.hpp"



#include <iterator>
#line 6 "tools/lower_bound.hpp"

namespace tools {

  template <class ForwardIterator, class T>
  auto lower_bound(ForwardIterator first, ForwardIterator last, const T& value) {
    return ::std::distance(first, ::std::lower_bound(first, last, value));
  }

  template <class ForwardIterator, class T, class Compare>
  auto lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp) {
    return ::std::distance(first, ::std::lower_bound(first, last, value, comp));
  }
}


#line 8 "tools/compress.hpp"

namespace tools {
  template <::std::ranges::range R, typename OutputIterator>
  void compress(R&& a, OutputIterator result) {
    using T = typename ::std::ranges::range_value_t<R>;
    if constexpr (::std::ranges::forward_range<R>) {
      ::std::vector<T> sorted(::std::ranges::begin(a), ::std::ranges::end(a));
      ::std::ranges::sort(sorted);
      sorted.erase(::std::unique(sorted.begin(), sorted.end()), sorted.end());
      for (auto it = ::std::ranges::begin(a); it != ::std::ranges::end(a); ++it, ++result) {
        *result = ::tools::lower_bound(sorted.begin(), sorted.end(), *it);
      }
    } else {
      ::tools::compress(::std::vector<T>(::std::ranges::begin(a), ::std::ranges::end(a)), result);
    }
  }
}

Back to top page