#include "rbst/treap.hpp"
#pragma once #include "../misc/rng.hpp" template <typename Node> struct TreapBase { using Ptr = Node *; template <typename... Args> inline Ptr my_new(Args... args) { return new Node(args...); } Ptr make_tree() { return nullptr; } // for avoiding memory leak, activate below /* using Ptr = shared_ptr<Node>; template <typename... Args> inline Ptr my_new(Args... args) { return make_shared<Node>(args...); } Ptr make_tree() {return Ptr();} */ int size(Ptr t) const { return count(t); } Ptr merge(Ptr l, Ptr r) { if (!l || !r) return l ? l : r; if (l->pr >= r->pr) { push(l); l->r = merge(l->r, r); return update(l); } else { push(r); r->l = merge(l, r->l); return update(r); } } pair<Ptr, Ptr> split(Ptr t, int k) { if (!t) return {nullptr, nullptr}; push(t); if (k <= count(t->l)) { auto s = split(t->l, k); t->l = s.second; return {s.first, update(t)}; } else { auto s = split(t->r, k - count(t->l) - 1); t->r = s.first; return {update(t), s.second}; } } Ptr build(const vector<decltype(Node::key)> &v) { int n = v.size(); vector<Ptr> ps; ps.reserve(n); for (int i = 0; i < n; i++) ps.push_back(my_new(v[i])); vector<int> p(n, -1), st; for (int i = 0; i < n; i++) { int prv = -1; while (!st.empty() && ps[i]->pr > ps[st.back()]->pr) { prv = st.back(); st.pop_back(); } if (prv != -1) p[prv] = i; if (!st.empty()) p[i] = st.back(); st.push_back(i); } int root = -1; for (int i = 0; i < n; i++) { if (p[i] != -1) { if (i < p[i]) { ps[p[i]]->l = ps[i]; } else { ps[p[i]]->r = ps[i]; } } else root = i; } dfs(ps[root]); return ps[root]; } template <typename... Args> void insert(Ptr &t, int k, const Args &...args) { auto x = split(t, k); t = merge(merge(x.first, my_new(args...)), x.second); } void erase(Ptr &t, int k) { auto x = split(t, k); t = merge(x.first, split(x.second, 1).second); } protected: void dfs(Ptr r) { if (r->l) dfs(r->l); if (r->r) dfs(r->r); update(r); } inline int count(const Ptr t) const { return t ? t->cnt : 0; } virtual void push(Ptr) {} virtual Ptr update(Ptr) = 0; }; template <typename T, typename E> struct LazyReversibleTreapNode { using Treap = TreapBase<LazyReversibleTreapNode>; typename Treap::Ptr l, r; T key, sum; E lazy; int cnt; uint32_t pr; bool rev; LazyReversibleTreapNode(const T &t = T(), const E &e = E()) : l(), r(), key(t), sum(t), lazy(e), cnt(1), pr(my_rand::rng()), rev(false) {} }; template <typename T, typename E, T (*f)(T, T), T (*g)(T, E), E (*h)(E, E), T (*ts)(T)> struct LazyReversibleTreap : TreapBase<LazyReversibleTreapNode<T, E>> { using Node = LazyReversibleTreapNode<T, E>; using base = TreapBase<LazyReversibleTreapNode<T, E>>; using base::merge; using base::split; using typename base::Ptr; LazyReversibleTreap() = default; void toggle(Ptr t) { if (!t) return; swap(t->l, t->r); t->sum = ts(t->sum); t->rev ^= true; } T fold(Ptr &t, int a, int b) { auto x = split(t, a); auto y = split(x.second, b - a); auto ret = sum(y.first); t = merge(x.first, merge(y.first, y.second)); return ret; } void reverse(Ptr &t, int a, int b) { auto x = split(t, a); auto y = split(x.second, b - a); toggle(y.first); t = merge(x.first, merge(y.first, y.second)); } void apply(Ptr &t, int a, int b, const E &e) { auto x = split(t, a); auto y = split(x.second, b - a); propagate(y.first, e); t = merge(x.first, merge(y.first, y.second)); } protected: inline T sum(const Ptr t) const { return t ? t->sum : T(); } Ptr update(Ptr t) override { push(t); t->cnt = 1; t->sum = t->key; if (t->l) t->cnt += t->l->cnt, t->sum = f(t->l->sum, t->sum); if (t->r) t->cnt += t->r->cnt, t->sum = f(t->sum, t->r->sum); return t; } void push(Ptr t) override { if (t->rev) { if (t->l) toggle(t->l); if (t->r) toggle(t->r); t->rev = false; } if (t->lazy != E()) { if (t->l) propagate(t->l, t->lazy); if (t->r) propagate(t->r, t->lazy); t->lazy = E(); } } void propagate(Ptr t, const E &x) { t->lazy = h(t->lazy, x); t->key = g(t->key, x); t->sum = g(t->sum, x); } }; /** * @brief 遅延伝搬反転可能Treap */
#line 2 "rbst/treap.hpp" #line 2 "misc/rng.hpp" #line 2 "internal/internal-seed.hpp" #include <chrono> using namespace std; namespace internal { unsigned long long non_deterministic_seed() { unsigned long long m = chrono::duration_cast<chrono::nanoseconds>( chrono::high_resolution_clock::now().time_since_epoch()) .count(); m ^= 9845834732710364265uLL; m ^= m << 24, m ^= m >> 31, m ^= m << 35; return m; } unsigned long long deterministic_seed() { return 88172645463325252UL; } // 64 bit の seed 値を生成 (手元では seed 固定) // 連続で呼び出すと同じ値が何度も返ってくるので注意 // #define RANDOMIZED_SEED するとシードがランダムになる unsigned long long seed() { #if defined(NyaanLocal) && !defined(RANDOMIZED_SEED) return deterministic_seed(); #else return non_deterministic_seed(); #endif } } // namespace internal #line 4 "misc/rng.hpp" namespace my_rand { using i64 = long long; using u64 = unsigned long long; // [0, 2^64 - 1) u64 rng() { static u64 _x = internal::seed(); return _x ^= _x << 7, _x ^= _x >> 9; } // [l, r] i64 rng(i64 l, i64 r) { assert(l <= r); return l + rng() % u64(r - l + 1); } // [l, r) i64 randint(i64 l, i64 r) { assert(l < r); return l + rng() % u64(r - l); } // choose n numbers from [l, r) without overlapping vector<i64> randset(i64 l, i64 r, i64 n) { assert(l <= r && n <= r - l); unordered_set<i64> s; for (i64 i = n; i; --i) { i64 m = randint(l, r + 1 - i); if (s.find(m) != s.end()) m = r - i; s.insert(m); } vector<i64> ret; for (auto& x : s) ret.push_back(x); return ret; } // [0.0, 1.0) double rnd() { return rng() * 5.42101086242752217004e-20; } // [l, r) double rnd(double l, double r) { assert(l < r); return l + rnd() * (r - l); } template <typename T> void randshf(vector<T>& v) { int n = v.size(); for (int i = 1; i < n; i++) swap(v[i], v[randint(0, i + 1)]); } } // namespace my_rand using my_rand::randint; using my_rand::randset; using my_rand::randshf; using my_rand::rnd; using my_rand::rng; #line 4 "rbst/treap.hpp" template <typename Node> struct TreapBase { using Ptr = Node *; template <typename... Args> inline Ptr my_new(Args... args) { return new Node(args...); } Ptr make_tree() { return nullptr; } // for avoiding memory leak, activate below /* using Ptr = shared_ptr<Node>; template <typename... Args> inline Ptr my_new(Args... args) { return make_shared<Node>(args...); } Ptr make_tree() {return Ptr();} */ int size(Ptr t) const { return count(t); } Ptr merge(Ptr l, Ptr r) { if (!l || !r) return l ? l : r; if (l->pr >= r->pr) { push(l); l->r = merge(l->r, r); return update(l); } else { push(r); r->l = merge(l, r->l); return update(r); } } pair<Ptr, Ptr> split(Ptr t, int k) { if (!t) return {nullptr, nullptr}; push(t); if (k <= count(t->l)) { auto s = split(t->l, k); t->l = s.second; return {s.first, update(t)}; } else { auto s = split(t->r, k - count(t->l) - 1); t->r = s.first; return {update(t), s.second}; } } Ptr build(const vector<decltype(Node::key)> &v) { int n = v.size(); vector<Ptr> ps; ps.reserve(n); for (int i = 0; i < n; i++) ps.push_back(my_new(v[i])); vector<int> p(n, -1), st; for (int i = 0; i < n; i++) { int prv = -1; while (!st.empty() && ps[i]->pr > ps[st.back()]->pr) { prv = st.back(); st.pop_back(); } if (prv != -1) p[prv] = i; if (!st.empty()) p[i] = st.back(); st.push_back(i); } int root = -1; for (int i = 0; i < n; i++) { if (p[i] != -1) { if (i < p[i]) { ps[p[i]]->l = ps[i]; } else { ps[p[i]]->r = ps[i]; } } else root = i; } dfs(ps[root]); return ps[root]; } template <typename... Args> void insert(Ptr &t, int k, const Args &...args) { auto x = split(t, k); t = merge(merge(x.first, my_new(args...)), x.second); } void erase(Ptr &t, int k) { auto x = split(t, k); t = merge(x.first, split(x.second, 1).second); } protected: void dfs(Ptr r) { if (r->l) dfs(r->l); if (r->r) dfs(r->r); update(r); } inline int count(const Ptr t) const { return t ? t->cnt : 0; } virtual void push(Ptr) {} virtual Ptr update(Ptr) = 0; }; template <typename T, typename E> struct LazyReversibleTreapNode { using Treap = TreapBase<LazyReversibleTreapNode>; typename Treap::Ptr l, r; T key, sum; E lazy; int cnt; uint32_t pr; bool rev; LazyReversibleTreapNode(const T &t = T(), const E &e = E()) : l(), r(), key(t), sum(t), lazy(e), cnt(1), pr(my_rand::rng()), rev(false) {} }; template <typename T, typename E, T (*f)(T, T), T (*g)(T, E), E (*h)(E, E), T (*ts)(T)> struct LazyReversibleTreap : TreapBase<LazyReversibleTreapNode<T, E>> { using Node = LazyReversibleTreapNode<T, E>; using base = TreapBase<LazyReversibleTreapNode<T, E>>; using base::merge; using base::split; using typename base::Ptr; LazyReversibleTreap() = default; void toggle(Ptr t) { if (!t) return; swap(t->l, t->r); t->sum = ts(t->sum); t->rev ^= true; } T fold(Ptr &t, int a, int b) { auto x = split(t, a); auto y = split(x.second, b - a); auto ret = sum(y.first); t = merge(x.first, merge(y.first, y.second)); return ret; } void reverse(Ptr &t, int a, int b) { auto x = split(t, a); auto y = split(x.second, b - a); toggle(y.first); t = merge(x.first, merge(y.first, y.second)); } void apply(Ptr &t, int a, int b, const E &e) { auto x = split(t, a); auto y = split(x.second, b - a); propagate(y.first, e); t = merge(x.first, merge(y.first, y.second)); } protected: inline T sum(const Ptr t) const { return t ? t->sum : T(); } Ptr update(Ptr t) override { push(t); t->cnt = 1; t->sum = t->key; if (t->l) t->cnt += t->l->cnt, t->sum = f(t->l->sum, t->sum); if (t->r) t->cnt += t->r->cnt, t->sum = f(t->sum, t->r->sum); return t; } void push(Ptr t) override { if (t->rev) { if (t->l) toggle(t->l); if (t->r) toggle(t->r); t->rev = false; } if (t->lazy != E()) { if (t->l) propagate(t->l, t->lazy); if (t->r) propagate(t->r, t->lazy); t->lazy = E(); } } void propagate(Ptr t, const E &x) { t->lazy = h(t->lazy, x); t->key = g(t->key, x); t->sum = g(t->sum, x); } }; /** * @brief 遅延伝搬反転可能Treap */