proconlib

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: tests/range_count_distinct.test.cpp

Depends on

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/static_range_count_distinct

#include <iostream>
#include <vector>
#include "tools/range_count_distinct.hpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  int N, Q;
  std::cin >> N >> Q;
  std::vector<int> a(N);
  for (auto& a_i : a) std::cin >> a_i;

  tools::range_count_distinct seq(a.begin(), a.end());

  for (int q = 0; q < Q; ++q) {
    int l, r;
    std::cin >> l >> r;
    std::cout << seq.query(l, r) << '\n';
  }

  return 0;
}

#line 1 "tests/range_count_distinct.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/static_range_count_distinct

#include <iostream>
#include <vector>
#line 1 "tools/range_count_distinct.hpp"



#include <cassert>
#include <cstddef>
#include <iterator>
#include <limits>
#include <ranges>
#line 1 "tools/wavelet_matrix.hpp"



#line 5 "tools/wavelet_matrix.hpp"
#include <utility>
#line 8 "tools/wavelet_matrix.hpp"
#include <algorithm>
#line 10 "tools/wavelet_matrix.hpp"
#include <array>
#include <tuple>
#include <optional>
#line 1 "tools/bit_vector.hpp"



#include <cstdint>
#line 6 "tools/bit_vector.hpp"
#include <immintrin.h>

// Source: https://nyaannyaan.github.io/library/data-structure-2d/wavelet-matrix.hpp.html
// License: CC0 1.0 Universal
// Author: Nyaan

namespace tools {
  class bit_vector {
  private:
    using u32 = ::std::uint32_t;
    using i64 = ::std::int64_t;
    using u64 = ::std::uint64_t;

    static constexpr u32 w = 64;
    ::std::vector<u64> m_block;
    ::std::vector<u32> m_count;
    u32 m_size, m_zeros;

  public:
    bit_vector() {}
    explicit bit_vector(int _n) { init(_n); }
    __attribute__((optimize("O3", "unroll-loops"))) void init(int _n) {
      m_size = m_zeros = _n;
      m_block.resize(m_size / w + 1, 0);
      m_count.resize(m_block.size(), 0);
    }

    u32 size() const { return m_size; }
    inline u32 get(u32 i) const { return u32(m_block[i / w] >> (i % w)) & 1u; }
    inline void set(u32 i) { m_block[i / w] |= 1LL << (i % w); }

    __attribute__((target("popcnt"))) void build() {
      for (u32 i = 1; i < m_block.size(); ++i)
        m_count[i] = m_count[i - 1] + _mm_popcnt_u64(m_block[i - 1]);
      m_zeros = rank0(m_size);
    }

    u32 zeros() const { return m_zeros; }
    inline u32 rank0(u32 i) const { return i - rank1(i); }
    __attribute__((target("bmi2,popcnt"))) inline u32 rank1(u32 i) const {
      return m_count[i / w] + _mm_popcnt_u64(_bzhi_u64(m_block[i / w], i % w));
    }
  };
}


#line 1 "tools/lower_bound.hpp"



#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 1 "tools/less_by_first.hpp"



#line 5 "tools/less_by_first.hpp"

namespace tools {

  class less_by_first {
  public:
    template <class T1, class T2>
    bool operator()(const ::std::pair<T1, T2>& x, const ::std::pair<T1, T2>& y) const {
      return x.first < y.first;
    }
  };
}


#line 1 "tools/floor_log2.hpp"



#line 1 "tools/bit_width.hpp"



#include <bit>
#line 6 "tools/bit_width.hpp"
#include <type_traits>
#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 1 "tools/is_signed.hpp"



#line 5 "tools/is_signed.hpp"

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

  template <typename T>
  inline constexpr bool is_signed_v = ::tools::is_signed<T>::value;
}


#line 1 "tools/make_unsigned.hpp"



#line 5 "tools/make_unsigned.hpp"

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

  template <typename T>
  using make_unsigned_t = typename ::tools::make_unsigned<T>::type;
}


#line 10 "tools/bit_width.hpp"

namespace tools {
  template <typename T>
  constexpr int bit_width(T) noexcept;

  template <typename T>
  constexpr int bit_width(const T x) noexcept {
    static_assert(::tools::is_integral_v<T> && !::std::is_same_v<::std::remove_cv_t<T>, bool>);
    if constexpr (::tools::is_signed_v<T>) {
      assert(x >= 0);
      return ::tools::bit_width<::tools::make_unsigned_t<T>>(x);
    } else {
      return ::std::bit_width(x);
    }
  }
}


#line 6 "tools/floor_log2.hpp"

namespace tools {
  template <typename T>
  constexpr T floor_log2(T x) noexcept {
    assert(x > 0);
    return ::tools::bit_width(x) - 1;
  }
}


#line 17 "tools/wavelet_matrix.hpp"

namespace tools {
  template <typename T>
  class wavelet_matrix {
  private:
    ::std::vector<::std::pair<T, T>> m_ps;
    ::std::vector<::std::pair<T, ::std::size_t>> m_xs;
    ::std::vector<T> m_ys;
    ::std::vector<::std::size_t> m_is;
    ::std::vector<::tools::bit_vector> m_bvs;

    ::std::size_t iid(const ::std::size_t i) const {
      return ::tools::lower_bound(this->m_xs.begin(), this->m_xs.end(), ::std::make_pair(this->m_ps[i].first, i));
    }
    ::std::size_t xid(const T& x) const {
      return ::tools::lower_bound(this->m_xs.begin(), this->m_xs.end(), ::std::make_pair(x, ::std::size_t{}), ::tools::less_by_first());
    }
    ::std::size_t yid(const T& y) const {
      return ::tools::lower_bound(this->m_ys.begin(), this->m_ys.end(), y);
    }
    ::std::size_t lg() const {
      return this->m_bvs.size();
    }
    bool built() const {
      return this->lg() > 0;
    }

  public:
    wavelet_matrix() = default;
    wavelet_matrix(const ::tools::wavelet_matrix<T>&) = default;
    wavelet_matrix(::tools::wavelet_matrix<T>&&) = default;
    ~wavelet_matrix() = default;
    ::tools::wavelet_matrix<T>& operator=(const ::tools::wavelet_matrix<T>&) = default;
    ::tools::wavelet_matrix<T>& operator=(::tools::wavelet_matrix<T>&&) = default;

    ::std::size_t size() const {
      return this->m_ps.size();
    }

    ::std::size_t add_point(const T& x, const T& y) {
      assert(!this->built());
      this->m_ps.emplace_back(x, y);
      return this->size() - 1;
    }

    ::std::pair<T, T> get_point(const ::std::size_t i) const {
      assert(i < this->size());
      return this->m_ps[i];
    }

    const ::std::vector<::std::pair<T, T>>& points() const {
      return this->m_ps;
    }

    ::std::vector<::std::vector<::std::size_t>> build() {
      assert(!this->built());

      this->m_xs.reserve(this->size());
      for (::std::size_t i = 0; i < this->size(); ++i) {
        this->m_xs.emplace_back(this->m_ps[i].first, i);
      }
      ::std::sort(this->m_xs.begin(), this->m_xs.end());

      this->m_ys.reserve(this->size());
      ::std::transform(this->m_ps.begin(), this->m_ps.end(), ::std::back_inserter(this->m_ys), [](const auto& p) { return p.second; });
      ::std::sort(this->m_ys.begin(), this->m_ys.end());
      this->m_ys.erase(::std::unique(this->m_ys.begin(), this->m_ys.end()), this->m_ys.end());

      const auto n = ::std::max<::std::size_t>(this->size(), 1);
      this->m_bvs.assign(::tools::floor_log2(::std::max<::std::size_t>(this->m_ys.size(), 1)) + 1, ::tools::bit_vector(n));

      ::std::vector<::std::size_t> cur;
      cur.reserve(n);
      ::std::transform(this->m_xs.begin(), this->m_xs.end(), ::std::back_inserter(cur), [&](const auto& p) { return this->yid(this->m_ps[p.second].second); });
      cur.resize(n);
      ::std::vector<::std::size_t> nxt(n);

      auto res = ::std::vector(this->lg() + 1, ::std::vector<::std::size_t>(n));
      ::std::transform(this->m_xs.begin(), this->m_xs.end(), res.back().begin(), [&](const auto& p) { return p.second; });

      for (::std::size_t h = this->lg(); h --> 0;) {
        for (::std::size_t i = 0; i < n; ++i) {
          if ((cur[i] >> h) & 1) {
            this->m_bvs[h].set(i);
          }
        }
        this->m_bvs[h].build();
        ::std::array<::std::size_t, 2> offsets = {0, this->m_bvs[h].zeros()};
        for (::std::size_t i = 0; i < n; ++i) {
          auto& offset = offsets[this->m_bvs[h].get(i)];
          nxt[offset] = cur[i];
          res[h][offset] = res[h + 1][i];
          ++offset;
        }
        ::std::swap(cur, nxt);
      }

      this->m_is = res.front();
      res.pop_back();
      return res;
    }

    ::std::vector<::std::pair<::std::size_t, ::std::size_t>> apply(::std::size_t i) const {
      assert(this->built());
      assert(i < this->size());

      ::std::vector<::std::pair<::std::size_t, ::std::size_t>> res(this->lg());
      i = this->iid(i);
      for (::std::size_t h = this->lg(); h --> 0;) {
        i = this->m_bvs[h].get(i) ? this->m_bvs[h].zeros() + this->m_bvs[h].rank1(i) : this->m_bvs[h].rank0(i);
        res[h] = ::std::make_pair(h, i);
      }
      return res;
    }

    ::std::size_t kth_smallest(const T& l, const T& r, ::std::size_t k) const {
      assert(this->built());
      assert(l <= r);

      auto lid = this->xid(l);
      auto rid = this->xid(r);

      assert(k < rid - lid);

      for (::std::size_t h = this->lg(); h --> 0;) {
        const auto l0 = this->m_bvs[h].rank0(lid);
        const auto r0 = this->m_bvs[h].rank0(rid);
        if (k < r0 - l0) {
          lid = l0;
          rid = r0;
        } else {
          k -= r0 - l0;
          lid += this->m_bvs[h].zeros() - l0;
          rid += this->m_bvs[h].zeros() - r0;
        }
      }

      return this->m_is[lid + k];
    }

    ::std::size_t kth_largest(const T& l, const T& r, const ::std::size_t k) const {
      assert(this->built());
      assert(l <= r);

      const auto lid = this->xid(l);
      const auto rid = this->xid(r);

      assert(k < rid - lid);

      return this->kth_smallest(l, r, rid - lid - k - 1);
    }

    ::std::vector<::std::tuple<::std::size_t, ::std::size_t, ::std::size_t>> range_prod(const T& l, const T& r, const T& u) const {
      assert(this->built());
      assert(l <= r);

      auto lid = this->xid(l);
      auto rid = this->xid(r);
      const auto uid = this->yid(u);

      ::std::vector<::std::tuple<::std::size_t, ::std::size_t, ::std::size_t>> res(this->lg());
      for (::std::size_t h = this->lg(); h --> 0;) {
        const auto l0 = this->m_bvs[h].rank0(lid);
        const auto r0 = this->m_bvs[h].rank0(rid);
        if ((uid >> h) & 1) {
          res[h] = ::std::make_tuple(h, l0, r0);
          lid += this->m_bvs[h].zeros() - l0;
          rid += this->m_bvs[h].zeros() - r0;
        } else {
          res[h] = ::std::make_tuple(h, 0, 0);
          lid = l0;
          rid = r0;
        }
      }
      return res;
    }

    ::std::size_t range_freq(const T& l, const T& r) const {
      assert(this->built());
      assert(l <= r);

      return this->xid(r) - this->xid(l);
    }

    ::std::size_t range_freq(const T& l, const T& r, const T& u) const {
      assert(this->built());
      assert(l <= r);

      auto lid = this->xid(l);
      auto rid = this->xid(r);
      const auto uid = this->yid(u);

      ::std::size_t res = 0;
      for (::std::size_t h = this->lg(); h --> 0;) {
        const auto l0 = this->m_bvs[h].rank0(lid);
        const auto r0 = this->m_bvs[h].rank0(rid);
        if ((uid >> h) & 1) {
          res += r0 - l0;
          lid += this->m_bvs[h].zeros() - l0;
          rid += this->m_bvs[h].zeros() - r0;
        } else {
          lid = l0;
          rid = r0;
        }
      }
      return res;
    }

    ::std::size_t range_freq(const T& l, const T& r, const T& d, const T& u) const {
      assert(this->built());
      assert(l <= r);
      assert(d <= u);

      return this->range_freq(l, r, u) - this->range_freq(l, r, d);
    }

    ::std::optional<T> prev_value(const T& l, const T& r, const T& u) const {
      assert(this->built());
      assert(l <= r);

      const auto k = this->range_freq(l, r, u);
      return k == 0 ? ::std::nullopt : ::std::make_optional(this->m_ps[this->kth_smallest(l, r, k - 1)].second);
    }

    ::std::optional<T> next_value(const T& l, const T& r, const T& d) const {
      assert(this->built());
      assert(l <= r);

      const auto k = this->range_freq(l, r, d);
      return k == this->range_freq(l, r) ? ::std::nullopt : ::std::make_optional(this->m_ps[this->kth_smallest(l, r, k)].second);
    }

    ::std::pair<typename ::std::vector<::std::size_t>::const_iterator, typename ::std::vector<::std::size_t>::const_iterator> prev_points(const T& l, const T& r, const T& u) const {
      assert(this->built());
      assert(l <= r);

      auto lid = this->xid(l);
      auto rid = this->xid(r);
      auto k = this->range_freq(l, r, u);
      if (k == 0) return ::std::make_pair(this->m_is.cend(), this->m_is.cend());
      --k;

      for (::std::size_t h = this->lg(); h --> 0;) {
        const auto l0 = this->m_bvs[h].rank0(lid);
        const auto r0 = this->m_bvs[h].rank0(rid);
        if (k < r0 - l0) {
          lid = l0;
          rid = r0;
        } else {
          k -= r0 - l0;
          lid += this->m_bvs[h].zeros() - l0;
          rid += this->m_bvs[h].zeros() - r0;
        }
      }

      return ::std::make_pair(this->m_is.cbegin() + lid, this->m_is.cbegin() + rid);
    }

    ::std::pair<typename ::std::vector<::std::size_t>::const_iterator, typename ::std::vector<::std::size_t>::const_iterator> next_points(const T& l, const T& r, const T& d) const {
      assert(this->built());
      assert(l <= r);

      auto lid = this->xid(l);
      auto rid = this->xid(r);
      auto k = this->range_freq(l, r, d);
      if (k == rid - lid) return ::std::make_pair(this->m_is.cend(), this->m_is.cend());

      for (::std::size_t h = this->lg(); h --> 0;) {
        const auto l0 = this->m_bvs[h].rank0(lid);
        const auto r0 = this->m_bvs[h].rank0(rid);
        if (k < r0 - l0) {
          lid = l0;
          rid = r0;
        } else {
          k -= r0 - l0;
          lid += this->m_bvs[h].zeros() - l0;
          rid += this->m_bvs[h].zeros() - r0;
        }
      }

      return ::std::make_pair(this->m_is.cbegin() + lid, this->m_is.cbegin() + rid);
    }
  };
}


#line 1 "tools/compress.hpp"



#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);
    }
  }
}


#line 1 "tools/mex.hpp"



#line 10 "tools/mex.hpp"

namespace tools {

  template <typename InputIterator>
  ::std::decay_t<decltype(*::std::declval<InputIterator>())> mex(InputIterator begin, InputIterator end) {
    using T = ::std::decay_t<decltype(*::std::declval<InputIterator>())>;
    const ::std::vector<T> orig(begin, end);
    const ::std::size_t n = orig.size();

    assert(::std::all_of(orig.begin(), orig.end(), [](const auto& o) { return o >= 0; }));

    ::std::vector<bool> exists(n, false);
    for (const ::std::size_t o : orig) {
      if (o < n) {
        exists[o] = true;
      }
    }
    for (::std::size_t i = 0; i < n; ++i) {
      if (!exists[i]) {
        return i;
      }
    }
    return n;
  }
}


#line 13 "tools/range_count_distinct.hpp"

namespace tools {
  class range_count_distinct {
  private:
    ::std::size_t m_size;
    ::tools::wavelet_matrix<::std::size_t> m_wm;

  public:
    range_count_distinct() = default;
    range_count_distinct(const ::tools::range_count_distinct&) = default;
    range_count_distinct(::tools::range_count_distinct&&) = default;
    ~range_count_distinct() = default;
    ::tools::range_count_distinct& operator=(const ::tools::range_count_distinct&) = default;
    ::tools::range_count_distinct& operator=(::tools::range_count_distinct&&) = default;

    template <typename InputIterator>
    range_count_distinct(const InputIterator begin, const InputIterator end) {
      ::std::vector<::std::size_t> seq;
      ::tools::compress(::std::ranges::subrange(begin, end), ::std::back_inserter(seq));
      this->m_size = seq.size();

      const auto NONE = ::std::numeric_limits<::std::size_t>::max();
      ::std::vector<::std::size_t> prev(::tools::mex(seq.begin(), seq.end()), NONE);
      for (::std::size_t i = 0; i < seq.size(); ++i) {
        if (prev[seq[i]] != NONE) {
          this->m_wm.add_point(prev[seq[i]], i);
        }
        prev[seq[i]] = i;
      }

      this->m_wm.build();
    }

    ::std::size_t size() const {
      return this->m_size;
    }

    ::std::size_t query(::std::size_t l, ::std::size_t r) const {
      assert(l <= r && r <= this->size());

      return (r - l) - this->m_wm.range_freq(l, ::std::numeric_limits<::std::size_t>::max(), r);
    }
  };
}


#line 6 "tests/range_count_distinct.test.cpp"

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);

  int N, Q;
  std::cin >> N >> Q;
  std::vector<int> a(N);
  for (auto& a_i : a) std::cin >> a_i;

  tools::range_count_distinct seq(a.begin(), a.end());

  for (int q = 0; q < Q; ++q) {
    int l, r;
    std::cin >> l >> r;
    std::cout << seq.query(l, r) << '\n';
  }

  return 0;
}

Test cases

Env Name Status Elapsed Memory
g++ example_00 :heavy_check_mark: AC 5 ms 4 MB
g++ random_00 :heavy_check_mark: AC 440 ms 96 MB
g++ random_01 :heavy_check_mark: AC 519 ms 112 MB
g++ random_02 :heavy_check_mark: AC 198 ms 9 MB
g++ random_03 :heavy_check_mark: AC 531 ms 120 MB
g++ random_04 :heavy_check_mark: AC 621 ms 120 MB
g++ random_05 :heavy_check_mark: AC 615 ms 65 MB
g++ small_n_00 :heavy_check_mark: AC 67 ms 4 MB
g++ small_n_01 :heavy_check_mark: AC 67 ms 4 MB
g++ small_n_02 :heavy_check_mark: AC 66 ms 3 MB
g++ small_q_00 :heavy_check_mark: AC 224 ms 120 MB
Back to top page