Mo's algorithm
(Mylib/Algorithm/mo_algorithm.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

• MoAlgorithm
• add(int l, int r)
  • クエリ[l, r)を追加する。
• build()
• run()
• make_mo

Requirements

• append(int i, int d)
  • i番目の要素を追加する操作。
  • d = -1で左端に追加、d = 1で右端に追加。
• remove(int i, int d)
  • i番目の要素を削除する操作。
  • d = -1で左端を削除、d = 1で右端を削除。
• query(int i)
  • i番目のクエリを処理する操作。
• 必ずadd, build, runの順で実行する。

Notes

Problems

• Yandex.Algorithm 2011: Round 2 D. Powerful array (出現数)
• SPOJ DQUERY (種類数)
• 第3回 ドワンゴからの挑戦状 本選 B - ニワンゴくんの約数 (積の約数の個数)
• Codeforces Round #221 (Div. 1) D. Tree and Queries (部分木 / 出現数k以上の種類数)
• Unique Art (出現数1の種類数)

References

• https://ei1333.hateblo.jp/entry/2017/09/11/211011
• https://snuke.hatenablog.com/entry/2016/07/01/000000
• https://www.hamayanhamayan.com/entry/2017/04/18/012937

Required by

• Range inversions query (Mylib/Typical/range_inversions_query.cpp)

Verified with

• test/aoj/0425/main.test.cpp
• test/yosupo-judge/static_range_inversions_query/main.test.cpp

Code

#pragma once
#include <algorithm>
#include <cassert>
#include <cmath>
#include <vector>

namespace haar_lib {
  template <typename AppendLeft, typename AppendRight, typename RemoveLeft, typename RemoveRight, typename Query>
  class mo_algorithm {
    int N_, Q_, index_, width_;
    std::vector<int> left_, right_, ord_;

    AppendLeft append_left_;
    AppendRight append_right_;
    RemoveLeft remove_left_;
    RemoveRight remove_right_;
    Query query_;

    bool is_built_ = false;

  public:
    mo_algorithm() {}
    mo_algorithm(
        int N, int Q,
        const AppendLeft &append_left, const AppendRight &append_right,
        const RemoveLeft &remove_left, const RemoveRight &remove_right,
        const Query &query) : N_(N), Q_(Q), index_(0), width_(std::sqrt(N)), left_(Q), right_(Q), ord_(Q), append_left_(append_left), append_right_(append_right), remove_left_(remove_left), remove_right_(remove_right), query_(query) {}

    // [l, r)
    void add(int l, int r) {
      left_[index_]  = l;
      right_[index_] = r;
      ord_[index_]   = index_;
      ++index_;
    }

    void run() {
      std::sort(
          ord_.begin(), ord_.end(),
          [&](int i, int j) {
            const int a = left_[i] / width_, b = left_[j] / width_;
            if (a == b) {
              if (a & 1)
                return right_[i] < right_[j];
              else
                return right_[i] > right_[j];
            } else {
              return a < b;
            }
          });

      int q = 0;
      int l = left_[ord_[0]], r = left_[ord_[0]];

      for (int i = 0; i < Q_; ++i) {
        int id = ord_[q++];

        while (l != left_[id] or r != right_[id]) {
          if (l > left_[id]) append_left_(--l);
          if (l < left_[id]) remove_left_(l++);
          if (r < right_[id]) append_right_(r++);
          if (r > right_[id]) remove_right_(--r);
        }

        query_(id);
      }
    }
  };
}  // namespace haar_lib

#line 2 "Mylib/Algorithm/mo_algorithm.cpp"
#include <algorithm>
#include <cassert>
#include <cmath>
#include <vector>

namespace haar_lib {
  template <typename AppendLeft, typename AppendRight, typename RemoveLeft, typename RemoveRight, typename Query>
  class mo_algorithm {
    int N_, Q_, index_, width_;
    std::vector<int> left_, right_, ord_;

    AppendLeft append_left_;
    AppendRight append_right_;
    RemoveLeft remove_left_;
    RemoveRight remove_right_;
    Query query_;

    bool is_built_ = false;

  public:
    mo_algorithm() {}
    mo_algorithm(
        int N, int Q,
        const AppendLeft &append_left, const AppendRight &append_right,
        const RemoveLeft &remove_left, const RemoveRight &remove_right,
        const Query &query) : N_(N), Q_(Q), index_(0), width_(std::sqrt(N)), left_(Q), right_(Q), ord_(Q), append_left_(append_left), append_right_(append_right), remove_left_(remove_left), remove_right_(remove_right), query_(query) {}

    // [l, r)
    void add(int l, int r) {
      left_[index_]  = l;
      right_[index_] = r;
      ord_[index_]   = index_;
      ++index_;
    }

    void run() {
      std::sort(
          ord_.begin(), ord_.end(),
          [&](int i, int j) {
            const int a = left_[i] / width_, b = left_[j] / width_;
            if (a == b) {
              if (a & 1)
                return right_[i] < right_[j];
              else
                return right_[i] > right_[j];
            } else {
              return a < b;
            }
          });

      int q = 0;
      int l = left_[ord_[0]], r = left_[ord_[0]];

      for (int i = 0; i < Q_; ++i) {
        int id = ord_[q++];

        while (l != left_[id] or r != right_[id]) {
          if (l > left_[id]) append_left_(--l);
          if (l < left_[id]) remove_left_(l++);
          if (r < right_[id]) append_right_(r++);
          if (r > right_[id]) remove_right_(--r);
        }

        query_(id);
      }
    }
  };
}  // namespace haar_lib

Back to top page