Interval Set
(misc/interval_set.hpp)

• View this file on GitHub
• Last update: 2024-01-08 00:27:17+09:00
• Include: #include "misc/interval_set.hpp"

Description

整数の閉区間の集合を管理する．

Operations

• bool covered(T x)
• bool covered(T l, T r)
  • 区間 $[l, r]$ が含まれているか判定する
  • 時間計算量: $O(\log n)$
• pair<T, T> covered_by(T x)
• pair<T, T> covered_by(T l, T r)
  • 区間 $[l, r]$ を含む区間を返す．そのような区間がない場合は $(-\infty, \infty)$ を返す
  • 時間計算量: $O(\log n)$
• void insert(T x)
• void insert(T l, T r)
  • 区間 $[l, r]$ を集合に追加する
  • 時間計算量: $\mathrm{amortized}\ O(\log n)$
• void erase(T x)
• void erase(T l, T r)
  • 区間 $[l, r]$ を集合から削除する
  • 時間計算量: $\mathrm{amortized}\ O(\log n)$
• T mex(T x)
  • $x$ 以上の整数のうち，集合に含まれない最小のものを返す
  • 時間計算量: $O(\log n)$

Note

隣り合う区間はマージされる．各区間に値を持たせたり，隣り合う区間をマージしないようにするには，Intervals クラスを使用のこと．

Reference

• 区間をsetで管理するやつでもうバグらせたくない
• 要素の追加・削除と mex を対数時間で処理するよ

Code

#pragma once
#include <cassert>
#include <limits>
#include <set>
#include <utility>

template <typename T>
class IntervalSet {
   public:
    static constexpr T INF = std::numeric_limits<T>::max() / 2;

    IntervalSet() {
        st.emplace(INF, INF);
        st.emplace(-INF, -INF);
    }

    bool covered(T x) const { return covered(x, x); }
    bool covered(T l, T r) const {
        assert(l <= r);
        auto it = --(st.lower_bound({l + 1, l + 1}));
        return it->first <= l && r <= it->second;
    }

    std::pair<T, T> covered_by(T x) const { return covered_by(x, x); }
    std::pair<T, T> covered_by(T l, T r) const {
        assert(l <= r);
        auto it = --(st.lower_bound({l + 1, l + 1}));
        if (it->first <= l && r <= it->second) return *it;
        return {-INF, -INF};
    }

    void insert(T x) { insert(x, x); }
    void insert(T l, T r) {
        assert(l <= r);
        auto it = --(st.lower_bound({l + 1, l + 1}));
        if (it->first <= l && r <= it->second) return;
        if (it->first <= l && l <= it->second + 1) {
            l = it->first;
            it = st.erase(it);
        } else {
            ++it;
        }
        while (it->second < r) {
            it = st.erase(it);
        }
        if (it->first - 1 <= r && r <= it->second) {
            r = it->second;
            st.erase(it);
        }
        st.emplace(l, r);
    }

    void erase(T x) { erase(x, x); }
    void erase(T l, T r) {
        assert(l <= r);
        auto it = --(st.lower_bound({l + 1, l + 1}));
        if (it->first <= l && r <= it->second) {
            if (it->first < l) st.emplace(it->first, l - 1);
            if (r < it->second) st.emplace(r + 1, it->second);
            st.erase(it);
            return;
        }
        if (it->first <= l && l <= it->second) {
            if (it->first < l) st.emplace(it->first, l - 1);
            it = st.erase(it);
        } else {
            ++it;
        }
        while (it->second <= r) {
            it = st.erase(it);
        }
        if (it->first <= r && r <= it->second) {
            if (r < it->second) st.emplace(r + 1, it->second);
            st.erase(it);
        }
    }

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

    T mex(T x) const {
        auto it = --(st.lower_bound({x + 1, x + 1}));
        if (it->first <= x && x <= it->second) return it->second + 1;
        return x;
    }

   private:
    std::set<std::pair<T, T>> st;
};

#line 2 "misc/interval_set.hpp"
#include <cassert>
#include <limits>
#include <set>
#include <utility>

template <typename T>
class IntervalSet {
   public:
    static constexpr T INF = std::numeric_limits<T>::max() / 2;

    IntervalSet() {
        st.emplace(INF, INF);
        st.emplace(-INF, -INF);
    }

    bool covered(T x) const { return covered(x, x); }
    bool covered(T l, T r) const {
        assert(l <= r);
        auto it = --(st.lower_bound({l + 1, l + 1}));
        return it->first <= l && r <= it->second;
    }

    std::pair<T, T> covered_by(T x) const { return covered_by(x, x); }
    std::pair<T, T> covered_by(T l, T r) const {
        assert(l <= r);
        auto it = --(st.lower_bound({l + 1, l + 1}));
        if (it->first <= l && r <= it->second) return *it;
        return {-INF, -INF};
    }

    void insert(T x) { insert(x, x); }
    void insert(T l, T r) {
        assert(l <= r);
        auto it = --(st.lower_bound({l + 1, l + 1}));
        if (it->first <= l && r <= it->second) return;
        if (it->first <= l && l <= it->second + 1) {
            l = it->first;
            it = st.erase(it);
        } else {
            ++it;
        }
        while (it->second < r) {
            it = st.erase(it);
        }
        if (it->first - 1 <= r && r <= it->second) {
            r = it->second;
            st.erase(it);
        }
        st.emplace(l, r);
    }

    void erase(T x) { erase(x, x); }
    void erase(T l, T r) {
        assert(l <= r);
        auto it = --(st.lower_bound({l + 1, l + 1}));
        if (it->first <= l && r <= it->second) {
            if (it->first < l) st.emplace(it->first, l - 1);
            if (r < it->second) st.emplace(r + 1, it->second);
            st.erase(it);
            return;
        }
        if (it->first <= l && l <= it->second) {
            if (it->first < l) st.emplace(it->first, l - 1);
            it = st.erase(it);
        } else {
            ++it;
        }
        while (it->second <= r) {
            it = st.erase(it);
        }
        if (it->first <= r && r <= it->second) {
            if (r < it->second) st.emplace(r + 1, it->second);
            st.erase(it);
        }
    }

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

    T mex(T x) const {
        auto it = --(st.lower_bound({x + 1, x + 1}));
        if (it->first <= x && x <= it->second) return it->second + 1;
        return x;
    }

   private:
    std::set<std::pair<T, T>> st;
};

Back to top page