はじめに

Ryoga.exe の競プロ用ライブラリ・スニペットのドキュメントです。

C++17 (GCC 9.2.1) での使用を想定しています。

報告や提案

バグや不具合、ドキュメントの誤字、改善点等を発見した際は、Ryoga.exe へ知らせてくれると嬉しいです。 Twitter で @Ryoga_exe をメンションするか直接 DM するかが確実です。

Issues や PR も大歓迎なので気軽に投げていただけるとありがたいです！

Follow @Ryoga_exe Tweet to @Ryoga_exe

ライセンス

ライブラリ本体とドキュメントにおける著作権等の権利は CC0 に従って放棄します。

Licensed under a CC0 license. See LICENSE file for more further details.

Data Structure

データ構造

RangeSet

区間 [l, r) を std::set のように管理するデータ構造です。

重なり合う区間はマージされ一つの区間になります。

Spec

• (constructor)
• begin
• end

Note

Code

#include <set>
#include <utility>
#include <iterator>
#include <vector>
#include <cassert>
#include <algorithm>

/// start
/// @prefix cpRangeSet
/// @description [l, r) の区間を管理するデータ構造
/// @isFileTemplate false
struct RangeSet {
public:
    using value_type = long long;
    using range_type = std::pair<value_type, value_type>;
    using container_type = std::set<range_type>;
    using iterator = typename container_type::iterator;
    using size_type = typename container_type::size_type;
private:
    container_type m_set;
public:
    RangeSet() = default;
    iterator begin() const noexcept {
        return m_set.begin();
    }
    iterator end() const noexcept {
        return m_set.end();
    }
    bool empty() const noexcept {
        return m_set.empty();
    }
    size_type size() const noexcept {
        return m_set.size();
    }
    value_type coveredLength() const noexcept {
        value_type result = 0;
        for (const auto& [l, r] : m_set) {
            result += (r - l);
        }
        return result;
    }
    container_type asSet() const {
        return m_set;
    }
    std::vector<range_type> asVector() const {
        std::vector<range_type> result;
        for (const auto& range : m_set) {
            result.push_back(range);
        }
        return result;
    }
    std::pair<iterator, bool> insert(value_type left, value_type right) {
        assert(left <= right);
        if (left == right) {
            return { m_set.end(), false };
        }
        auto itr_l = m_set.lower_bound({ left + 1, left + 1 });
        auto itr_r = m_set.lower_bound({ right + 1, right + 1 });
        if (itr_l != m_set.begin()) {
            if (std::prev(itr_l)->second >= left) {
                itr_l--;
            }
        }
        auto tl = left, tr = right;
        if (itr_l != itr_r) {
            tl = std::min(left, itr_l->first);
            tr = std::max(right, std::prev(itr_r)->second);
            m_set.erase(itr_l, itr_r);
        }
        return m_set.insert({ tl, tr });
    }
    void erase(const value_type left, const value_type right) {
        assert(left <= right);
        if (left == right) {
            return;
        }
        auto itr_l = m_set.lower_bound({ left + 1, left + 1 });
        auto itr_r = m_set.lower_bound({ right + 1, right + 1 });
        if (itr_l != m_set.begin()) {
            if (std::prev(itr_l)->second >= left) {
                itr_l--;
            }
        }
        if (itr_l == itr_r) {
            return;
        }
        auto tl = std::min(left, itr_l->first);
        auto tr = std::max(right, std::prev(itr_r)->second);
        m_set.erase(itr_l, itr_r);
        if (tl < left) {
            m_set.insert({ tl, left });
        }
        if (right < tr) {
            m_set.insert({ right, tr });
        }
    }
    iterator find(const value_type x) const {
        auto itr = m_set.lower_bound({ x + 1, x + 1 });
        if (itr == m_set.begin() || (--itr)->second <= x) {
            return m_set.end();
        }
        return itr;
    }
    iterator find(const value_type left, const value_type right) const {
        assert(left <= right);
        auto itr = find(left);
        if (itr == m_set.end()) {
            return m_set.end();
        }
        if (right <= itr->second) {
            return itr;
        }
        else {
            return m_set.end();
        }
    }
    bool contains(const value_type left, const value_type right) const {
        assert(left <= right);
        return find(left, right) != m_set.end();
    }
    bool contains(const value_type x) const {
        return find(x) != m_set.end();
    }
};

Example

Math

数学