This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub maspypy/library
#include "ds/intervals.hpp"
#include "ds/fastset.hpp" // FastSet で高速化したもの template <typename T> struct Intervals_Fast { const int LLIM, RLIM; const T none_val; // none_val でない区間の個数と長さ合計 int total_num; int total_len; vc<T> dat; FastSet ss; Intervals_Fast(int N, T none_val) : LLIM(0), RLIM(N), none_val(none_val), total_num(0), total_len(0), dat(N, none_val), ss(N) { ss.insert(0); } // x を含む区間の情報の取得 l, r, t tuple<int, int, T> get(int x, bool ERASE = false) { int l = ss.prev(x); int r = ss.next(x + 1); T t = dat[l]; if (t != none_val && ERASE) { --total_num, total_len -= r - l; dat[l] = none_val; merge_at(l); merge_at(r); } return {l, r, t}; } // [L, R) 内の全データの取得 // f(l,r,x) template <typename F> void enumerate_range(int L, int R, F f, bool ERASE = false) { assert(LLIM <= L && L <= R && R <= RLIM); if (L == R) return; if (!ERASE) { int l = ss.prev(L); while (l < R) { int r = ss.next(l + 1); f(max(l, L), min(r, R), dat[l]); l = r; } return; } // 半端なところの分割 int p = ss.prev(L); if (p < L) { ss.insert(L); dat[L] = dat[p]; if (dat[L] != none_val) ++total_num; } p = ss.next(R); if (R < p) { dat[R] = dat[ss.prev(R)]; ss.insert(R); if (dat[R] != none_val) ++total_num; } p = L; while (p < R) { int q = ss.next(p + 1); T x = dat[p]; f(p, q, x); if (dat[p] != none_val) --total_num, total_len -= q - p; ss.erase(p); p = q; } ss.insert(L); dat[L] = none_val; } void set(int L, int R, T t) { if (L == R) return; enumerate_range( L, R, [](int l, int r, T x) -> void {}, true); ss.insert(L); dat[L] = t; if (t != none_val) total_num++, total_len += R - L; merge_at(L); merge_at(R); } template <typename F> void enumerate_all(F f) { enumerate_range(0, RLIM, f, false); } void merge_at(int p) { if (p <= 0 || RLIM <= p) return; int q = ss.prev(p - 1); if (dat[p] == dat[q]) { if (dat[p] != none_val) --total_num; ss.erase(p); } } }; // https://codeforces.com/contest/1638/problem/E // 持つ値のタイプ T、座標タイプ X // コンストラクタでは T none_val を指定する // 先読み可能なら座圧して fastset の方が速い template <typename T, typename X = ll> struct Intervals { static constexpr X LLIM = -infty<X>; static constexpr X RLIM = infty<X>; T none_val; // const T none_val; // none_val でない区間の個数と長さ合計 int total_num; X total_len; map<X, T> dat; Intervals(T none_val) : none_val(none_val), total_num(0), total_len(0) { dat[LLIM] = none_val; dat[RLIM] = none_val; } // x を含む区間の情報の取得 l, r, t tuple<X, X, T> get(X x, bool ERASE = false) { auto it2 = dat.upper_bound(x); auto it1 = prev(it2); auto [l, tl] = *it1; auto [r, tr] = *it2; if (tl != none_val && ERASE) { --total_num, total_len -= r - l; dat[l] = none_val; merge_at(l); merge_at(r); } return {l, r, tl}; } // [L, R) 内の全データの取得 f(l, r, t) template <typename F> void enumerate_range(X L, X R, F f, bool ERASE = false) { assert(LLIM <= L && L <= R && R <= RLIM); if (!ERASE) { auto it = prev(dat.upper_bound(L)); while ((*it).fi < R) { auto it2 = next(it); f(max((*it).fi, L), min((*it2).fi, R), (*it).se); it = it2; } return; } // 半端なところの分割 auto p = prev(dat.upper_bound(L)); if ((*p).fi < L) { dat[L] = (*p).se; if (dat[L] != none_val) ++total_num; } p = dat.lower_bound(R); if (R < (*p).fi) { T t = (*prev(p)).se; dat[R] = t; if (t != none_val) ++total_num; } p = dat.lower_bound(L); while (1) { if ((*p).fi >= R) break; auto q = next(p); T t = (*p).se; f((*p).fi, (*q).fi, t); if (t != none_val) --total_num, total_len -= (*q).fi - (*p).fi; p = dat.erase(p); } dat[L] = none_val; } void set(X L, X R, T t) { assert(L <= R); if (L == R) return; enumerate_range( L, R, [](int l, int r, T x) -> void {}, true); dat[L] = t; if (t != none_val) total_num++, total_len += R - L; merge_at(L); merge_at(R); } template <typename F> void enumerate_all(F f) { enumerate_range(LLIM, RLIM, f, false); } void merge_at(X p) { if (p == LLIM || RLIM == p) return; auto itp = dat.lower_bound(p); assert((*itp).fi == p); auto itq = prev(itp); if ((*itp).se == (*itq).se) { if ((*itp).se != none_val) --total_num; dat.erase(itp); } } };
#line 2 "ds/fastset.hpp" // 64-ary tree // space: (N/63) * u64 struct FastSet { static constexpr u32 B = 64; int n, log; vvc<u64> seg; FastSet() {} FastSet(int n) { build(n); } int size() { return n; } template <typename F> FastSet(int n, F f) { build(n, f); } void build(int m) { seg.clear(); n = m; do { seg.push_back(vc<u64>((m + B - 1) / B)); m = (m + B - 1) / B; } while (m > 1); log = len(seg); } template <typename F> void build(int n, F f) { build(n); FOR(i, n) { seg[0][i / B] |= u64(f(i)) << (i % B); } FOR(h, log - 1) { FOR(i, len(seg[h])) { seg[h + 1][i / B] |= u64(bool(seg[h][i])) << (i % B); } } } bool operator[](int i) const { return seg[0][i / B] >> (i % B) & 1; } void insert(int i) { assert(0 <= i && i < n); for (int h = 0; h < log; h++) { seg[h][i / B] |= u64(1) << (i % B), i /= B; } } void add(int i) { insert(i); } void erase(int i) { assert(0 <= i && i < n); u64 x = 0; for (int h = 0; h < log; h++) { seg[h][i / B] &= ~(u64(1) << (i % B)); seg[h][i / B] |= x << (i % B); x = bool(seg[h][i / B]); i /= B; } } void remove(int i) { erase(i); } // min[x,n) or n int next(int i) { assert(i <= n); chmax(i, 0); for (int h = 0; h < log; h++) { if (i / B == seg[h].size()) break; u64 d = seg[h][i / B] >> (i % B); if (!d) { i = i / B + 1; continue; } i += lowbit(d); for (int g = h - 1; g >= 0; g--) { i *= B; i += lowbit(seg[g][i / B]); } return i; } return n; } // max [0,x], or -1 int prev(int i) { assert(i >= -1); if (i >= n) i = n - 1; for (int h = 0; h < log; h++) { if (i == -1) break; u64 d = seg[h][i / B] << (63 - i % B); if (!d) { i = i / B - 1; continue; } i -= __builtin_clzll(d); for (int g = h - 1; g >= 0; g--) { i *= B; i += topbit(seg[g][i / B]); } return i; } return -1; } bool any(int l, int r) { return next(l) < r; } // [l, r) template <typename F> void enumerate(int l, int r, F f) { for (int x = next(l); x < r; x = next(x + 1)) f(x); } string to_string() { string s(n, '?'); for (int i = 0; i < n; ++i) s[i] = ((*this)[i] ? '1' : '0'); return s; } }; #line 2 "ds/intervals.hpp" // FastSet で高速化したもの template <typename T> struct Intervals_Fast { const int LLIM, RLIM; const T none_val; // none_val でない区間の個数と長さ合計 int total_num; int total_len; vc<T> dat; FastSet ss; Intervals_Fast(int N, T none_val) : LLIM(0), RLIM(N), none_val(none_val), total_num(0), total_len(0), dat(N, none_val), ss(N) { ss.insert(0); } // x を含む区間の情報の取得 l, r, t tuple<int, int, T> get(int x, bool ERASE = false) { int l = ss.prev(x); int r = ss.next(x + 1); T t = dat[l]; if (t != none_val && ERASE) { --total_num, total_len -= r - l; dat[l] = none_val; merge_at(l); merge_at(r); } return {l, r, t}; } // [L, R) 内の全データの取得 // f(l,r,x) template <typename F> void enumerate_range(int L, int R, F f, bool ERASE = false) { assert(LLIM <= L && L <= R && R <= RLIM); if (L == R) return; if (!ERASE) { int l = ss.prev(L); while (l < R) { int r = ss.next(l + 1); f(max(l, L), min(r, R), dat[l]); l = r; } return; } // 半端なところの分割 int p = ss.prev(L); if (p < L) { ss.insert(L); dat[L] = dat[p]; if (dat[L] != none_val) ++total_num; } p = ss.next(R); if (R < p) { dat[R] = dat[ss.prev(R)]; ss.insert(R); if (dat[R] != none_val) ++total_num; } p = L; while (p < R) { int q = ss.next(p + 1); T x = dat[p]; f(p, q, x); if (dat[p] != none_val) --total_num, total_len -= q - p; ss.erase(p); p = q; } ss.insert(L); dat[L] = none_val; } void set(int L, int R, T t) { if (L == R) return; enumerate_range( L, R, [](int l, int r, T x) -> void {}, true); ss.insert(L); dat[L] = t; if (t != none_val) total_num++, total_len += R - L; merge_at(L); merge_at(R); } template <typename F> void enumerate_all(F f) { enumerate_range(0, RLIM, f, false); } void merge_at(int p) { if (p <= 0 || RLIM <= p) return; int q = ss.prev(p - 1); if (dat[p] == dat[q]) { if (dat[p] != none_val) --total_num; ss.erase(p); } } }; // https://codeforces.com/contest/1638/problem/E // 持つ値のタイプ T、座標タイプ X // コンストラクタでは T none_val を指定する // 先読み可能なら座圧して fastset の方が速い template <typename T, typename X = ll> struct Intervals { static constexpr X LLIM = -infty<X>; static constexpr X RLIM = infty<X>; T none_val; // const T none_val; // none_val でない区間の個数と長さ合計 int total_num; X total_len; map<X, T> dat; Intervals(T none_val) : none_val(none_val), total_num(0), total_len(0) { dat[LLIM] = none_val; dat[RLIM] = none_val; } // x を含む区間の情報の取得 l, r, t tuple<X, X, T> get(X x, bool ERASE = false) { auto it2 = dat.upper_bound(x); auto it1 = prev(it2); auto [l, tl] = *it1; auto [r, tr] = *it2; if (tl != none_val && ERASE) { --total_num, total_len -= r - l; dat[l] = none_val; merge_at(l); merge_at(r); } return {l, r, tl}; } // [L, R) 内の全データの取得 f(l, r, t) template <typename F> void enumerate_range(X L, X R, F f, bool ERASE = false) { assert(LLIM <= L && L <= R && R <= RLIM); if (!ERASE) { auto it = prev(dat.upper_bound(L)); while ((*it).fi < R) { auto it2 = next(it); f(max((*it).fi, L), min((*it2).fi, R), (*it).se); it = it2; } return; } // 半端なところの分割 auto p = prev(dat.upper_bound(L)); if ((*p).fi < L) { dat[L] = (*p).se; if (dat[L] != none_val) ++total_num; } p = dat.lower_bound(R); if (R < (*p).fi) { T t = (*prev(p)).se; dat[R] = t; if (t != none_val) ++total_num; } p = dat.lower_bound(L); while (1) { if ((*p).fi >= R) break; auto q = next(p); T t = (*p).se; f((*p).fi, (*q).fi, t); if (t != none_val) --total_num, total_len -= (*q).fi - (*p).fi; p = dat.erase(p); } dat[L] = none_val; } void set(X L, X R, T t) { assert(L <= R); if (L == R) return; enumerate_range( L, R, [](int l, int r, T x) -> void {}, true); dat[L] = t; if (t != none_val) total_num++, total_len += R - L; merge_at(L); merge_at(R); } template <typename F> void enumerate_all(F f) { enumerate_range(LLIM, RLIM, f, false); } void merge_at(X p) { if (p == LLIM || RLIM == p) return; auto itp = dat.lower_bound(p); assert((*itp).fi == p); auto itq = prev(itp); if ((*itp).se == (*itq).se) { if ((*itp).se != none_val) --total_num; dat.erase(itp); } } };