This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/icpc_library
#include "data_structure/section_set.hpp"
区間を管理するセットである。
$[l, r)$ を追加
$[l, r)$ を削除
$x$ が含まれるか判定
$[l, r)$ が含まれるか判定
$x$ の含まれる区間 $[l, r)$ を返す。 $x$ を含む区間がないならば $[0, 0)$ を返す。
左端が $l$ 以上の区間を返す。
#pragma once #include "../template/template.hpp" namespace lib { template <class T> struct section_set { private: std::set<std::pair<T, T>> st; public: section_set() { st.insert( {std::numeric_limits<T>::min(), std::numeric_limits<T>::min()}); st.insert( {std::numeric_limits<T>::max(), std::numeric_limits<T>::max()}); } std::set<std::pair<T, T>> sections() const { return st; } // [l, r)を追加 void insert(T l, T r) { auto itr = std::prev(st.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); st.erase(itr); } itr = st.lower_bound({l, std::numeric_limits<T>::min()}); while (itr->first <= r) { assert(l <= itr->first); r = std::max(r, itr->second); itr = st.erase(itr); } st.insert({l, r}); return; } // 集合内の[l, r)に含まれている要素を削除 void erase(T l, T r) { auto itr = std::prev(st.lower_bound({l, std::numeric_limits<T>::min()})); if (l < itr->second) { assert(itr->first < l); st.insert({itr->first, l}); if (r < itr->second) { st.insert({r, itr->second}); } st.erase(itr); } itr = st.lower_bound({l, std::numeric_limits<T>::min()}); while (itr->first < r) { if (itr->second <= r) { itr = st.erase(itr); } else { st.insert({r, itr->second}); st.erase(itr); break; } } return; } bool find(T x) const { auto itr = std::prev(st.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(st.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(st.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 *st.lower_bound({l, std::numeric_limits<T>::min()}); } }; } // namespace lib
#line 2 "data_structure/section_set.hpp" #line 2 "template/template.hpp" #include <bits/stdc++.h> #define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++) #define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--) #define all(v) v.begin(), v.end() using ll = long long; using ld = long double; using ull = unsigned long long; template <typename T> bool chmin(T &a, const T &b) { if (a <= b) return false; a = b; return true; } template <typename T> bool chmax(T &a, const T &b) { if (a >= b) return false; a = b; return true; } namespace lib { using namespace std; } // namespace lib // using namespace lib; #line 4 "data_structure/section_set.hpp" namespace lib { template <class T> struct section_set { private: std::set<std::pair<T, T>> st; public: section_set() { st.insert( {std::numeric_limits<T>::min(), std::numeric_limits<T>::min()}); st.insert( {std::numeric_limits<T>::max(), std::numeric_limits<T>::max()}); } std::set<std::pair<T, T>> sections() const { return st; } // [l, r)を追加 void insert(T l, T r) { auto itr = std::prev(st.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); st.erase(itr); } itr = st.lower_bound({l, std::numeric_limits<T>::min()}); while (itr->first <= r) { assert(l <= itr->first); r = std::max(r, itr->second); itr = st.erase(itr); } st.insert({l, r}); return; } // 集合内の[l, r)に含まれている要素を削除 void erase(T l, T r) { auto itr = std::prev(st.lower_bound({l, std::numeric_limits<T>::min()})); if (l < itr->second) { assert(itr->first < l); st.insert({itr->first, l}); if (r < itr->second) { st.insert({r, itr->second}); } st.erase(itr); } itr = st.lower_bound({l, std::numeric_limits<T>::min()}); while (itr->first < r) { if (itr->second <= r) { itr = st.erase(itr); } else { st.insert({r, itr->second}); st.erase(itr); break; } } return; } bool find(T x) const { auto itr = std::prev(st.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(st.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(st.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 *st.lower_bound({l, std::numeric_limits<T>::min()}); } }; } // namespace lib