SegmentSet
(src/data_structure/segment_set.hpp)

• View this file on GitHub
• Last update: 2024-11-09 01:50:04+09:00
• Include: #include "src/data_structure/segment_set.hpp"

SegmentSet

区間の集合を管理するデータ構造です．

コンストラクタ

SegmentSet<T> st

空の集合 st を作成します．

計算量

• $O(1)$

insert

void st.insert(T l, T r)

集合 st に区間 $[l, r)$ を追加します．

すでに入っている区間と重なりがある場合，それらの区間はマージされます． (サンプルコードを参照)

計算量

• 償却 $O(\log N)$ ( $N$ は入っている区間の個数)

erase

void st.erase(T l, T r)

集合 st から区間 $[l, r)$ を削除します．

元から入っていない部分については何も起こりません． (サンプルコード参照)

計算量

• 償却 $O(\log N)$

next

T st.next(T x)

集合 st に入っている区間に含まれる値のうち $x$ 以上の最小値を返します．

そのような値が存在しない場合，型 $T$ の最大値を返します．

計算量

• $O(\log N)$

size

size_t st.size()

集合 st に何個の区間が含まれているかを返します．
マージされた区間は $1$ つとみなします．

計算量

• $O(1)$

begin(), end(), find(), lower_bound()

(1) iterator st.begin()
(2) iterator st.end()
(3) iterator st.find()
(4) iterator st.lower_bound()

std::set などと同じです．

サンプルコード

#include "src/template/template.hpp"
#include "src/data_structure/segment_set.hpp"
int main(void) {
    SegmentSet<int> st;
    st.insert(3, 7);            // st: {[3, 7)}
    st.insert(10, 15);          // st: {[3, 7), [10, 15)}
    st.insert(13, 20);          // st: {[3, 7), [10, 20)}
    st.erase(5, 13);            // st: {[3, 5), [13, 20)}
    cout << st.size() << '\n';  // 2
    for(auto it : st) {
        cout << it.first << ' ' << it.second << '\n';  // (3, 5), (13, 20)
    }
    cout << st.next(10) << '\n';   // 13
    cout << st.next(17) << '\n';   // 17
    cout << st.next(5) << '\n';    // 13
    cout << st.next(100) << '\n';  // INT_MAX
}

Depends on

• template (src/template/template.hpp)

Code

#pragma once
#include "../template/template.hpp"
template <typename T>
struct SegmentSet {
    SegmentSet() = default;
    using const_iterator = typename map<T, T>::const_iterator;
    const_iterator begin() const {
        return st.begin();
    }
    const_iterator end() const {
        return st.end();
    }
    const_iterator find(const T& x) const {
        auto it = st.upper_bound(x);
        if(it == st.begin() or (--it)->second <= x) return st.end();
        return it;
    }
    const_iterator lower_bound(const T& x) const {
        auto it = st.lower_bound(x);
        if(it == st.begin() or prev(it)->second <= x) return it;
        return prev(it);
    }
    void insert(T l, T r) {
        auto L = st.upper_bound(l), R = st.upper_bound(r);
        if(L != st.begin() and l <= prev(L)->second) --L;
        if(L != R) {
            l = min(l, L->first);
            r = max(r, prev(R)->second);
            st.erase(L, R);
        }
        st[l] = r;
    }
    void erase(const T& l, const T& r) {
        auto L = st.upper_bound(l), R = st.upper_bound(r);
        if(L != st.begin() and l <= prev(L)->second) --L;
        if(L == R) return;
        const T nl = min(l, L->first), nr = max(r, prev(R)->second);
        st.erase(L, R);
        if(nl < l) st[nl] = l;
        if(r < nr) st[r] = nr;
    }
    T next(const T& x) const {
        auto it = this->lower_bound(x);
        if(it == this->end()) return numeric_limits<T>::max();
        return max<T>(x, it->first);
    }
    size_t size() const {
        return st.size();
    }

   private:
    map<T, T> st;
};

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/data_structure/segment_set.hpp"
template <typename T>
struct SegmentSet {
    SegmentSet() = default;
    using const_iterator = typename map<T, T>::const_iterator;
    const_iterator begin() const {
        return st.begin();
    }
    const_iterator end() const {
        return st.end();
    }
    const_iterator find(const T& x) const {
        auto it = st.upper_bound(x);
        if(it == st.begin() or (--it)->second <= x) return st.end();
        return it;
    }
    const_iterator lower_bound(const T& x) const {
        auto it = st.lower_bound(x);
        if(it == st.begin() or prev(it)->second <= x) return it;
        return prev(it);
    }
    void insert(T l, T r) {
        auto L = st.upper_bound(l), R = st.upper_bound(r);
        if(L != st.begin() and l <= prev(L)->second) --L;
        if(L != R) {
            l = min(l, L->first);
            r = max(r, prev(R)->second);
            st.erase(L, R);
        }
        st[l] = r;
    }
    void erase(const T& l, const T& r) {
        auto L = st.upper_bound(l), R = st.upper_bound(r);
        if(L != st.begin() and l <= prev(L)->second) --L;
        if(L == R) return;
        const T nl = min(l, L->first), nr = max(r, prev(R)->second);
        st.erase(L, R);
        if(nl < l) st[nl] = l;
        if(r < nr) st[r] = nr;
    }
    T next(const T& x) const {
        auto it = this->lower_bound(x);
        if(it == this->end()) return numeric_limits<T>::max();
        return max<T>(x, it->first);
    }
    size_t size() const {
        return st.size();
    }

   private:
    map<T, T> st;
};

Back to top page