区間を std::set で管理するやつ
(include/emthrm/data_structure/intervals_managed_by_set.hpp)

• View this file on GitHub
• Last update: 2023-02-23 21:59:12+09:00
• Include: #include "emthrm/data_structure/intervals_managed_by_set.hpp"

閉区間を std::set によって管理するデータ構造である。

時間計算量

amortized $O(\log{N})$ ?

仕様

template <typename T>
struct IntervalsManagedBySet;

• T：要素型

メンバ変数

名前	説明	備考
IntervalsType intervals	区間の集合	番兵 $\lbrack -\infty, -\infty \rbrack, \lbrack \infty, \infty \rbrack$ を含む。

メンバ関数

名前	効果・戻り値
IntervalsManagedBySet();	デフォルトコンストラクタ。集合 $S \mathrel{:=} \emptyset$ を表すオブジェクトを構築する。
bool contains(const T x) const;	$x \in S$ を満たすか。
bool contains(const T left, const T right) const;	任意の $x \in \lbrace \mathrm{left}, \ldots, \mathrm{right} \rbrace$ に対して $x \in S$ を満たすか。
std::pair<IntervalsType::const_iterator, bool> erase(const T x);	$S \gets S \setminus \lbrace x \rbrace$ の操作後、削除された要素の次を指すイテレータと実際に削除したかを返す。
std::pair<IntervalsType::const_iterator, T> erase(const T left, const T right);	$S \gets S \setminus \lbrace \mathrm{left}, \ldots, \mathrm{right} \rbrace$ の操作後、削除された要素の次を指すイテレータと削除した要素数を返す。
IntervalsType::const_iterator find(const T x) const;	$x$ を含む区間へのイテレータ。ただし $x \notin S$ を満たすときは intervals.end() を返す。
IntervalsType::const_iterator find(const T left, const T right) const;	$\lbrack \mathrm{left}, \mathrm{right} \rbrack$ を含む区間へのイテレータ。ただし $x \notin S$ を満たす $x \in \lbrace \mathrm{left}, \ldots, \mathrm{right} \rbrace$ が存在するときは intervals.end() を返す。
std::pair<IntervalsType::const_iterator, bool> insert(const T x);	$S \gets S \cup \lbrace x \rbrace$ の操作後、要素へのイテレータと実際に挿入されたかどうかを返す。
std::pair<IntervalsType::const_iterator, T> insert(T left, T right);	$S \gets S \cup \lbrace \mathrm{left}, \ldots, \mathrm{right} \rbrace$ の操作後、要素へのイテレータと実際に挿入した要素数を返す。
T mex(const T x = 0) const;	$\mathrm{mex}(S)$
friend std::ostream& operator<<(std::ostream& os, const IntervalsManagedBySet& x);

メンバ型

名前	説明
IntervalsType	std::set<std::pair<T, T>>

参考文献

• https://mugen1337.hatenablog.com/entry/2020/10/14/134022

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/2880/review/5242323/emthrm/C++17

Verified with

• データ構造/区間を std::set で管理するやつ (test/data_structure/intervals_managed_by_set.test.cpp)

Code

#ifndef EMTHRM_DATA_STRUCTURE_INTERVALS_MANAGED_BY_SET_HPP_
#define EMTHRM_DATA_STRUCTURE_INTERVALS_MANAGED_BY_SET_HPP_

#include <cassert>
#include <iostream>
#include <iterator>
#include <limits>
#include <set>
#include <utility>

namespace emthrm {

template <typename T>
struct IntervalsManagedBySet {
  using IntervalsType = std::set<std::pair<T, T>>;
  IntervalsType intervals{
      {std::numeric_limits<T>::lowest(), std::numeric_limits<T>::lowest()},
      {std::numeric_limits<T>::max(), std::numeric_limits<T>::max()}};

  IntervalsManagedBySet() = default;

  bool contains(const T x) const { return contains(x, x); }

  bool contains(const T left, const T right) const {
    return find(left, right) != intervals.end();
  }

  std::pair<typename IntervalsType::const_iterator, bool> erase(const T x) {
    typename IntervalsType::const_iterator it = intervals.lower_bound({x, x});
    if (it->first == x) {
      const T right = it->second;
      it = intervals.erase(it);
      if (x + 1 <= right) it = intervals.emplace(x + 1, right).first;
    } else {
      it = std::prev(it);
      const auto [left, right] = *it;
      if (right < x) return {std::next(it), false};
      intervals.erase(it);
      it = std::next(intervals.emplace(left, x - 1).first);
      if (x + 1 <= right) it = intervals.emplace(x + 1, right).first;
    }
    return {it, true};
  }

  std::pair<typename IntervalsType::const_iterator, T> erase(
      const T left, const T right) {
    assert(left <= right);
    typename IntervalsType::const_iterator it =
        intervals.lower_bound({left, left});
    T res = 0;
    for (; it->second <= right; it = intervals.erase(it)) {
      res += it->second - it->first + 1;
    }
    if (it->first <= right) {
      res += right - it->first + 1;
      const T r = it->second;
      intervals.erase(it);
      it = intervals.emplace(right + 1, r).first;
    }
    if (left <= std::prev(it)->second) {
      it = std::prev(it);
      const auto [l, r] = *it;
      intervals.erase(it);
      if (right < r) {
        res += right - left + 1;
        intervals.emplace(right + 1, r);
      } else {
        res += r - left + 1;
      }
      it = std::next(intervals.emplace(l, left - 1).first);
    }
    return {it, res};
  }

  typename IntervalsType::const_iterator find(const T x) const {
    return find(x, x);
  }

  typename IntervalsType::const_iterator find(
      const T left, const T right) const {
    typename IntervalsType::const_iterator it =
        intervals.lower_bound({left, left});
    if (left < it->first) it = std::prev(it);
    return it->first <= left && right <= it->second ? it : intervals.end();
  }

  std::pair<typename IntervalsType::const_iterator, bool> insert(const T x) {
    typename IntervalsType::const_iterator it = intervals.lower_bound({x, x});
    if (it->first == x) return {it, false};
    if (x <= std::prev(it)->second) return {std::prev(it), false};
    T left = x, right = x;
    if (x + 1 == it->first) {
      right = it->second;
      it = intervals.erase(it);
    }
    if (std::prev(it)->second == x - 1) {
      it = std::prev(it);
      left = it->first;
      intervals.erase(it);
    }
    return {intervals.emplace(left, right).first, true};
  }

  std::pair<typename IntervalsType::const_iterator, T> insert(T left, T right) {
    assert(left <= right);
    typename IntervalsType::const_iterator it =
        intervals.lower_bound({left, left});
    if (left <= std::prev(it)->second) {
      it = std::prev(it);
      left = it->first;
    }
    T res = 0;
    if (left == it->first && right <= it->second) return {it, res};
    for (; it->second <= right; it = intervals.erase(it)) {
      res -= it->second - it->first + 1;
    }
    if (it->first <= right) {
      res -= it->second - it->first + 1;
      right = it->second;
      it = intervals.erase(it);
    }
    res += right - left + 1;
    if (right + 1 == it->first) {
      right = it->second;
      it = intervals.erase(it);
    }
    if (std::prev(it)->second == left - 1) {
      it = std::prev(it);
      left = it->first;
      intervals.erase(it);
    }
    return {intervals.emplace(left, right).first, res};
  }

  T mex(const T x = 0) const {
    auto it = intervals.lower_bound({x, x});
    if (x <= std::prev(it)->second) it = std::prev(it);
    return x < it->first ? x : it->second + 1;
  }

  friend std::ostream& operator<<(std::ostream& os,
                                  const IntervalsManagedBySet& x) {
    if (x.intervals.size() == 2) return os;
    auto it = next(x.intervals.begin());
    while (true) {
      os << '[' << it->first << ", " << it->second << ']';
      it = next(it);
      if (next(it) == x.intervals.end()) break;
      os << ' ';
    }
    return os;
  }
};

}  // namespace emthrm

#endif  // EMTHRM_DATA_STRUCTURE_INTERVALS_MANAGED_BY_SET_HPP_

#line 1 "include/emthrm/data_structure/intervals_managed_by_set.hpp"



#include <cassert>
#include <iostream>
#include <iterator>
#include <limits>
#include <set>
#include <utility>

namespace emthrm {

template <typename T>
struct IntervalsManagedBySet {
  using IntervalsType = std::set<std::pair<T, T>>;
  IntervalsType intervals{
      {std::numeric_limits<T>::lowest(), std::numeric_limits<T>::lowest()},
      {std::numeric_limits<T>::max(), std::numeric_limits<T>::max()}};

  IntervalsManagedBySet() = default;

  bool contains(const T x) const { return contains(x, x); }

  bool contains(const T left, const T right) const {
    return find(left, right) != intervals.end();
  }

  std::pair<typename IntervalsType::const_iterator, bool> erase(const T x) {
    typename IntervalsType::const_iterator it = intervals.lower_bound({x, x});
    if (it->first == x) {
      const T right = it->second;
      it = intervals.erase(it);
      if (x + 1 <= right) it = intervals.emplace(x + 1, right).first;
    } else {
      it = std::prev(it);
      const auto [left, right] = *it;
      if (right < x) return {std::next(it), false};
      intervals.erase(it);
      it = std::next(intervals.emplace(left, x - 1).first);
      if (x + 1 <= right) it = intervals.emplace(x + 1, right).first;
    }
    return {it, true};
  }

  std::pair<typename IntervalsType::const_iterator, T> erase(
      const T left, const T right) {
    assert(left <= right);
    typename IntervalsType::const_iterator it =
        intervals.lower_bound({left, left});
    T res = 0;
    for (; it->second <= right; it = intervals.erase(it)) {
      res += it->second - it->first + 1;
    }
    if (it->first <= right) {
      res += right - it->first + 1;
      const T r = it->second;
      intervals.erase(it);
      it = intervals.emplace(right + 1, r).first;
    }
    if (left <= std::prev(it)->second) {
      it = std::prev(it);
      const auto [l, r] = *it;
      intervals.erase(it);
      if (right < r) {
        res += right - left + 1;
        intervals.emplace(right + 1, r);
      } else {
        res += r - left + 1;
      }
      it = std::next(intervals.emplace(l, left - 1).first);
    }
    return {it, res};
  }

  typename IntervalsType::const_iterator find(const T x) const {
    return find(x, x);
  }

  typename IntervalsType::const_iterator find(
      const T left, const T right) const {
    typename IntervalsType::const_iterator it =
        intervals.lower_bound({left, left});
    if (left < it->first) it = std::prev(it);
    return it->first <= left && right <= it->second ? it : intervals.end();
  }

  std::pair<typename IntervalsType::const_iterator, bool> insert(const T x) {
    typename IntervalsType::const_iterator it = intervals.lower_bound({x, x});
    if (it->first == x) return {it, false};
    if (x <= std::prev(it)->second) return {std::prev(it), false};
    T left = x, right = x;
    if (x + 1 == it->first) {
      right = it->second;
      it = intervals.erase(it);
    }
    if (std::prev(it)->second == x - 1) {
      it = std::prev(it);
      left = it->first;
      intervals.erase(it);
    }
    return {intervals.emplace(left, right).first, true};
  }

  std::pair<typename IntervalsType::const_iterator, T> insert(T left, T right) {
    assert(left <= right);
    typename IntervalsType::const_iterator it =
        intervals.lower_bound({left, left});
    if (left <= std::prev(it)->second) {
      it = std::prev(it);
      left = it->first;
    }
    T res = 0;
    if (left == it->first && right <= it->second) return {it, res};
    for (; it->second <= right; it = intervals.erase(it)) {
      res -= it->second - it->first + 1;
    }
    if (it->first <= right) {
      res -= it->second - it->first + 1;
      right = it->second;
      it = intervals.erase(it);
    }
    res += right - left + 1;
    if (right + 1 == it->first) {
      right = it->second;
      it = intervals.erase(it);
    }
    if (std::prev(it)->second == left - 1) {
      it = std::prev(it);
      left = it->first;
      intervals.erase(it);
    }
    return {intervals.emplace(left, right).first, res};
  }

  T mex(const T x = 0) const {
    auto it = intervals.lower_bound({x, x});
    if (x <= std::prev(it)->second) it = std::prev(it);
    return x < it->first ? x : it->second + 1;
  }

  friend std::ostream& operator<<(std::ostream& os,
                                  const IntervalsManagedBySet& x) {
    if (x.intervals.size() == 2) return os;
    auto it = next(x.intervals.begin());
    while (true) {
      os << '[' << it->first << ", " << it->second << ']';
      it = next(it);
      if (next(it) == x.intervals.end()) break;
      os << ' ';
    }
    return os;
  }
};

}  // namespace emthrm

Back to top page