proconlib

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

View the Project on GitHub anqooqie/proconlib

:heavy_check_mark: tests/mo.test.cpp

Depends on

Code

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

#include <iostream>
#include <vector>
#include "tools/mo.hpp"
#include "tools/unordered_map.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::mo mo(N, Q);
  std::vector<int> queries(Q);
  for (int i = 0; i < Q; ++i) {
    int l, r;
    std::cin >> l >> r;
    mo.add_query(l, r);
    std::cin >> queries[i];
  }

  tools::unordered_map<int, int> freq;
  const auto add = [&](const int i) { ++freq[a[i]]; };
  const auto remove = [&](const int i) { --freq[a[i]]; };
  ::std::vector<int> answers(Q);
  mo.run(add, add, remove, remove, [&](const int q) {
    if (const auto it = freq.find(queries[q]); it != freq.end()) {
      answers[q] = it->second;
    } else {
      answers[q] = 0;
    }
  });

  for (const auto& answer : answers) {
    std::cout << answer << '\n';
  }
  return 0;
}

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

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



#include <cstddef>
#line 6 "tools/mo.hpp"
#include <tuple>
#include <algorithm>
#include <cassert>
#line 1 "tools/floor_sqrt.hpp"



#line 5 "tools/floor_sqrt.hpp"

namespace tools {

  template <typename T>
  T floor_sqrt(const T n) {
    assert(n >= 0);

    T ok = 0;
    T ng;
    for (ng = 1; ng <= n / ng; ng *= 2);

    while (ng - ok > 1) {
      const T mid = ok + (ng - ok) / 2;
      if (mid <= n / mid) {
        ok = mid;
      } else {
        ng = mid;
      }
    }

    return ok;
  }
}


#line 1 "tools/ceil.hpp"



#line 5 "tools/ceil.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_unsigned.hpp"



#line 5 "tools/is_unsigned.hpp"

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

  template <typename T>
  inline constexpr bool is_unsigned_v = ::tools::is_unsigned<T>::value;
}


#line 8 "tools/ceil.hpp"

namespace tools {
  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> ceil(const M x, const N y) noexcept {
    assert(y != 0);
    if (y >= 0) {
      if (x > 0) {
        return (x - 1) / y + 1;
      } else {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      }
    } else {
      if (x >= 0) {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      } else {
        return (x + 1) / y + 1;
      }
    }
  }
}


#line 1 "tools/less_by_get.hpp"



#line 6 "tools/less_by_get.hpp"

namespace tools {

  template <::std::size_t I>
  struct less_by_get {
    template <class T>
    bool operator()(const T& x, const T& y) const {
      return ::std::get<I>(x) < ::std::get<I>(y);
    }
  };
}


#line 1 "tools/greater_by_get.hpp"



#line 6 "tools/greater_by_get.hpp"

namespace tools {

  template <::std::size_t I>
  struct greater_by_get {
    template <class T>
    bool operator()(const T& x, const T& y) const {
      return ::std::get<I>(x) > ::std::get<I>(y);
    }
  };
}


#line 13 "tools/mo.hpp"

namespace tools {
  class mo {
  private:
    ::std::size_t m_query_count;
    ::std::size_t m_bucket_size;
    ::std::vector<::std::vector<::std::tuple<::std::size_t, ::std::size_t, ::std::size_t>>> m_buckets;

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

    mo(const ::std::size_t n, const ::std::size_t q) :
      m_query_count(0),
      m_bucket_size(::std::clamp<::std::size_t>(::tools::floor_sqrt(3 * (n + 1) * (n + 1) / (2 * (q + 1))), 1, n + 1)),
      m_buckets(::tools::ceil(n + 1, this->m_bucket_size)) {
    }

    void add_query(const ::std::size_t l, const ::std::size_t r) {
      assert(l <= r);
      this->m_buckets[l / this->m_bucket_size].emplace_back(this->m_query_count, l, r);
      ++this->m_query_count;
    }

    template <typename AL, typename AR, typename DL, typename DR, typename F>
    void run(const AL& add_left, const AR& add_right, const DL& delete_left, const DR& delete_right, const F& run_query) {
      ::std::size_t l = 0;
      ::std::size_t r = 0;
      for (::std::size_t i = 0; i < this->m_buckets.size(); ++i) {
        if (i % 2 == 0) {
          ::std::sort(this->m_buckets[i].begin(), this->m_buckets[i].end(), ::tools::less_by_get<2>());
        } else {
          ::std::sort(this->m_buckets[i].begin(), this->m_buckets[i].end(), ::tools::greater_by_get<2>());
        }
        for (const auto& [qi, ql, qr] : this->m_buckets[i]) {
          for (; ql < l; --l) add_left(l - 1);
          for (; r < qr; ++r) add_right(r);
          for (; l < ql; ++l) delete_left(l);
          for (; qr < r; --r) delete_right(r - 1);
          run_query(qi);
        }
      }
    }
  };
}


#line 1 "tools/unordered_map.hpp"



#include <functional>
#include <utility>
#line 7 "tools/unordered_map.hpp"
#include <ext/pb_ds/assoc_container.hpp>

namespace tools {

  template <typename Key, typename T, typename Hash = ::std::hash<Key>>
  class unordered_map : public ::__gnu_pbds::gp_hash_table<Key, T, Hash> {
  public:
    using ::__gnu_pbds::gp_hash_table<Key, T, Hash>::gp_hash_table;

    template <typename... Args>
    auto emplace(Args&&... args) {
      return this->insert(::std::make_pair(::std::forward<Args>(args)...));
    }

    template <typename M>
    auto insert_or_assign(const Key& k, M&& obj) {
      if (auto it = this->find(k); it != this->end()) {
        it->second = obj;
        return ::std::make_pair(it, false);
      } else {
        return this->emplace(k, obj);
      }
    }
  };
}


#line 7 "tests/mo.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::mo mo(N, Q);
  std::vector<int> queries(Q);
  for (int i = 0; i < Q; ++i) {
    int l, r;
    std::cin >> l >> r;
    mo.add_query(l, r);
    std::cin >> queries[i];
  }

  tools::unordered_map<int, int> freq;
  const auto add = [&](const int i) { ++freq[a[i]]; };
  const auto remove = [&](const int i) { --freq[a[i]]; };
  ::std::vector<int> answers(Q);
  mo.run(add, add, remove, remove, [&](const int q) {
    if (const auto it = freq.find(queries[q]); it != freq.end()) {
      answers[q] = it->second;
    } else {
      answers[q] = 0;
    }
  });

  for (const auto& answer : answers) {
    std::cout << answer << '\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 453 ms 22 MB
g++ random_01 :heavy_check_mark: AC 948 ms 22 MB
g++ random_02 :heavy_check_mark: AC 242 ms 21 MB
g++ random_03 :heavy_check_mark: AC 625 ms 26 MB
g++ random_04 :heavy_check_mark: AC 1092 ms 25 MB
g++ random_05 :heavy_check_mark: AC 1689 ms 35 MB
g++ small_n_00 :heavy_check_mark: AC 111 ms 19 MB
g++ small_n_01 :heavy_check_mark: AC 114 ms 23 MB
g++ small_n_02 :heavy_check_mark: AC 114 ms 24 MB
g++ small_q_00 :heavy_check_mark: AC 33 ms 5 MB
Back to top page