Mo's Algorithm
(misc/mo.hpp)

• View this file on GitHub
• Last update: 2024-01-08 00:27:17+09:00
• Include: #include "misc/mo.hpp"

Description

Mo のアルゴリズム (クエリ平方分割) は，静的な列に対するクエリをオフラインで高速に処理するアルゴリズムである．

Operations

• Mo(int n)
  • 長さ $n$ の列に対するクエリを処理する
  • 時間計算量: $O(1)$
• void query(int l, int r)
  • 区間 $[l, r)$ に対してクエリをする
  • 時間計算量: $O(1)$
• void run(ExL exl, ShL shl, ExR exr, ShR shr, Out out)
  • 以下の関数を引数に取り，クエリを実行する
    • exl: 区間を左に1マス伸ばしたときの状態を更新する
    • shl: 区間を左に1マス縮めたときの状態を更新する
    • exr: 区間を右に1マス伸ばしたときの状態を更新する
    • shr: 区間を右に1マス縮めたときの状態を更新する
    • out: $i$ 番目のクエリの結果を計算する
  • 時間計算量: $O(f(n)n\sqrt{n})$, $f(n)$ は状態の更新にかかる計算量

Verified with

• test/yosupo/static_range_inversions_query.test.cpp

Code

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

class Mo {
   public:
    Mo() = default;
    explicit Mo(int n) : n(n), cnt(0) {}

    void query(int l, int r) { queries.emplace_back(cnt++, l, r); }

    template <typename ExL, typename ShL, typename ExR, typename ShR,
              typename Out>
    void run(ExL exl, ShL shl, ExR exr, ShR shr, Out out) {
        int s = sqrt(n);
        std::ranges::sort(
            queries, {}, [&](auto& q) { return std::make_pair(q.l / s, q.r); });
        int curL = 0, curR = 0;
        for (auto [id, l, r] : queries) {
            while (curL > l) exl(--curL);
            while (curR < r) exr(curR++);
            while (curL < l) shl(curL++);
            while (curR > r) shr(--curR);
            out(id);
        }
    }

   private:
    struct Query {
        int id, l, r;
    };

    int n, cnt;
    std::vector<Query> queries;
};

#line 2 "misc/mo.hpp"
#include <algorithm>
#include <cmath>
#include <vector>

class Mo {
   public:
    Mo() = default;
    explicit Mo(int n) : n(n), cnt(0) {}

    void query(int l, int r) { queries.emplace_back(cnt++, l, r); }

    template <typename ExL, typename ShL, typename ExR, typename ShR,
              typename Out>
    void run(ExL exl, ShL shl, ExR exr, ShR shr, Out out) {
        int s = sqrt(n);
        std::ranges::sort(
            queries, {}, [&](auto& q) { return std::make_pair(q.l / s, q.r); });
        int curL = 0, curR = 0;
        for (auto [id, l, r] : queries) {
            while (curL > l) exl(--curL);
            while (curR < r) exr(curR++);
            while (curL < l) shl(curL++);
            while (curR > r) shr(--curR);
            out(id);
        }
    }

   private:
    struct Query {
        int id, l, r;
    };

    int n, cnt;
    std::vector<Query> queries;
};

Back to top page