section set
(data_structure/section_set.hpp)

• View this file on GitHub
• Last update: 2024-02-18 14:20:37+09:00
• Include: #include "data_structure/section_set.hpp"

説明

区間を管理するセットである。

insert(l, r)

$[l, r)$ を追加

erase(l, r)

$[l, r)$ を削除

find(x)

$x$ が含まれるか判定

find(l, r)

$[l, r)$ が含まれるか判定

belong(x)

$x$ の含まれる区間 $[l, r)$ を返す。 $x$ を含む区間がないならば $[0, 0)$ を返す。

lower_bound(l)

左端が $l$ 以上の区間を返す。

Verified with

• test/aoj/aoj_2152.test.cpp

Code

#pragma once

#include <cassert>
#include <limits>
#include <set>

namespace ebi {

template <class T> struct section_set {
  private:
    std::set<std::pair<T, T>> set;

  public:
    section_set() {
        set.insert(
            {std::numeric_limits<T>::min(), std::numeric_limits<T>::min()});
        set.insert(
            {std::numeric_limits<T>::max(), std::numeric_limits<T>::max()});
    }

    std::set<std::pair<T, T>> sections() const {
        return set;
    }

    // [l, r)を追加
    void insert(T l, T r) {
        auto itr =
            std::prev(set.lower_bound({l, std::numeric_limits<T>::min()}));
        if (l <= itr->second) {
            assert(itr->first <= l);
            l = itr->first;
            r = std::max(r, itr->second);
            set.erase(itr);
        }
        itr = set.lower_bound({l, std::numeric_limits<T>::min()});
        while (itr->first <= r) {
            assert(l <= itr->first);
            r = std::max(r, itr->second);
            itr = set.erase(itr);
        }
        set.insert({l, r});
        return;
    }

    // 集合内の[l, r)に含まれている要素を削除
    void erase(T l, T r) {
        auto itr =
            std::prev(set.lower_bound({l, std::numeric_limits<T>::min()}));
        if (l < itr->second) {
            assert(itr->first < l);
            set.insert({itr->first, l});
            if (r < itr->second) {
                set.insert({r, itr->second});
            }
            set.erase(itr);
        }
        itr = set.lower_bound({l, std::numeric_limits<T>::min()});
        while (itr->first < r) {
            if (itr->second <= r) {
                itr = set.erase(itr);
            } else {
                set.insert({r, itr->second});
                set.erase(itr);
                break;
            }
        }
        return;
    }

    bool find(T x) const {
        auto itr =
            std::prev(set.upper_bound({x, std::numeric_limits<T>::max()}));
        if (x < itr->second) {
            assert(itr->first <= x);
            return true;
        } else {
            return false;
        }
    }

    bool find(T l, T r) const {
        auto itr =
            std::prev(set.upper_bound({l, std::numeric_limits<T>::max()}));
        if (r <= itr->second) {
            assert(itr->first <= l);
            return true;
        } else {
            return false;
        }
    }

    std::pair<T, T> belong(T x) const {
        auto itr =
            std::prev(set.upper_bound({x, std::numeric_limits<T>::max()}));
        if (x < itr->second) {
            assert(itr->first <= x);
            return *itr;
        } else {
            return {0, 0};
        }
    }

    std::pair<T, T> lower_bound(T l) const {
        return *set.lower_bound({l, std::numeric_limits<T>::min()});
    }
};

}  // namespace ebi

#line 2 "data_structure/section_set.hpp"

#include <cassert>
#include <limits>
#include <set>

namespace ebi {

template <class T> struct section_set {
  private:
    std::set<std::pair<T, T>> set;

  public:
    section_set() {
        set.insert(
            {std::numeric_limits<T>::min(), std::numeric_limits<T>::min()});
        set.insert(
            {std::numeric_limits<T>::max(), std::numeric_limits<T>::max()});
    }

    std::set<std::pair<T, T>> sections() const {
        return set;
    }

    // [l, r)を追加
    void insert(T l, T r) {
        auto itr =
            std::prev(set.lower_bound({l, std::numeric_limits<T>::min()}));
        if (l <= itr->second) {
            assert(itr->first <= l);
            l = itr->first;
            r = std::max(r, itr->second);
            set.erase(itr);
        }
        itr = set.lower_bound({l, std::numeric_limits<T>::min()});
        while (itr->first <= r) {
            assert(l <= itr->first);
            r = std::max(r, itr->second);
            itr = set.erase(itr);
        }
        set.insert({l, r});
        return;
    }

    // 集合内の[l, r)に含まれている要素を削除
    void erase(T l, T r) {
        auto itr =
            std::prev(set.lower_bound({l, std::numeric_limits<T>::min()}));
        if (l < itr->second) {
            assert(itr->first < l);
            set.insert({itr->first, l});
            if (r < itr->second) {
                set.insert({r, itr->second});
            }
            set.erase(itr);
        }
        itr = set.lower_bound({l, std::numeric_limits<T>::min()});
        while (itr->first < r) {
            if (itr->second <= r) {
                itr = set.erase(itr);
            } else {
                set.insert({r, itr->second});
                set.erase(itr);
                break;
            }
        }
        return;
    }

    bool find(T x) const {
        auto itr =
            std::prev(set.upper_bound({x, std::numeric_limits<T>::max()}));
        if (x < itr->second) {
            assert(itr->first <= x);
            return true;
        } else {
            return false;
        }
    }

    bool find(T l, T r) const {
        auto itr =
            std::prev(set.upper_bound({l, std::numeric_limits<T>::max()}));
        if (r <= itr->second) {
            assert(itr->first <= l);
            return true;
        } else {
            return false;
        }
    }

    std::pair<T, T> belong(T x) const {
        auto itr =
            std::prev(set.upper_bound({x, std::numeric_limits<T>::max()}));
        if (x < itr->second) {
            assert(itr->first <= x);
            return *itr;
        } else {
            return {0, 0};
        }
    }

    std::pair<T, T> lower_bound(T l) const {
        return *set.lower_bound({l, std::numeric_limits<T>::min()});
    }
};

}  // namespace ebi

Back to top page