#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include "template/template.hpp"
#include "data-structure/interval-set.hpp"
#include "util/xorshift.hpp"
constexpr int L = -20;
constexpr int R = 80;
vector<pair<int, int>> enumerate_naive(const vector<bool>& a, int l, int r) {
vector<pair<int, int>> ret;
l = max(l, L);
r = min(r, R);
for (int x = l; x < r;) {
if (!a[x - L]) {
x++;
continue;
}
int y = x;
while (y < r && a[y - L]) y++;
ret.push_back({x, y});
x = y;
}
return ret;
}
void check_points(const IntervalSet<int>& s, const vector<bool>& a) {
rep(x, L, R) assert(s.contains(x) == a[x - L]);
vector<pair<int, int>> intervals(s.begin(), s.end());
assert(intervals == enumerate_naive(a, L, R));
assert(s.empty() == intervals.empty());
}
void check_query(const IntervalSet<int>& s, const vector<bool>& a, int l, int r) {
bool ok = true;
rep(x, l, r) ok &= a[x - L];
assert(s.contains(l, r) == ok);
assert(s.enumerate(l, r) == enumerate_naive(a, l, r));
}
void check_full(const IntervalSet<int>& s, const vector<bool>& a) {
check_points(s, a);
rep(l, L, R + 1) rep(r, l, R + 1) {
check_query(s, a, l, r);
}
rep(x, L, R) {
auto itv = s.get(x);
if (!a[x - L]) {
assert(!itv);
} else {
int l = x, r = x + 1;
while (L < l && a[l - 1 - L]) l--;
while (r < R && a[r - L]) r++;
assert(itv);
assert(*itv == make_pair(l, r));
}
}
rep(x, L, R + 1) {
int expected = x;
while (expected < R && a[expected - L]) expected++;
assert(s.mex(x) == expected);
}
}
void check_random_queries(const IntervalSet<int>& s, const vector<bool>& a) {
check_points(s, a);
rep(_, 0, 20) {
int l = L + (int)(XORShift::xor32() % (R - L + 1));
int r = L + (int)(XORShift::xor32() % (R - L + 1));
if (l > r) swap(l, r);
check_query(s, a, l, r);
}
rep(_, 0, 20) {
int x = L + (int)(XORShift::xor32() % (R - L));
auto itv = s.get(x);
if (!a[x - L]) {
assert(!itv);
} else {
int l = x, r = x + 1;
while (L < l && a[l - 1 - L]) l--;
while (r < R && a[r - L]) r++;
assert(itv);
assert(*itv == make_pair(l, r));
}
}
rep(_, 0, 20) {
int x = L + (int)(XORShift::xor32() % (R - L + 1));
int expected = x;
while (expected < R && a[expected - L]) expected++;
assert(s.mex(x) == expected);
}
}
void test_fixed() {
IntervalSet<int> s;
vector<bool> a(R - L, false);
check_full(s, a);
s.add(1, 3);
s.add(3, 5);
rep(x, 1, 5) a[x - L] = true;
check_full(s, a);
s.remove(2, 4);
rep(x, 2, 4) a[x - L] = false;
check_full(s, a);
s.add(10);
a[10 - L] = true;
check_full(s, a);
s.remove(10);
a[10 - L] = false;
check_full(s, a);
s.clear();
fill(a.begin(), a.end(), false);
check_full(s, a);
}
void test_random() {
IntervalSet<int> s;
vector<bool> a(R - L, false);
rep(_, 0, 20000) {
int op = XORShift::xor32() % 6;
int l = L + (int)(XORShift::xor32() % (R - L + 1));
int r = L + (int)(XORShift::xor32() % (R - L + 1));
if (l > r) swap(l, r);
if (op == 0) {
s.add(l, r);
rep(x, l, r) a[x - L] = true;
} else if (op == 1) {
s.remove(l, r);
rep(x, l, r) a[x - L] = false;
} else if (op == 2) {
int x = L + (int)(XORShift::xor32() % (R - L));
s.add(x);
a[x - L] = true;
} else if (op == 3) {
int x = L + (int)(XORShift::xor32() % (R - L));
s.remove(x);
a[x - L] = false;
}
check_random_queries(s, a);
}
}
int main() {
test_fixed();
test_random();
int a, b;
in(a, b);
out(a + b);
}
#line 1 "verify/data-structure/UNIT_interval_set.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#line 2 "template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#line 2 "template/macro.hpp"
#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (int)(b) - 1; i >= (a); i--)
#define ALL(v) (v).begin(), (v).end()
#define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())
#define SZ(v) (int)v.size()
#define MIN(v) *min_element(ALL(v))
#define MAX(v) *max_element(ALL(v))
#define LB(v, x) int(lower_bound(ALL(v), (x)) - (v).begin())
#define UB(v, x) int(upper_bound(ALL(v), (x)) - (v).begin())
#define YN(b) cout << ((b) ? "YES" : "NO") << "\n";
#define Yn(b) cout << ((b) ? "Yes" : "No") << "\n";
#define yn(b) cout << ((b) ? "yes" : "no") << "\n";
#line 6 "template/template.hpp"
#line 2 "template/util.hpp"
using uint = unsigned int;
using ll = long long int;
using ull = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
template <class T, class S = T>
S SUM(const vector<T>& a) {
return accumulate(ALL(a), S(0));
}
template <class T>
inline bool chmin(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T>
inline bool chmax(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <class T>
int popcnt(T x) {
return __builtin_popcountll(x);
}
template <class T>
int topbit(T x) {
return (x == 0 ? -1 : 63 - __builtin_clzll(x));
}
template <class T>
int lowbit(T x) {
return (x == 0 ? -1 : __builtin_ctzll(x));
}
#line 8 "template/template.hpp"
#line 2 "template/inout.hpp"
struct Fast {
Fast() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cout << fixed << setprecision(15);
}
} fast;
ostream& operator<<(ostream& os, __uint128_t x) {
char buf[40];
size_t k = 0;
while (x > 0) buf[k++] = (char)(x % 10 + '0'), x /= 10;
if (k == 0) buf[k++] = '0';
while (k) os << buf[--k];
return os;
}
ostream& operator<<(ostream& os, __int128_t x) {
return x < 0 ? (os << '-' << (__uint128_t)(-x)) : (os << (__uint128_t)x);
}
template <class T1, class T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
return is >> p.first >> p.second;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
return os << p.first << " " << p.second;
}
template <class T>
istream& operator>>(istream& is, vector<T>& a) {
for (auto& v : a) is >> v;
return is;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& a) {
for (auto it = a.begin(); it != a.end();) {
os << *it;
if (++it != a.end()) os << " ";
}
return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& st) {
os << "{";
for (auto it = st.begin(); it != st.end();) {
os << *it;
if (++it != st.end()) os << ",";
}
os << "}";
return os;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const map<T1, T2>& mp) {
os << "{";
for (auto it = mp.begin(); it != mp.end();) {
os << it->first << ":" << it->second;
if (++it != mp.end()) os << ",";
}
os << "}";
return os;
}
void in() {}
template <typename T, class... U>
void in(T& t, U&... u) {
cin >> t;
in(u...);
}
void out() { cout << "\n"; }
template <typename T, class... U, char sep = ' '>
void out(const T& t, const U&... u) {
cout << t;
if (sizeof...(u)) cout << sep;
out(u...);
}
namespace IO {
namespace Graph {
vector<vector<int>> unweighted(int n, int m, bool directed = false, int offset = 1) {
vector<vector<int>> g(n);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
u -= offset, v -= offset;
g[u].push_back(v);
if (!directed) g[v].push_back(u);
}
return g;
}
template <class T>
vector<vector<pair<int, T>>> weighted(int n, int m, bool directed = false, int offset = 1) {
vector<vector<pair<int, T>>> g(n);
for (int i = 0; i < m; i++) {
int u, v;
T w;
cin >> u >> v >> w;
u -= offset, v -= offset;
g[u].push_back({v, w});
if (!directed) g[v].push_back({u, w});
}
return g;
}
} // namespace Graph
namespace Tree {
vector<vector<int>> unweighted(int n, bool directed = false, int offset = 1) {
return Graph::unweighted(n, n - 1, directed, offset);
}
template <class T>
vector<vector<pair<int, T>>> weighted(int n, bool directed = false, int offset = 1) {
return Graph::weighted<T>(n, n - 1, directed, offset);
}
vector<vector<int>> rooted(int n, bool to_root = true, bool to_leaf = true, int offset = 1) {
vector<vector<int>> g(n);
for (int i = 1; i < n; i++) {
int p;
cin >> p;
p -= offset;
if (to_root) g[i].push_back(p);
if (to_leaf) g[p].push_back(i);
}
return g;
}
} // namespace Tree
} // namespace IO
#line 10 "template/template.hpp"
#line 2 "template/debug.hpp"
#ifdef LOCAL
#define debug 1
#define show(...) _show(0, #__VA_ARGS__, __VA_ARGS__)
#else
#define debug 0
#define show(...) true
#endif
template <class T>
void _show(int i, T name) {
cerr << '\n';
}
template <class T1, class T2, class... T3>
void _show(int i, const T1& a, const T2& b, const T3&... c) {
for (; a[i] != ',' && a[i] != '\0'; i++) cerr << a[i];
cerr << ":" << b << " ";
_show(i + 1, a, c...);
}
#line 2 "data-structure/interval-set.hpp"
template <class T>
struct IntervalSet {
using value_type = pair<T, T>;
IntervalSet() = default;
bool contains(T x) const {
auto it = LR.upper_bound({x, INF});
if (it == LR.begin()) return false;
--it;
return it->first <= x && x < it->second;
}
bool contains(T l, T r) const {
assert(l <= r);
if (l == r) return true;
auto it = LR.upper_bound({l, INF});
if (it == LR.begin()) return false;
--it;
return it->first <= l && r <= it->second;
}
optional<value_type> get(T x) const {
auto it = LR.upper_bound({x, INF});
if (it == LR.begin()) return nullopt;
--it;
if (it->first <= x && x < it->second) return *it;
return nullopt;
}
void add(T x) {
assert(x < INF);
add(x, x + 1);
}
void add(T l, T r) {
assert(l <= r);
if (l == r) return;
auto it = LR.upper_bound({l, INF});
if (it != LR.begin()) {
auto pre = prev(it);
if (l <= pre->second) {
l = pre->first;
r = max(r, pre->second);
it = LR.erase(pre);
}
}
while (it != LR.end() && it->first <= r) {
r = max(r, it->second);
it = LR.erase(it);
}
LR.insert({l, r});
}
void remove(T x) {
assert(x < INF);
remove(x, x + 1);
}
void remove(T l, T r) {
assert(l <= r);
if (l == r) return;
auto it = LR.upper_bound({l, INF});
if (it != LR.begin()) {
auto pre = prev(it);
if (l < pre->second) {
T l1 = pre->first, r1 = pre->second;
LR.erase(pre);
if (l1 < l) LR.insert({l1, l});
if (r < r1) {
LR.insert({r, r1});
return;
}
}
}
while (it != LR.end() && it->first < r) {
T r1 = it->second;
it = LR.erase(it);
if (r < r1) {
LR.insert({r, r1});
break;
}
}
}
vector<value_type> enumerate(T l, T r) const {
assert(l <= r);
vector<value_type> ret;
if (l == r) return ret;
auto it = LR.upper_bound({l, INF});
if (it != LR.begin()) {
auto pre = prev(it);
if (l < pre->second) it = pre;
}
while (it != LR.end() && it->first < r) {
ret.push_back({max(l, it->first), min(r, it->second)});
++it;
}
return ret;
}
T mex(T x = 0) const {
auto it = LR.upper_bound({x, INF});
if (it != LR.begin()) {
auto pre = prev(it);
if (pre->first <= x && x < pre->second) x = pre->second;
}
while (it != LR.end() && it->first <= x) {
if (x < it->second) x = it->second;
++it;
}
return x;
}
bool empty() const { return LR.empty(); }
void clear() { LR.clear(); }
auto begin() const { return LR.begin(); }
auto end() const { return LR.end(); }
private:
static constexpr T INF = numeric_limits<T>::max();
set<value_type> LR;
};
/**
* @brief 区間集合
* @docs docs/data-structure/interval-set.md
*/
#line 2 "util/xorshift.hpp"
namespace XORShift {
unsigned int xor32() {
static unsigned int x = 123456789u;
x ^= x << 13, x ^= x >> 17, x ^= x << 5;
return x;
}
unsigned long long xor64() {
static unsigned long long x = 123456789ull;
x ^= x << 13, x ^= x >> 7, x ^= x << 17;
return x;
}
}; // namespace XORShift
/**
* @brief XOR shift
*/
#line 6 "verify/data-structure/UNIT_interval_set.test.cpp"
constexpr int L = -20;
constexpr int R = 80;
vector<pair<int, int>> enumerate_naive(const vector<bool>& a, int l, int r) {
vector<pair<int, int>> ret;
l = max(l, L);
r = min(r, R);
for (int x = l; x < r;) {
if (!a[x - L]) {
x++;
continue;
}
int y = x;
while (y < r && a[y - L]) y++;
ret.push_back({x, y});
x = y;
}
return ret;
}
void check_points(const IntervalSet<int>& s, const vector<bool>& a) {
rep(x, L, R) assert(s.contains(x) == a[x - L]);
vector<pair<int, int>> intervals(s.begin(), s.end());
assert(intervals == enumerate_naive(a, L, R));
assert(s.empty() == intervals.empty());
}
void check_query(const IntervalSet<int>& s, const vector<bool>& a, int l, int r) {
bool ok = true;
rep(x, l, r) ok &= a[x - L];
assert(s.contains(l, r) == ok);
assert(s.enumerate(l, r) == enumerate_naive(a, l, r));
}
void check_full(const IntervalSet<int>& s, const vector<bool>& a) {
check_points(s, a);
rep(l, L, R + 1) rep(r, l, R + 1) {
check_query(s, a, l, r);
}
rep(x, L, R) {
auto itv = s.get(x);
if (!a[x - L]) {
assert(!itv);
} else {
int l = x, r = x + 1;
while (L < l && a[l - 1 - L]) l--;
while (r < R && a[r - L]) r++;
assert(itv);
assert(*itv == make_pair(l, r));
}
}
rep(x, L, R + 1) {
int expected = x;
while (expected < R && a[expected - L]) expected++;
assert(s.mex(x) == expected);
}
}
void check_random_queries(const IntervalSet<int>& s, const vector<bool>& a) {
check_points(s, a);
rep(_, 0, 20) {
int l = L + (int)(XORShift::xor32() % (R - L + 1));
int r = L + (int)(XORShift::xor32() % (R - L + 1));
if (l > r) swap(l, r);
check_query(s, a, l, r);
}
rep(_, 0, 20) {
int x = L + (int)(XORShift::xor32() % (R - L));
auto itv = s.get(x);
if (!a[x - L]) {
assert(!itv);
} else {
int l = x, r = x + 1;
while (L < l && a[l - 1 - L]) l--;
while (r < R && a[r - L]) r++;
assert(itv);
assert(*itv == make_pair(l, r));
}
}
rep(_, 0, 20) {
int x = L + (int)(XORShift::xor32() % (R - L + 1));
int expected = x;
while (expected < R && a[expected - L]) expected++;
assert(s.mex(x) == expected);
}
}
void test_fixed() {
IntervalSet<int> s;
vector<bool> a(R - L, false);
check_full(s, a);
s.add(1, 3);
s.add(3, 5);
rep(x, 1, 5) a[x - L] = true;
check_full(s, a);
s.remove(2, 4);
rep(x, 2, 4) a[x - L] = false;
check_full(s, a);
s.add(10);
a[10 - L] = true;
check_full(s, a);
s.remove(10);
a[10 - L] = false;
check_full(s, a);
s.clear();
fill(a.begin(), a.end(), false);
check_full(s, a);
}
void test_random() {
IntervalSet<int> s;
vector<bool> a(R - L, false);
rep(_, 0, 20000) {
int op = XORShift::xor32() % 6;
int l = L + (int)(XORShift::xor32() % (R - L + 1));
int r = L + (int)(XORShift::xor32() % (R - L + 1));
if (l > r) swap(l, r);
if (op == 0) {
s.add(l, r);
rep(x, l, r) a[x - L] = true;
} else if (op == 1) {
s.remove(l, r);
rep(x, l, r) a[x - L] = false;
} else if (op == 2) {
int x = L + (int)(XORShift::xor32() % (R - L));
s.add(x);
a[x - L] = true;
} else if (op == 3) {
int x = L + (int)(XORShift::xor32() % (R - L));
s.remove(x);
a[x - L] = false;
}
check_random_queries(s, a);
}
}
int main() {
test_fixed();
test_random();
int a, b;
in(a, b);
out(a + b);
}
verify/data-structure/UNIT_interval_set.test.cpp