This documentation is automatically generated by competitive-verifier/competitive-verifier
区間の集合についてのクエリを処理する構造体
SegmentSet()
:初期化した集合 $S$ を得る.insert(x)
:$S \leftarrow S \cup \{x\}$insert(l, r)
:$S \leftarrow S \cup \{l, l+1, …, r-1, r\}$erase(x)
:$S \leftarrow S \setminus \{x\}$erase(l, r)
:$S \leftarrow S \setminus \{l, l+1, …, r-1, r\}$
get_seg(x)
:$x$ が所属する区間の両端の値をもつ pair
を返す.$x$ がどの区間にも所属しない場合は pair(0, -1)
を返す.min()
:最も左にある区間の左端の値を返す.max()
:最も右にある区間の右端の値を返す.mex(x)
:$x$ 以上であって集合に含まれない値のうち最小のものを返す.same(x, y)
:$x$ と $y$ が同じ区間に含まれる場合は true
,そうでない場合は false
を返す.size()
:区間の数を返す.out()
:区間の一覧表示を出力する.区間の数を $n$ とする.
insert(x)
:$O(\log n)$insert(l, r)
:$O(\log n)$erase(x)
:$O(\log n)$erase(l, r)
:$O(\log n)$
get_seg(x)
:$O(\log n)$min()
:$O(1)$max()
:$O(1)$mex(x)
:$O(\log n)$same(x, y)
:$O(\log n)$size()
:$O(1)$out()
:$O(n)$#pragma once
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T> struct SegmentSet {
private:
map<T, T> mp;
public:
SegmentSet() : mp(){};
void insert(T x) {
insert(x, x);
}
void insert(T l, T r) {
assert(l <= r);
auto itr_l = mp.upper_bound(l), itr_r = mp.upper_bound(r + 1);
if(itr_l != mp.begin()) {
if((--itr_l)->second < l - 1) itr_l++;
}
if(itr_l != itr_r) {
l = std::min(l, itr_l->first);
r = std::max(r, prev(itr_r)->second);
mp.erase(itr_l, itr_r);
}
mp[l] = r;
}
void erase(T x) {
erase(x, x);
}
void erase(T l, T r) {
assert(l <= r);
auto itr_l = mp.upper_bound(l), itr_r = mp.upper_bound(r);
if(itr_l != mp.begin()) {
if((--itr_l)->second < l) itr_l++;
}
if(itr_l == itr_r) return;
T tmp_l = itr_l->first, tmp_r = prev(itr_r)->second;
mp.erase(itr_l, itr_r);
if(tmp_l < l) mp[tmp_l] = l - 1;
if(r < tmp_r) mp[r + 1] = tmp_r;
}
pair<T, T> get_seg(T x) {
auto itr = mp.upper_bound(x);
if(itr == mp.begin() or (--itr)->second < x) return pair<T, T>(0, -1);
return pair<T, T>(itr->first, itr->second);
}
T min() {
return mp.begin()->first;
}
T max() {
return mp.rbegin()->second;
}
T mex(T x = 0) {
pair<T, T> p = get_seg(x);
if(p.first > p.second) return x;
return p.second + 1;
}
bool same(T x, T y) {
pair<T, T> p = get_seg(x);
return p.first <= p.second and p.first <= y and y <= p.second;
}
int size() {
return int(mp.size());
}
void out() {
for(auto [l, r] : mp) cout << "[" << l << ", " << r << "]\n";
}
};
#line 2 "structure/segment_set.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T> struct SegmentSet {
private:
map<T, T> mp;
public:
SegmentSet() : mp(){};
void insert(T x) {
insert(x, x);
}
void insert(T l, T r) {
assert(l <= r);
auto itr_l = mp.upper_bound(l), itr_r = mp.upper_bound(r + 1);
if(itr_l != mp.begin()) {
if((--itr_l)->second < l - 1) itr_l++;
}
if(itr_l != itr_r) {
l = std::min(l, itr_l->first);
r = std::max(r, prev(itr_r)->second);
mp.erase(itr_l, itr_r);
}
mp[l] = r;
}
void erase(T x) {
erase(x, x);
}
void erase(T l, T r) {
assert(l <= r);
auto itr_l = mp.upper_bound(l), itr_r = mp.upper_bound(r);
if(itr_l != mp.begin()) {
if((--itr_l)->second < l) itr_l++;
}
if(itr_l == itr_r) return;
T tmp_l = itr_l->first, tmp_r = prev(itr_r)->second;
mp.erase(itr_l, itr_r);
if(tmp_l < l) mp[tmp_l] = l - 1;
if(r < tmp_r) mp[r + 1] = tmp_r;
}
pair<T, T> get_seg(T x) {
auto itr = mp.upper_bound(x);
if(itr == mp.begin() or (--itr)->second < x) return pair<T, T>(0, -1);
return pair<T, T>(itr->first, itr->second);
}
T min() {
return mp.begin()->first;
}
T max() {
return mp.rbegin()->second;
}
T mex(T x = 0) {
pair<T, T> p = get_seg(x);
if(p.first > p.second) return x;
return p.second + 1;
}
bool same(T x, T y) {
pair<T, T> p = get_seg(x);
return p.first <= p.second and p.first <= y and y <= p.second;
}
int size() {
return int(mp.size());
}
void out() {
for(auto [l, r] : mp) cout << "[" << l << ", " << r << "]\n";
}
};