This documentation is automatically generated by online-judge-tools/verification-helper
#include "DataStructure/rangeunionset.hpp"
RangeUnionSet()
: 空のデータ構造を作成。テンプレートに型と最大値を指定。
void insert(T L,T R)
: 半開区間 $[L,R)$ を整数集合に追加。
void erase(T L,T R)
: 半開区間 $[L,R)$ を整数集合から削除。
T mex(T x)
: 整数集合の mex を求める。
#pragma once
template <typename T, T mx> struct RangeUnionSet {
map<T, T> data;
RangeUnionSet() {}
void insert(T lb, T rb) {
auto L = data.upper_bound(lb), R = data.upper_bound(rb);
if (L != data.begin() and lb <= prev(L)->second)
L--;
if (L != R) {
chmin(lb, L->first);
chmax(rb, prev(R)->second);
data.erase(L, R);
}
data[lb] = rb;
}
void erase(T lb, T rb) {
auto L = data.upper_bound(lb), R = data.upper_bound(rb);
if (L != data.begin() and lb <= prev(L)->second)
L--;
if (L == R)
return;
T nl = min(lb, L->first), nr = max(rb, prev(R)->second);
data.erase(L, R);
if (nl < lb)
data[nl] = lb;
if (rb < nr)
data[rb] = nr;
}
T mex(T x) const {
auto it = data.lower_bound(x);
if (it != data.begin() and prev(it)->second > x)
it--;
if (it == data.end())
return mx;
return max(x, it->first);
}
vector<pair<T, T>> get() {
vector<pair<T, T>> ret;
for (auto &[L, R] : data)
ret.push_back({L, R});
return ret;
}
};
/**
* @brief Range Union Set
* @docs docs/rangeunionset.md
*/
#line 2 "DataStructure/rangeunionset.hpp"
template <typename T, T mx> struct RangeUnionSet {
map<T, T> data;
RangeUnionSet() {}
void insert(T lb, T rb) {
auto L = data.upper_bound(lb), R = data.upper_bound(rb);
if (L != data.begin() and lb <= prev(L)->second)
L--;
if (L != R) {
chmin(lb, L->first);
chmax(rb, prev(R)->second);
data.erase(L, R);
}
data[lb] = rb;
}
void erase(T lb, T rb) {
auto L = data.upper_bound(lb), R = data.upper_bound(rb);
if (L != data.begin() and lb <= prev(L)->second)
L--;
if (L == R)
return;
T nl = min(lb, L->first), nr = max(rb, prev(R)->second);
data.erase(L, R);
if (nl < lb)
data[nl] = lb;
if (rb < nr)
data[rb] = nr;
}
T mex(T x) const {
auto it = data.lower_bound(x);
if (it != data.begin() and prev(it)->second > x)
it--;
if (it == data.end())
return mx;
return max(x, it->first);
}
vector<pair<T, T>> get() {
vector<pair<T, T>> ret;
for (auto &[L, R] : data)
ret.push_back({L, R});
return ret;
}
};
/**
* @brief Range Union Set
* @docs docs/rangeunionset.md
*/