This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub plasmatic1/templates
#pragma once #include "../template.hpp" mt19937 _mt_treap(04072020); uniform_int_distribution<int> _dis_treap(INT_MIN, INT_MAX); struct Node { Node *l, *r; int pri; int sz; ll val, sum; Node(ll v0) : l(nullptr), r(nullptr), pri(_dis_treap(_mt_treap)), sz(1), val(v0), sum(v0) {} }; int sz(Node *n) { return n ? n->sz : 0; } ll sum(Node *n) { return n ? n->sum : 0; } void push(Node *n) { if (n) { } } void upd(Node *n) { push(n->l); push(n->r); if (n) { n->sz = sz(n->l) + sz(n->r) + 1; n->sum = sum(n->l) + sum(n->r) + n->val; } } const bool VAL = 0, IDX = 1; // type=0->val, type=1->idx void split(Node *n, bool type, ll key, Node *&l, Node *&r) { if (!n) return void(l = r = nullptr); push(n); int rm = sz(n->l) + 1; if ((type == VAL && n->val <= key) || (type == IDX && rm <= key)) { split(n->r, type, key - (type * rm), n->r, r); l = n; } else { split(n->l, type, key, l, n->l); r = n; } upd(n); } void merge(Node *&n, Node *l, Node *r) { push(l); push(r); if (!l || !r) n = l ? l : r; else if (l->pri > r->pri) { merge(l->r, l->r, r); n = l; } else { merge(r->l, l, r->l); n = r; } upd(n); } // debug void io(Node *n) { if(!n)return;io(n->l);cout<<n->val<<", ";io(n->r); } #define PS(n) do{cout<<(#n)<<": [";io(n);cout<<"]"<<endl;}while(0) void ins(Node *&rt, ll x) { Node *tmp; split(rt, VAL, x, rt, tmp); merge(rt, rt, new Node(x)); merge(rt, rt, tmp); } void rem(Node *&rt, ll x) { if (rt->val == x) merge(rt, rt->l, rt->r); else rem(x > rt->val ? rt->r : rt->l, x); upd(rt); } ll over(Node *n, ll x) { if (!n) return LLINF; push(n); if (n->val > x) return min(n->val, over(n->l, x)); return over(n->r, x); }
#line 2 "template.hpp" #include <bits/stdc++.h> #define DEBUG 1 using namespace std; // Defines #define fs first #define sn second #define pb push_back #define eb emplace_back #define mpr make_pair #define mtp make_tuple #define all(x) (x).begin(), (x).end() // Basic type definitions #if __cplusplus == 201703L // CPP17 only things template <typename T> using opt_ref = optional<reference_wrapper<T>>; // for some templates #endif using ll = long long; using ull = unsigned long long; using ld = long double; using pii = pair<int, int>; using pll = pair<long long, long long>; #ifdef __GNUG__ // PBDS order statistic tree #include <ext/pb_ds/assoc_container.hpp> // Common file #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template <typename T, class comp = less<T>> using os_tree = tree<T, null_type, comp, rb_tree_tag, tree_order_statistics_node_update>; template <typename K, typename V, class comp = less<K>> using treemap = tree<K, V, comp, rb_tree_tag, tree_order_statistics_node_update>; // HashSet #include <ext/pb_ds/assoc_container.hpp> template <typename T, class Hash> using hashset = gp_hash_table<T, null_type, Hash>; template <typename K, typename V, class Hash> using hashmap = gp_hash_table<K, V, Hash>; const ll RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count(); struct chash { ll operator()(ll x) const { return x ^ RANDOM; } }; #endif // More utilities int SZ(string &v) { return v.length(); } template <typename C> int SZ(C &v) { return v.size(); } template <typename C> void UNIQUE(vector<C> &v) { sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin()); } template <typename T, typename U> void maxa(T &a, U b) { a = max(a, b); } template <typename T, typename U> void mina(T &a, U b) { a = min(a, b); } const ll INF = 0x3f3f3f3f, LLINF = 0x3f3f3f3f3f3f3f3f; #line 3 "ds/treap.cpp" mt19937 _mt_treap(04072020); uniform_int_distribution<int> _dis_treap(INT_MIN, INT_MAX); struct Node { Node *l, *r; int pri; int sz; ll val, sum; Node(ll v0) : l(nullptr), r(nullptr), pri(_dis_treap(_mt_treap)), sz(1), val(v0), sum(v0) {} }; int sz(Node *n) { return n ? n->sz : 0; } ll sum(Node *n) { return n ? n->sum : 0; } void push(Node *n) { if (n) { } } void upd(Node *n) { push(n->l); push(n->r); if (n) { n->sz = sz(n->l) + sz(n->r) + 1; n->sum = sum(n->l) + sum(n->r) + n->val; } } const bool VAL = 0, IDX = 1; // type=0->val, type=1->idx void split(Node *n, bool type, ll key, Node *&l, Node *&r) { if (!n) return void(l = r = nullptr); push(n); int rm = sz(n->l) + 1; if ((type == VAL && n->val <= key) || (type == IDX && rm <= key)) { split(n->r, type, key - (type * rm), n->r, r); l = n; } else { split(n->l, type, key, l, n->l); r = n; } upd(n); } void merge(Node *&n, Node *l, Node *r) { push(l); push(r); if (!l || !r) n = l ? l : r; else if (l->pri > r->pri) { merge(l->r, l->r, r); n = l; } else { merge(r->l, l, r->l); n = r; } upd(n); } // debug void io(Node *n) { if(!n)return;io(n->l);cout<<n->val<<", ";io(n->r); } #define PS(n) do{cout<<(#n)<<": [";io(n);cout<<"]"<<endl;}while(0) void ins(Node *&rt, ll x) { Node *tmp; split(rt, VAL, x, rt, tmp); merge(rt, rt, new Node(x)); merge(rt, rt, tmp); } void rem(Node *&rt, ll x) { if (rt->val == x) merge(rt, rt->l, rt->r); else rem(x > rt->val ? rt->r : rt->l, x); upd(rt); } ll over(Node *n, ll x) { if (!n) return LLINF; push(n); if (n->val > x) return min(n->val, over(n->l, x)); return over(n->r, x); }