algorithm/mo_algorithm.hpp

• View this file on GitHub
• Last update: 2023-05-08 16:51:58+09:00
• Include: #include "algorithm/mo_algorithm.hpp"

Verified with

• test/data_structure/Static_Range_Inversion_Query.test.cpp

Code

#pragma once

#include <algorithm>

#include <cmath>

#include <numeric>

#include <vector>


namespace ebi {

template <class IL, class IR, class DL, class DR, class O>
void mo_algorithm(const int &n, const std::vector<int> &l,
                  const std::vector<int> &r, const IL &insert_left,
                  const IR &insert_right, const DL &delete_left,
                  const DR &delete_right, const O &out) {
    const int q = l.size();
    const int block = n / std::max<int>(1, std::sqrt(n));
    std::vector<int> order(q, 0);
    iota(order.begin(), order.end(), 0);
    std::sort(order.begin(), order.end(), [&](int i, int j) {
        int bi = l[i] / block;
        int bj = l[j] / block;
        return bi != bj ? bi < bj : bi & 1 ? r[i] > r[j] : r[i] < r[j];
    });
    int nl = 0, nr = 0;
    for (auto i : order) {
        while (l[i] < nl) insert_left(--nl);
        while (nr < r[i]) insert_right(nr++);
        while (nl < l[i]) delete_left(nl++);
        while (r[i] < nr) delete_right(--nr);
        out(i);
    }
    return;
}

}  // namespace ebi

#line 2 "algorithm/mo_algorithm.hpp"

#include <algorithm>

#include <cmath>

#include <numeric>

#include <vector>


namespace ebi {

template <class IL, class IR, class DL, class DR, class O>
void mo_algorithm(const int &n, const std::vector<int> &l,
                  const std::vector<int> &r, const IL &insert_left,
                  const IR &insert_right, const DL &delete_left,
                  const DR &delete_right, const O &out) {
    const int q = l.size();
    const int block = n / std::max<int>(1, std::sqrt(n));
    std::vector<int> order(q, 0);
    iota(order.begin(), order.end(), 0);
    std::sort(order.begin(), order.end(), [&](int i, int j) {
        int bi = l[i] / block;
        int bj = l[j] / block;
        return bi != bj ? bi < bj : bi & 1 ? r[i] > r[j] : r[i] < r[j];
    });
    int nl = 0, nr = 0;
    for (auto i : order) {
        while (l[i] < nl) insert_left(--nl);
        while (nr < r[i]) insert_right(nr++);
        while (nl < l[i]) delete_left(nl++);
        while (r[i] < nr) delete_right(--nr);
        out(i);
    }
    return;
}

}  // namespace ebi

Back to top page