This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub shibh308/library
// verify: https://atcoder.jp/contests/arc030/submissions/12211957/ template <typename T, typename U> struct RedBlackTree{ struct Node; using Index = typename MemoryPool<Node>::Index; struct Node{ int siz, level; T sum; U lazy; bool red; typename MemoryPool<Node>::Index l, r; Node(){} Node(T val, U lazy, bool red, bool leaf, int li = -1, int ri = -1) : sum(val), lazy(lazy), siz(leaf), level(0), red(red){ l = {li}; r = {ri}; } Node(T val, U lazy, bool red, bool leaf, Index l, Index r) : sum(val), lazy(lazy), siz(leaf), level(0), red(red), l(l), r(r){} }; MemoryPool<Node> pool; Index nil; function<T(T, T)> f; function<U(T, U, int)> g; function<U(U, U)> h; T op_t; U op_u; RedBlackTree(function<T(T, T)> f, function<T(T, U, int)> g, function<U(U, U)> h, T op_t, U op_u) : f(f), g(g), h(h), op_t(op_t), op_u(op_u){ nil = pool.alloc(); pool[nil] = Node(op_t, op_u, false, false); pool[nil].l = pool[nil].r = nil; } Index build(vector<T>& a){ nil = pool.alloc(); pool[nil] = Node(op_t, op_u, false, false); pool[nil].l = pool[nil].r = nil; int siz = a.size(); vector<Index> v(siz); for(int i = 0; i < siz; ++i) v[i] = make(a[i]); while(siz != 1){ int nex_siz = (siz + 1) >> 1; vector<Index> nex(nex_siz); for(int i = 0; i < (siz >> 1); ++i) nex[i] = merge(v[2 * i], v[2 * i + 1]); if(siz & 1) nex.back() = v.back(); siz = nex_siz; v = move(nex); } return v[0]; } void clear(){ while(!pool.st.empty()) pool.st.pop(); for(int i = 1; i <= pool.idx; ++i) pool.st.push(i); } Index index(int x){return {x};} T get_val(Index pi){ auto& p = get(pi); return g(p.sum, p.lazy, p.siz); } pair<T, Index> get_val(Index pi, int k){ Index root; tie(pi, root) = access(pi, k); return make_pair(get_val(pi), root); } pair<Index, bool> eval(Index pi){ if(pi == nil) return {pi, false}; if(get(pi).lazy == op_u) return {pi, false}; pi = clone(pi); auto& p = get(pi); if(p.l != nil){ p.l = clone(p.l); p.r = clone(p.r); auto& l = get(p.l); l.lazy = h(l.lazy, p.lazy); auto& r = get(p.r); r.lazy = h(r.lazy, p.lazy); } p.sum = get_val(pi); p.lazy = op_u; return {pi, true}; } Index make(T val){ Index idx = pool.alloc(); pool[idx] = Node(val, op_u, false, true, nil, nil); pool[idx].level = 1; return idx; } Index clone(Index pi){ if(pi == nil) return pi; Index qi = pool.alloc(); auto& p = get(pi); pool[qi] = Node(p.sum, p.lazy, p.red, false, p.l, p.r); pool[qi].siz = (p.l == nil ? 1 : pool[p.l].siz + pool[p.r].siz); pool[qi].level = pool[p.l].level + !pool[p.l].red; return qi; } Index makeInternal(Index l, Index r, bool red){ Index idx = pool.alloc(); pool[idx] = Node(op_t, op_u, red, false, l, r); pool[idx].sum = f(get_val(l), get_val(r)); pool[idx].siz = pool[l].siz + pool[r].siz; pool[idx].level = pool[l].level + !pool[l].red; return idx; } Index mergeSub(Index ai, Index bi){ ai = eval(ai).first; bi = eval(bi).first; auto& a = get(ai); auto& b = get(bi); assert(ai != nil && bi != nil); if(a.level < b.level){ Index ci = mergeSub(ai, b.l); auto& c = get(ci); if(!b.red && c.red && get(c.l).red){ if(!get(b.r).red) return makeInternal(c.l, makeInternal(c.r, b.r, true), false); else{ b.r = eval(b.r).first; return makeInternal(makeInternal(c.l, c.r, false), makeInternal(get(b.r).l, get(b.r).r, false), true); } } return makeInternal(ci, b.r, b.red); } else if(a.level > b.level){ Index ci = mergeSub(a.r, bi); auto& c = get(ci); if(!a.red && c.red && get(c.r).red){ if(!get(a.l).red) return makeInternal(makeInternal(a.l, c.l, true), c.r, false); else{ a.l = eval(a.l).first; return makeInternal(makeInternal(get(a.l).l, get(a.l).r, false), makeInternal(c.l, c.r, false), true); } } return makeInternal(a.l, ci, a.red); } else{ if(a.red) ai = makeInternal(a.l, a.r, false); if(b.red) bi = makeInternal(b.l, b.r, false); return makeInternal(ai, bi, true); } } Index merge(Index ai, Index bi){ if(ai == nil) return bi; if(bi == nil) return ai; Index ci = mergeSub(ai, bi); auto& c = get(ci); if(c.red){ pool.free(ci); return makeInternal(c.l, c.r, false); } return ci; } pair<Index, Index> split(Index ai, int k){ if(ai == nil) return make_pair(nil, nil); bool fl; tie(ai, fl) = eval(ai); auto& a = get(ai); if(k == 0) return make_pair(nil, ai); if(k == a.siz) return make_pair(ai, nil); Index li = a.l; Index ri = a.r; if(fl) pool.free(ai); auto& l = get(li); if(k < l.siz){ auto res = split(li, k); return make_pair(res.first, merge(res.second, ri)); } else if(k > get(a.l).siz){ auto res = split(ri, k - l.siz); return make_pair(merge(li, res.first), res.second); } else{ return make_pair(li, ri); } } pair<T, Index> range_get(Index pi, int l, int r){ auto res = split(pi, r); auto res2 = split(res.first, l); T val = get_val(res2.second); return make_pair(val, merge(merge(res2.first, res2.second), res.second)); } Index range_update(Index pi, int l, int r, U val){ if(l == r) return pi; auto res = split(pi, r); auto res2 = split(res.first, l); Index mi = clone(res2.second); auto& mid = get(mi); mid.lazy = h(mid.lazy, val); Index nex_mi; bool fl; tie(nex_mi, fl) = eval(mi); if(fl) pool.free(mi); return merge(merge(res2.first, nex_mi), res.second); } Index insert(Index pi, int k, T val){ auto res = split(pi, k); return merge(res.first, merge(make(val), res.second)); } Index erase(Index pi, int k){ auto res = split(pi, k + 1); auto res2 = split(res.first, k); return merge(res2.first, res.second); } pair<Index, Index> access(Index pi, int k){ auto res = split(pi, k + 1); auto res2 = split(res.first, k); return make_pair(res2.second, merge(merge(res2.first, res2.second), res.second)); } Index set(Index pi, int k, T val, function<T(T, T)> af = [](T x, T y){return y;}){ auto res = split(pi, k + 1); auto res2 = split(res.first, k); Index qi = eval(res2.second); get(qi).sum = af(get_val(qi), val); return make_pair(qi, merge(merge(res2.first, qi), res.second)); } void dump(Index pi, vector<T>& v){ Index qi = eval(pi).first; auto& q = get(qi); if(q.l != nil){ dump(q.l, v); dump(q.r, v); } else v.emplace_back(get_val(pi)); } vector<T> dump(Index pi){ vector<T> v; dump(pi, v); return v; } Index rebuild(Index pi){ auto v = dump(pi); clear(); return build(v); } Node& get(Index k){return pool[k];} Node& operator[](Index k){return pool[k];} };
#line 1 "lib/classes/redblacktree_persistent_lazy.cpp" // verify: https://atcoder.jp/contests/arc030/submissions/12211957/ template <typename T, typename U> struct RedBlackTree{ struct Node; using Index = typename MemoryPool<Node>::Index; struct Node{ int siz, level; T sum; U lazy; bool red; typename MemoryPool<Node>::Index l, r; Node(){} Node(T val, U lazy, bool red, bool leaf, int li = -1, int ri = -1) : sum(val), lazy(lazy), siz(leaf), level(0), red(red){ l = {li}; r = {ri}; } Node(T val, U lazy, bool red, bool leaf, Index l, Index r) : sum(val), lazy(lazy), siz(leaf), level(0), red(red), l(l), r(r){} }; MemoryPool<Node> pool; Index nil; function<T(T, T)> f; function<U(T, U, int)> g; function<U(U, U)> h; T op_t; U op_u; RedBlackTree(function<T(T, T)> f, function<T(T, U, int)> g, function<U(U, U)> h, T op_t, U op_u) : f(f), g(g), h(h), op_t(op_t), op_u(op_u){ nil = pool.alloc(); pool[nil] = Node(op_t, op_u, false, false); pool[nil].l = pool[nil].r = nil; } Index build(vector<T>& a){ nil = pool.alloc(); pool[nil] = Node(op_t, op_u, false, false); pool[nil].l = pool[nil].r = nil; int siz = a.size(); vector<Index> v(siz); for(int i = 0; i < siz; ++i) v[i] = make(a[i]); while(siz != 1){ int nex_siz = (siz + 1) >> 1; vector<Index> nex(nex_siz); for(int i = 0; i < (siz >> 1); ++i) nex[i] = merge(v[2 * i], v[2 * i + 1]); if(siz & 1) nex.back() = v.back(); siz = nex_siz; v = move(nex); } return v[0]; } void clear(){ while(!pool.st.empty()) pool.st.pop(); for(int i = 1; i <= pool.idx; ++i) pool.st.push(i); } Index index(int x){return {x};} T get_val(Index pi){ auto& p = get(pi); return g(p.sum, p.lazy, p.siz); } pair<T, Index> get_val(Index pi, int k){ Index root; tie(pi, root) = access(pi, k); return make_pair(get_val(pi), root); } pair<Index, bool> eval(Index pi){ if(pi == nil) return {pi, false}; if(get(pi).lazy == op_u) return {pi, false}; pi = clone(pi); auto& p = get(pi); if(p.l != nil){ p.l = clone(p.l); p.r = clone(p.r); auto& l = get(p.l); l.lazy = h(l.lazy, p.lazy); auto& r = get(p.r); r.lazy = h(r.lazy, p.lazy); } p.sum = get_val(pi); p.lazy = op_u; return {pi, true}; } Index make(T val){ Index idx = pool.alloc(); pool[idx] = Node(val, op_u, false, true, nil, nil); pool[idx].level = 1; return idx; } Index clone(Index pi){ if(pi == nil) return pi; Index qi = pool.alloc(); auto& p = get(pi); pool[qi] = Node(p.sum, p.lazy, p.red, false, p.l, p.r); pool[qi].siz = (p.l == nil ? 1 : pool[p.l].siz + pool[p.r].siz); pool[qi].level = pool[p.l].level + !pool[p.l].red; return qi; } Index makeInternal(Index l, Index r, bool red){ Index idx = pool.alloc(); pool[idx] = Node(op_t, op_u, red, false, l, r); pool[idx].sum = f(get_val(l), get_val(r)); pool[idx].siz = pool[l].siz + pool[r].siz; pool[idx].level = pool[l].level + !pool[l].red; return idx; } Index mergeSub(Index ai, Index bi){ ai = eval(ai).first; bi = eval(bi).first; auto& a = get(ai); auto& b = get(bi); assert(ai != nil && bi != nil); if(a.level < b.level){ Index ci = mergeSub(ai, b.l); auto& c = get(ci); if(!b.red && c.red && get(c.l).red){ if(!get(b.r).red) return makeInternal(c.l, makeInternal(c.r, b.r, true), false); else{ b.r = eval(b.r).first; return makeInternal(makeInternal(c.l, c.r, false), makeInternal(get(b.r).l, get(b.r).r, false), true); } } return makeInternal(ci, b.r, b.red); } else if(a.level > b.level){ Index ci = mergeSub(a.r, bi); auto& c = get(ci); if(!a.red && c.red && get(c.r).red){ if(!get(a.l).red) return makeInternal(makeInternal(a.l, c.l, true), c.r, false); else{ a.l = eval(a.l).first; return makeInternal(makeInternal(get(a.l).l, get(a.l).r, false), makeInternal(c.l, c.r, false), true); } } return makeInternal(a.l, ci, a.red); } else{ if(a.red) ai = makeInternal(a.l, a.r, false); if(b.red) bi = makeInternal(b.l, b.r, false); return makeInternal(ai, bi, true); } } Index merge(Index ai, Index bi){ if(ai == nil) return bi; if(bi == nil) return ai; Index ci = mergeSub(ai, bi); auto& c = get(ci); if(c.red){ pool.free(ci); return makeInternal(c.l, c.r, false); } return ci; } pair<Index, Index> split(Index ai, int k){ if(ai == nil) return make_pair(nil, nil); bool fl; tie(ai, fl) = eval(ai); auto& a = get(ai); if(k == 0) return make_pair(nil, ai); if(k == a.siz) return make_pair(ai, nil); Index li = a.l; Index ri = a.r; if(fl) pool.free(ai); auto& l = get(li); if(k < l.siz){ auto res = split(li, k); return make_pair(res.first, merge(res.second, ri)); } else if(k > get(a.l).siz){ auto res = split(ri, k - l.siz); return make_pair(merge(li, res.first), res.second); } else{ return make_pair(li, ri); } } pair<T, Index> range_get(Index pi, int l, int r){ auto res = split(pi, r); auto res2 = split(res.first, l); T val = get_val(res2.second); return make_pair(val, merge(merge(res2.first, res2.second), res.second)); } Index range_update(Index pi, int l, int r, U val){ if(l == r) return pi; auto res = split(pi, r); auto res2 = split(res.first, l); Index mi = clone(res2.second); auto& mid = get(mi); mid.lazy = h(mid.lazy, val); Index nex_mi; bool fl; tie(nex_mi, fl) = eval(mi); if(fl) pool.free(mi); return merge(merge(res2.first, nex_mi), res.second); } Index insert(Index pi, int k, T val){ auto res = split(pi, k); return merge(res.first, merge(make(val), res.second)); } Index erase(Index pi, int k){ auto res = split(pi, k + 1); auto res2 = split(res.first, k); return merge(res2.first, res.second); } pair<Index, Index> access(Index pi, int k){ auto res = split(pi, k + 1); auto res2 = split(res.first, k); return make_pair(res2.second, merge(merge(res2.first, res2.second), res.second)); } Index set(Index pi, int k, T val, function<T(T, T)> af = [](T x, T y){return y;}){ auto res = split(pi, k + 1); auto res2 = split(res.first, k); Index qi = eval(res2.second); get(qi).sum = af(get_val(qi), val); return make_pair(qi, merge(merge(res2.first, qi), res.second)); } void dump(Index pi, vector<T>& v){ Index qi = eval(pi).first; auto& q = get(qi); if(q.l != nil){ dump(q.l, v); dump(q.r, v); } else v.emplace_back(get_val(pi)); } vector<T> dump(Index pi){ vector<T> v; dump(pi, v); return v; } Index rebuild(Index pi){ auto v = dump(pi); clear(); return build(v); } Node& get(Index k){return pool[k];} Node& operator[](Index k){return pool[k];} };