algorithm-dev

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub today2098/algorithm-dev

:heavy_check_mark: Mo's Algorithm（クエリ平方分割）
(algorithm/Others/mo_algorithm.hpp)

概要

区間に対する複数のクエリをまとめて高速に処理するアルゴリズム． 特に，区間 $[l,m)$ と $[m,r)$ の結果をマージして区間 $[l,r)$ の結果を求めることが簡単にできない場合に適している．

Mo’s algorithm を適用するためには，次の3つの条件を満たす必要がある．

アルゴリズムの説明

本アルゴリズムの基本的なアイデアは，クエリを適切な順番に並び替えて，全体での区間の伸縮回数を抑えることにより，計算量を小さくするということである．

アルゴリズムの流れは次の通り． ただし，区間の長さを $N$ ，クエリ数を $Q$ ，$i$ 番目のクエリの区間を $[l_i, r_i)$ とおく．

  1. 区間を幅 $n$ の $N/n$ 個のブロックに分割する．
  2. 各クエリを $l_i$ についてブロックごとに分け，さらにブロック内で $r_i$ についてソートする．
  3. 各クエリを並び替えた順に，区間を伸縮させながら処理する．

このとき，左端，右端の伸縮回数はそれぞれ $Q n$ 回，$N (N/n)$ 回となる． これから，アルゴリズムの計算量は，区間伸縮1回あたりの計算量を $\mathcal{O}(\alpha)$ とすると，クエリの並び替えが $\mathcal{O}(Q \log{Q})$ ，すべてのクエリ処理が $\mathcal{O}(\alpha (Q n + N (N/n)))$ となる．

ここで最適な $n$ の値を決めることがミソである． 本実装では $n = N / \sqrt{Q}$ としており，全体の計算量は $\mathcal{O}(Q \log{Q} + \alpha N \sqrt{Q})$ になる．

参考文献

  1. ageprocpp. “Mo’s algorithm(クエリ平方分割)の話”. Qiita. https://qiita.com/ageprocpp/items/34121c58e571ea8c4023.
  2. ei1333. “Mo’s algorithm”. HatenaBlog. https://ei1333.hateblo.jp/entry/2017/09/11/211011.
  3. strangerxxx. “Mo’s Algorithmのイメージを視覚的に理解したい”. HatenaBlog. https://strangerxxx.hateblo.jp/entry/20230314/1678795200.
  4. ふくぶちょ〜. “Mo′s Algorithm(クエリ平方分割)について”. note. https://note.com/fukubutyo1729/n/n597953224d3a.
  5. “Mo’s algorithm”. アルゴリズムとデータ構造大全. https://take44444.github.io/Algorithm-Book/range/mo/main.html.

問題

Verified with

Code

#ifndef ALGORITHM_MO_ALGORITHM_HPP
#define ALGORITHM_MO_ALGORITHM_HPP 1

/**
 * @brief Mo's Algorithm（クエリ平方分割）
 * @docs docs/Others/mo_algorithm.md
 */

#include <algorithm>
#include <cassert>
#include <cmath>
#include <tuple>
#include <vector>

namespace algorithm {

// Mo's Algorithm（クエリ平方分割）.
class Mo {
    int m_len;                                          // m_len:=(区間の長さ).
    int m_q;                                            // m_q:=(クエリ数).
    std::vector<std::tuple<int, int, int> > m_queries;  // m_queries[i]:=(i番目の区間クエリ). tuple of (left, right, index).

    void sort_queries() {
        if(m_q == 0) return;
        const int width = std::max(m_len / (int)std::sqrt(m_q), 1);  // width:=N/√Q.
        std::sort(m_queries.begin(), m_queries.end(), [&width](const std::tuple<int, int, int> &a, const std::tuple<int, int, int> &b) -> bool {
            const auto &[al, ar, _] = a;
            const auto &[bl, br, __] = b;
            int a_block = al / width, b_block = bl / width;
            if(a_block == b_block) return (a_block & 1 ? ar > br : ar < br);
            return a_block < b_block;
        });
    }

public:
    Mo() : Mo(0) {}
    explicit Mo(size_t n) : m_len(n), m_q(0) {}
    explicit Mo(size_t n, size_t q) : Mo(n) {
        m_queries.reserve(q);
    }

    // 区間[l,r)についてのクエリを追加する．
    void insert(int l, int r) {
        assert(0 <= l and l < r and r <= m_len);
        m_queries.emplace_back(l, r, m_q++);
    }
    // 各クエリを実行する．O(Q*logQ+α*N*√Q).
    template <class F1, class F2, class F3>
    void execute(const F1 &add, const F2 &del, const F3 &solve) { execute(add, del, add, del, solve); }
    template <class F1, class F2, class F3, class F4, class F5>
    void execute(const F1 &add_l, const F2 &del_l, const F3 &add_r, const F4 &del_r, const F5 &solve) {
        sort_queries();
        int l = 0, r = 0;
        for(const auto &[nl, nr, idx] : m_queries) {
            while(nl < l) add_l(--l);
            while(r < nr) add_r(r++);
            while(l < nl) del_l(l++);
            while(nr < r) del_r(--r);
            solve(idx);
        }
    }
    void reset() {
        m_queries.clear();
        m_q = 0;
    }
};

}  // namespace algorithm

#endif
#line 1 "algorithm/Others/mo_algorithm.hpp"



/**
 * @brief Mo's Algorithm（クエリ平方分割）
 * @docs docs/Others/mo_algorithm.md
 */

#include <algorithm>
#include <cassert>
#include <cmath>
#include <tuple>
#include <vector>

namespace algorithm {

// Mo's Algorithm（クエリ平方分割）.
class Mo {
    int m_len;                                          // m_len:=(区間の長さ).
    int m_q;                                            // m_q:=(クエリ数).
    std::vector<std::tuple<int, int, int> > m_queries;  // m_queries[i]:=(i番目の区間クエリ). tuple of (left, right, index).

    void sort_queries() {
        if(m_q == 0) return;
        const int width = std::max(m_len / (int)std::sqrt(m_q), 1);  // width:=N/√Q.
        std::sort(m_queries.begin(), m_queries.end(), [&width](const std::tuple<int, int, int> &a, const std::tuple<int, int, int> &b) -> bool {
            const auto &[al, ar, _] = a;
            const auto &[bl, br, __] = b;
            int a_block = al / width, b_block = bl / width;
            if(a_block == b_block) return (a_block & 1 ? ar > br : ar < br);
            return a_block < b_block;
        });
    }

public:
    Mo() : Mo(0) {}
    explicit Mo(size_t n) : m_len(n), m_q(0) {}
    explicit Mo(size_t n, size_t q) : Mo(n) {
        m_queries.reserve(q);
    }

    // 区間[l,r)についてのクエリを追加する．
    void insert(int l, int r) {
        assert(0 <= l and l < r and r <= m_len);
        m_queries.emplace_back(l, r, m_q++);
    }
    // 各クエリを実行する．O(Q*logQ+α*N*√Q).
    template <class F1, class F2, class F3>
    void execute(const F1 &add, const F2 &del, const F3 &solve) { execute(add, del, add, del, solve); }
    template <class F1, class F2, class F3, class F4, class F5>
    void execute(const F1 &add_l, const F2 &del_l, const F3 &add_r, const F4 &del_r, const F5 &solve) {
        sort_queries();
        int l = 0, r = 0;
        for(const auto &[nl, nr, idx] : m_queries) {
            while(nl < l) add_l(--l);
            while(r < nr) add_r(r++);
            while(l < nl) del_l(l++);
            while(nr < r) del_r(--r);
            solve(idx);
        }
    }
    void reset() {
        m_queries.clear();
        m_q = 0;
    }
};

}  // namespace algorithm
Back to top page