Mo's Algorithm (other/mo.hpp)

Description

Mo’s algorithm processes offline range queries efficiently by reordering queries to minimize the number of element additions/removals.

Operations

Mo(int n, const vector<pair<int, int>> &qs)
- Constructs Mo’s algorithm instance with array size n and queries qs
- Each query is a pair (l, r) representing range [l, r)
- Time complexity: $\mathcal O(q \log q)$
void run(Eval eval, AL add_l, DL del_l, AR add_r, DR del_r)
- Processes queries with separate callbacks for adding/removing elements on left and right
- eval(i) is called when query i should be evaluated
- add_l(i) / del_l(i) are called when adding/removing element at index i from the left
- add_r(i) / del_r(i) are called when adding/removing element at index i from the right
- Time complexity: $\mathcal O(n \sqrt{q})$
void run(Eval eval, Add add, Del del)
- Processes queries with symmetric callbacks for adding/removing elements
- eval(i) is called when query i should be evaluated
- add(i) / del(i) are called when adding/removing element at index i
- Time complexity: $\mathcal O(n \sqrt{q})$

Required by

Mo's Algorithm on Tree (tree/mo_on_tree.hpp)

Verified with

test/yosupo/ds/static_range_inversions_query.test.cpp

Code

#pragma once

struct Mo {
    int q;
    const int B;
    vector<int> qi;
    vector<pair<int, int>> qs;

    int l = 0, r = 0;

    Mo(int n, const vector<pair<int, int>> &_qs) :
        q((int)_qs.size()), B(blk_sz(n, q)), qi(q), qs(_qs) {
        iota(begin(qi), end(qi), 0);
        sort(begin(qi), end(qi), [&](int i, int j) {
            auto [li, ri] = qs[i];
            auto [lj, rj] = qs[j];
            int bi = li / B, bj = lj / B;
            if (bi != bj) return bi < bj;
            if (ri != rj) return (bi & 1) != (ri < rj);
            return li < lj;
        });
    }

    template<class Eval, class AL, class DL, class AR, class DR>
    void run(Eval eval, AL add_l, DL del_l, AR add_r, DR del_r) {
        for (int i : qi) {
            auto [ql, qr] = qs[i];
            while (ql < l) add_l(--l);
            while (r < qr) add_r(r++);
            while (l < ql) del_l(l++);
            while (qr < r) del_r(--r);
            eval(i);
        }
    }
    template<class Eval, class Add, class Del>
    void run(Eval eval, Add add, Del del) {
        run(eval, add, del, add, del);
    }

  private:
    static int blk_sz(int n, int q) {
        return max(1, int(n / max<double>(1, sqrt(q * 2.0 / 3.0))));
    }
};

#line 2 "other/mo.hpp"

struct Mo {
    int q;
    const int B;
    vector<int> qi;
    vector<pair<int, int>> qs;

    int l = 0, r = 0;

    Mo(int n, const vector<pair<int, int>> &_qs) :
        q((int)_qs.size()), B(blk_sz(n, q)), qi(q), qs(_qs) {
        iota(begin(qi), end(qi), 0);
        sort(begin(qi), end(qi), [&](int i, int j) {
            auto [li, ri] = qs[i];
            auto [lj, rj] = qs[j];
            int bi = li / B, bj = lj / B;
            if (bi != bj) return bi < bj;
            if (ri != rj) return (bi & 1) != (ri < rj);
            return li < lj;
        });
    }

    template<class Eval, class AL, class DL, class AR, class DR>
    void run(Eval eval, AL add_l, DL del_l, AR add_r, DR del_r) {
        for (int i : qi) {
            auto [ql, qr] = qs[i];
            while (ql < l) add_l(--l);
            while (r < qr) add_r(r++);
            while (l < ql) del_l(l++);
            while (qr < r) del_r(--r);
            eval(i);
        }
    }
    template<class Eval, class Add, class Del>
    void run(Eval eval, Add add, Del del) {
        run(eval, add, del, add, del);
    }

  private:
    static int blk_sz(int n, int q) {
        return max(1, int(n / max<double>(1, sqrt(q * 2.0 / 3.0))));
    }
};