Mo's Algorithm
(src/datastructure/Mo.hpp)

• View this file on GitHub
• Last update: 2024-06-01 01:35:37+09:00
• Include: #include "src/datastructure/Mo.hpp"

概要

区間の伸縮による更新が容易にできるときに，事前にクエリの区間を適切に並び替えることで効率的に処理するアルゴリズム．

以下に記す時間計算量においては伸縮 1 回あたりの計算量を $O(1)$ としている．

メンバ関数	効果	時間計算量
Mo(n)	要素数 $n$ の列に関するクエリを処理するとして初期化する．	$O(1)$
add(l, r)	$[l, r)$ についてのクエリを追加する．この追加順はクエリの解答順に則る．	$O(1)$
run(add_left, add_right, del_left, del_right, rem)	伸縮操作の関数及び解答の関数を引数にしてクエリを処理する．	$O(N\sqrt{Q} + Q)$
run(add, del, rem)	伸縮操作の関数 (左右で等価) 及び解答の関数を引数にしてクエリを処理する．	$O(N\sqrt{Q} + Q)$

問題例

• Codeforces Round #221 (Div. 1) D. Tree and Queries
  • 部分木クエリはオイラーツアー順に並べることにより区間クエリになる． 種類数や転倒数に関連するクエリは Mo’s algorithm で扱いやすい．

Links

• Mo’s algorithm とその上位互換の話 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
• Mo’s algorithm - ei1333の日記

Verified with

• test/yosupo/static_range_inversions_query.test.cpp

Code

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

struct Mo {
    Mo(int n) : n(n) {}

    void add(int l, int r) {
        assert(l <= r);
        left.emplace_back(l);
        right.emplace_back(r);
    }

    template <typename AL, typename AR, typename DL, typename DR, typename REM>
    void run(const AL& add_left, const AR& add_right, const DL& del_left, const DR del_right, const REM& rem) {
        int q = left.size(), width = n / std::min(std::max<int>(sqrt(q * 2 / 3), 1), n);
        std::vector<int> order(q);
        std::iota(order.begin(), order.end(), 0);
        std::sort(order.begin(), order.end(), [&](int a, int b) {
            int ablock = left[a] / width, bblock = left[b] / width;
            if (ablock != bblock) return ablock < bblock;
            return (ablock & 1) ? (right[a] > right[b]) : (right[a] < right[b]);
        });

        int l = 0, r = 0;
        for (auto idx : order) {
            while (l > left[idx]) add_left(--l);
            while (r < right[idx]) add_right(r++);
            while (l < left[idx]) del_left(l++);
            while (r > right[idx]) del_right(--r);
            rem(idx);
        }
    }

    template <typename A, typename D, typename REM> void run(const A& add, const D& del, const REM& rem) {
        run(add, add, del, del, rem);
    }

private:
    int n;
    std::vector<int> left, right;
};

#line 2 "src/datastructure/Mo.hpp"
#include <algorithm>
#include <cassert>
#include <cmath>
#include <numeric>
#include <vector>

struct Mo {
    Mo(int n) : n(n) {}

    void add(int l, int r) {
        assert(l <= r);
        left.emplace_back(l);
        right.emplace_back(r);
    }

    template <typename AL, typename AR, typename DL, typename DR, typename REM>
    void run(const AL& add_left, const AR& add_right, const DL& del_left, const DR del_right, const REM& rem) {
        int q = left.size(), width = n / std::min(std::max<int>(sqrt(q * 2 / 3), 1), n);
        std::vector<int> order(q);
        std::iota(order.begin(), order.end(), 0);
        std::sort(order.begin(), order.end(), [&](int a, int b) {
            int ablock = left[a] / width, bblock = left[b] / width;
            if (ablock != bblock) return ablock < bblock;
            return (ablock & 1) ? (right[a] > right[b]) : (right[a] < right[b]);
        });

        int l = 0, r = 0;
        for (auto idx : order) {
            while (l > left[idx]) add_left(--l);
            while (r < right[idx]) add_right(r++);
            while (l < left[idx]) del_left(l++);
            while (r > right[idx]) del_right(--r);
            rem(idx);
        }
    }

    template <typename A, typename D, typename REM> void run(const A& add, const D& del, const REM& rem) {
        run(add, add, del, del, rem);
    }

private:
    int n;
    std::vector<int> left, right;
};

Back to top page