Halc's Library

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

---

Project maintained by halc-git Hosted on GitHub Pages — Theme by mattgraham

Mo's Algorithm
(Misc/Mo.hpp)

• View this file on GitHub
• Last update: 2024-05-08 20:46:35+09:00
• Include: #include "Misc/Mo.hpp"

関数の設定

struct M{
    using T;
    static void add_left(int pos) {}
    static void delete_left(int pos) {}
    static void add_right(int pos) {}
    static void delete_right(int pos) {}
    static T rem() {}
};

• T: 答えの型です。
• void add_left(int pos): pos 番目の要素を左に追加するときの処理です。
• void delete_left(int pos): pos 番目の要素を左から削除するときの処理です。
• void add_right(int pos): pos 番目の要素を右に追加するときの処理です。
• void delete_right(int pos): pos 番目の要素を右から削除するときの処理です。
• T rem(): 現時点でのクエリに対する答えを返す処理です。

Verified with

• Verify/verify-yosupo-datastructure/static_range_inversions_query-mo.test.cpp
• Verify/verify-yuki/2338.test.cpp

Code

#pragma once
#include <cmath>
#include <numeric>
#include <vector>
template <class M>
struct Mo {
    using T = typename M::T;
    int32_t backet;
    std::vector<int32_t> left, right, order;
    Mo(int32_t N, int32_t Q) {
        order.resize(Q);
        backet = std::max<int32_t>(
            1, (double)(N) / std::max<double>(1, std::sqrt(Q * 2.0 / 3)));
        std::iota(order.begin(), order.end(), 0);
    }
    void add_query(int32_t lf, int32_t ri) {
        left.emplace_back(lf);
        right.emplace_back(ri);
    }
    std::vector<T> run() {
        std::vector<T> answer(order.size());
        sort(order.begin(), order.end(), [&](int32_t a, int32_t b) {
            int32_t ab = left[a] / backet, bb = left[b] / backet;
            if (ab != bb) return ab < bb;
            if (ab & 1) return right[a] < right[b];
            return right[a] > right[b];
        });
        int32_t nl = 0, nr = 0;
        for (int32_t i : order) {
            while (nl > left[i]) {
                nl--;
                M::add_left(nl);
            }
            while (right[i] > nr) {
                M::add_right(nr);
                nr++;
            }
            while (nl < left[i]) {
                M::delete_left(nl);
                nl++;
            }
            while (right[i] < nr) {
                nr--;
                M::delete_right(nr);
            }
            answer[i] = M::rem();
        }
        return answer;
    }
};

#line 2 "Misc/Mo.hpp"
#include <cmath>
#include <numeric>
#include <vector>
template <class M>
struct Mo {
    using T = typename M::T;
    int32_t backet;
    std::vector<int32_t> left, right, order;
    Mo(int32_t N, int32_t Q) {
        order.resize(Q);
        backet = std::max<int32_t>(
            1, (double)(N) / std::max<double>(1, std::sqrt(Q * 2.0 / 3)));
        std::iota(order.begin(), order.end(), 0);
    }
    void add_query(int32_t lf, int32_t ri) {
        left.emplace_back(lf);
        right.emplace_back(ri);
    }
    std::vector<T> run() {
        std::vector<T> answer(order.size());
        sort(order.begin(), order.end(), [&](int32_t a, int32_t b) {
            int32_t ab = left[a] / backet, bb = left[b] / backet;
            if (ab != bb) return ab < bb;
            if (ab & 1) return right[a] < right[b];
            return right[a] > right[b];
        });
        int32_t nl = 0, nr = 0;
        for (int32_t i : order) {
            while (nl > left[i]) {
                nl--;
                M::add_left(nl);
            }
            while (right[i] > nr) {
                M::add_right(nr);
                nr++;
            }
            while (nl < left[i]) {
                M::delete_left(nl);
                nl++;
            }
            while (right[i] < nr) {
                nr--;
                M::delete_right(nr);
            }
            answer[i] = M::rem();
        }
        return answer;
    }
};

Back to top page