Mo's algorithm (tools/mo.hpp)

Assume the following situation.

$Q$ queries are given.
The $i$-th query asks you about some kind of value for the range $[l_i, r_i)$. $(0 \leq l_i \leq r_i \leq N)$
Some kind of state is uniquely determined from a range $[l, r)$.
If you know the state uniquely determined from $[l - 1, r)$, you can calculate the state uniquely determined from $[l, r)$ in $\alpha$ time.
If you know the state uniquely determined from $[l + 1, r)$, you can calculate the state uniquely determined from $[l, r)$ in $\alpha$ time.
If you know the state uniquely determined from $[l, r - 1)$, you can calculate the state uniquely determined from $[l, r)$ in $\alpha$ time.
If you know the state uniquely determined from $[l, r + 1)$, you can calculate the state uniquely determined from $[l, r)$ in $\alpha$ time.
If you know the state uniquely determined from $[l_i, r_i)$, you can answer the $i$-th query in $\beta$ time.

In this situation, Mo’s algorithm can answer $Q$ queries in $O(\alpha N \sqrt{Q} + \beta Q)$ time.

References

License

Author

anqooqie

Constructor

mo mo(std::size_t N, std::size_t Q);

It creates a storage for queries.

Constraints

None

Time Complexity

$O\left(\log \frac{N}{\sqrt{Q}} + \sqrt{Q}\right)$

add_query

void mo.add_query(std::size_t l, std::size_t r);

It adds a query for $[l, r)$ to the storage.

Constraints

$0 \leq l \leq r \leq N$

Time Complexity

$O(1)$ amortized

run

template <typename AL, typename AR, typename DL, typename DR, typename F>
void mo.run(AL add_left, AR add_right, DL delete_left, DR delete_right, F run_query);

It runs Mo’s algorithm. When run_query(i) is invoked, you can answer the $i$-th query by using the state uniquely determined from $[l_i, r_i)$.

Constraints

add_left(std::size_t) is invocable.
add_right(std::size_t) is invocable.
delete_left(std::size_t) is invocable.
delete_right(std::size_t) is invocable.
run_query(std::size_t) is invocable.
When add_left(i) is invoked, you have to update the state from one uniquely determined from $[l, r)$ to one uniquely determined from $[l - 1, r)$. (You may utilize the contract that $i = l - 1$ holds.)
When add_right(i) is invoked, you have to update the state from one uniquely determined from $[l, r)$ to one uniquely determined from $[l, r + 1)$. (You may utilize the contract that $i = r$ holds.)
When delete_left(i) is invoked, you have to update the state from one uniquely determined from $[l, r)$ to one uniquely determined from $[l + 1, r)$. (You may utilize the contract that $i = l$ holds.)
When delete_right(i) is invoked, you have to update the state from one uniquely determined from $[l, r)$ to one uniquely determined from $[l, r - 1)$. (You may utilize the contract that $i = r - 1$ holds.)

Time Complexity

$O(\alpha N \sqrt{Q} + \beta Q)$ where $\alpha$ is the time to run add_left, add_right, delete_left and delete_right, and $\beta$ is the time to run run_query.

Depends on

Verified with

tests/mo.test.cpp

Code

#ifndef TOOLS_MO_HPP
#define TOOLS_MO_HPP

#include <cstddef>
#include <vector>
#include <tuple>
#include <algorithm>
#include <cassert>
#include "tools/floor_sqrt.hpp"
#include "tools/ceil.hpp"
#include "tools/less_by_get.hpp"
#include "tools/greater_by_get.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);
        }
      }
    }
  };
}

#endif

#line 1 "tools/mo.hpp"



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