m1une's library

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

View on GitHub

:warning: Offline Algorithms All
(algo/offline/all.hpp)

Overview

algo/offline/all.hpp includes offline query-processing techniques. The public namespace is m1une::algo.

Included Headers

Header Contents
algo/offline/mo.hpp Mo’s algorithm for reordering static range queries.
algo/offline/parallel_binary_search.hpp Parallel binary search for batched monotone prefix decisions.
algo/offline/cdq_divide_and_conquer.hpp Generic CDQ divide-and-conquer recursion helper.

Depends on

Required by

Code

#ifndef M1UNE_ALGO_OFFLINE_ALL_HPP
#define M1UNE_ALGO_OFFLINE_ALL_HPP 1

#include "cdq_divide_and_conquer.hpp"
#include "mo.hpp"
#include "parallel_binary_search.hpp"

#endif  // M1UNE_ALGO_OFFLINE_ALL_HPP
#line 1 "algo/offline/all.hpp"



#line 1 "algo/offline/cdq_divide_and_conquer.hpp"



#include <cassert>

namespace m1une {
namespace algo {

template <class SolveCross>
void cdq_divide_and_conquer(int left, int right, SolveCross solve_cross) {
    assert(left <= right);

    auto dfs = [&](auto& self, int l, int r) -> void {
        if (r - l <= 1) return;
        const int middle = l + (r - l) / 2;
        self(self, l, middle);
        self(self, middle, r);
        solve_cross(l, middle, r);
    };
    dfs(dfs, left, right);
}

template <class SolveCross>
void cdq_divide_and_conquer(int n, SolveCross solve_cross) {
    assert(0 <= n);
    cdq_divide_and_conquer(0, n, solve_cross);
}

}  // namespace algo
}  // namespace m1une


#line 1 "algo/offline/mo.hpp"



#include <algorithm>
#line 6 "algo/offline/mo.hpp"
#include <cmath>
#include <numeric>
#include <vector>

namespace m1une {
namespace algo {

// Offline Mo's algorithm for half-open array ranges.
struct Mo {
    struct Query {
        int left;
        int right;
        int id;
    };

   private:
    int _n;
    std::vector<Query> _queries;

   public:
    Mo() : _n(0) {}

    explicit Mo(int n) : _n(n) {
        assert(0 <= n);
    }

    int size() const {
        return _n;
    }

    int query_count() const {
        return int(_queries.size());
    }

    bool empty() const {
        return _queries.empty();
    }

    const std::vector<Query>& queries() const {
        return _queries;
    }

    void reserve(int query_capacity) {
        assert(0 <= query_capacity);
        _queries.reserve(query_capacity);
    }

    void clear() {
        _queries.clear();
    }

    // Adds [left, right) and returns its insertion-order ID.
    int add_query(int left, int right) {
        assert(0 <= left && left <= right && right <= _n);
        int id = query_count();
        _queries.push_back(Query{left, right, id});
        return id;
    }

    // Returns query IDs in Mo order. A non-positive block size selects one
    // automatically.
    std::vector<int> order(int block_size = 0) const {
        int query_size = query_count();
        std::vector<int> result(query_size);
        std::iota(result.begin(), result.end(), 0);
        if (query_size == 0) return result;

        if (block_size <= 0) {
            block_size = std::max(1, int(_n / std::sqrt(static_cast<double>(query_size))));
        }

        std::sort(result.begin(), result.end(), [&](int first, int second) {
            const Query& a = _queries[first];
            const Query& b = _queries[second];
            int first_block = a.left / block_size;
            int second_block = b.left / block_size;
            if (first_block != second_block) {
                return first_block < second_block;
            }
            if (first_block & 1) return a.right > b.right;
            return a.right < b.right;
        });
        return result;
    }

    // Maintains [left, right). Each movement callback receives the array index
    // being inserted or erased. `answer(query_id)` stores or reports a result.
    template <class AddLeft, class AddRight, class RemoveLeft, class RemoveRight, class Answer>
    void run(AddLeft add_left, AddRight add_right, RemoveLeft remove_left, RemoveRight remove_right, Answer answer,
             int block_size = 0) const {
        int left = 0;
        int right = 0;
        for (int query_index : order(block_size)) {
            const Query& query = _queries[query_index];
            while (query.left < left) add_left(--left);
            while (right < query.right) add_right(right++);
            while (left < query.left) remove_left(left++);
            while (query.right < right) remove_right(--right);
            answer(query.id);
        }
    }

    // Convenience overload for statistics whose update is independent of
    // which side moves.
    template <class Add, class Remove, class Answer>
    void run(Add add, Remove remove, Answer answer, int block_size = 0) const {
        run(add, add, remove, remove, answer, block_size);
    }
};

}  // namespace algo
}  // namespace m1une


#line 1 "algo/offline/parallel_binary_search.hpp"



#line 6 "algo/offline/parallel_binary_search.hpp"

namespace m1une {
namespace algo {

template <class Apply, class Check, class Reset>
std::vector<int> parallel_binary_search(
    int query_count,
    int event_count,
    Apply apply,
    Check check,
    Reset reset
) {
    assert(0 <= query_count);
    assert(0 <= event_count);

    std::vector<int> low(query_count, -1);
    std::vector<int> high(query_count, event_count + 1);
    std::vector<std::vector<int>> bucket(event_count + 1);

    while (true) {
        bool active = false;
        for (auto& queries : bucket) queries.clear();

        for (int query = 0; query < query_count; ++query) {
            if (high[query] - low[query] <= 1) continue;
            const int middle = low[query] + (high[query] - low[query]) / 2;
            bucket[middle].push_back(query);
            active = true;
        }
        if (!active) break;

        reset();
        int applied = 0;
        for (int middle = 0; middle <= event_count; ++middle) {
            while (applied < middle) {
                apply(applied);
                ++applied;
            }
            for (int query : bucket[middle]) {
                if (check(query)) {
                    high[query] = middle;
                } else {
                    low[query] = middle;
                }
            }
        }
    }

    return high;
}

}  // namespace algo
}  // namespace m1une


#line 7 "algo/offline/all.hpp"
Back to top page