C++ Library for Competitive Programming
#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://onlinejudge.u-aizu.ac.jp/solutions/problem/2880/review/5242323/emthrm/C++17
#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