†全能データ構造†
あらゆるクエリを対数時間で処理する
- lib_implicit_treap<T>(); コンストラクタ
- insert(i, x); i番目の前に値xを挿入
- print_all(); 配列の値を空白区切りで全て出力
- range_add(l, r, x)：区間加算
- range_erase(l, r); 区間削除
- range_max(l, r); 区間最大値取得
- range_min(l, r); 区間最小値取得
- range_mul(l, r, x); 区間乗算
- range_reverse(l, r); 区間反転
- range_sum(l, r); 区間和取得
- range_update(l, r, x); 区間更新
※範囲は 0-indexed、半開区間 [l, r) で指定
サンプル入力
int main(){ lib_implicit_treap<ll> t; for(int i=0;i<9;i++) t.insert(i,i+1); t.print_all(); couten("t.range_erase(3,6);"); t.range_erase(3,6); t.print_all(); couten("t.insert(3,5);"); t.insert(3,5); t.print_all(); couten("t.range_reverse(1,6);"); t.range_reverse(1,6); t.print_all(); couten("t.range_sum(0,7);",t.range_sum(0,7)); t.range_add(1,4,5); couten("t.range_add(1,4,5);"); t.print_all(); t.range_mul(1,4,2); couten("t.range_mul(1,4,2);"); t.print_all(); t.range_update(2,5,4); couten("t.range_update(2,5,4);"); t.print_all(); couten("t.range_max(0,6);",t.range_max(0,6)); couten("t.range_min(1,7);",t.range_min(1,7)); return 0; }
サンプル出力
1 2 3 4 5 6 7 8 9 t.range_erase(3,6); 1 2 3 7 8 9 t.insert(3,5); 1 2 3 5 7 8 9 t.range_reverse(1,6); 1 8 7 5 3 2 9 t.range_sum(0,7); 35 t.range_add(1,4,5); 1 13 12 10 3 2 9 t.range_mul(1,4,2); 1 26 24 20 3 2 9 t.range_update(2,5,4); 1 26 4 4 4 2 9 t.range_max(0,6); 26 t.range_min(1,7); 2
ライブラリ
// Implicit Treap (Randomized Balanced BST) with Lazy Range Single-header library. // Author: ChatGPT (GPT-5 Thinking) // License: MIT template<class T>class lib_implicit_treap { private: struct Node { T val, sum; T add, mul; bool rev; int sz; unsigned pri; Node *l, *r; bool has_set; T set_val; T sub_max, sub_min; Node(ll v): val(v), sum(v), add(0), mul(1), rev(false), sz(1), pri(rand()), l(nullptr), r(nullptr), has_set(false), set_val(0), sub_max(v), sub_min(v) {} }; using pNode = Node*; int node_size(pNode t) { return t ? t->sz : 0; } T node_sum(pNode t) { return t ? t->sum : 0; } vo apply_set(pNode t, T x) { if(!t) return; t->val = x; t->sum = x * t->sz; t->has_set = true; t->set_val = x; t->add = 0; t->mul = 1; t->sub_max = x; t->sub_min = x; } vo apply_add(pNode t, T x) { if(!t) return; if(t->has_set){ t->set_val += x; t->val += x; t->sum = t->set_val * t->sz; t->sub_max = t->set_val; t->sub_min = t->set_val; return; } t->val += x; t->sum += x * t->sz; t->add += x; t->sub_max += x; t->sub_min += x; } vo apply_mul(pNode t, T x) { if(!t) return; if(t->has_set){ t->set_val *= x; t->val = t->set_val; t->sum = t->set_val * t->sz; t->sub_max = t->set_val; t->sub_min = t->set_val; return; } t->val *= x; t->sum *= x; t->add *= x; t->mul *= x; if(x >= 0ll){ t->sub_max *= x; t->sub_min *= x; } else { T new_max = t->sub_min * x; T new_min = t->sub_max * x; t->sub_max = new_max; t->sub_min = new_min; } } vo apply_rev(pNode t) { if(!t) return; t->rev ^= 1; swap(t->l, t->r); } vo push(pNode t) { if(!t) return; if(t->has_set){ apply_set(t->l, t->set_val); apply_set(t->r, t->set_val); t->has_set = false; } if(t->mul != 1){ apply_mul(t->l, t->mul); apply_mul(t->r, t->mul); t->mul = 1; } if(t->add != 0){ apply_add(t->l, t->add); apply_add(t->r, t->add); t->add = 0; } if(t->rev){ apply_rev(t->l); apply_rev(t->r); t->rev = false; } } vo update(pNode t) { if(!t) return; t->sz = 1 + node_size(t->l) + node_size(t->r); t->sum = t->val + node_sum(t->l) + node_sum(t->r); t->sub_max = t->val; t->sub_min = t->val; if(t->l){ t->sub_max = max(t->sub_max, t->l->sub_max); t->sub_min = min(t->sub_min, t->l->sub_min); } if(t->r){ t->sub_max = max(t->sub_max, t->r->sub_max); t->sub_min = min(t->sub_min, t->r->sub_min); } } vo split(pNode t, ll k, pNode &l, pNode &r) { if(!t){ l = r = nullptr; return; } push(t); if(node_size(t->l) >= k){ split(t->l, k, l, t->l); r = t; update(r); } else { split(t->r, k - node_size(t->l) - 1, t->r, r); l = t; update(l); } } pNode merge(pNode l, pNode r) { if(!l||!r) return l?l:r; if(l->pri > r->pri){ push(l); l->r = merge(l->r, r); update(l); return l; } else { push(r); r->l = merge(l, r->l); update(r); return r; } } public: pNode root; lib_implicit_treap(): root(nullptr) { srand(71268726); } vo insert(ll pos, ll val){ pNode a,b; split(root,pos,a,b); root=merge(merge(a,new Node(val)),b); } vo erase(ll pos){ pNode a,b,c; split(root,pos,a,b); split(b,1,b,c); root=merge(a,c); } vo print_all() { std::function<vo(pNode)> dfs=[&](pNode t){ if(!t) return; push(t); dfs(t->l); cout<<t->val<<" "; dfs(t->r); }; dfs(root); cout<<"\n"; } vo range_add(ll l, ll r, ll x){ pNode a,b,c; split(root,r,b,c); split(b,l,a,b); apply_add(b,x); root=merge(merge(a,b),c); } vo range_erase(ll l, ll r) { pNode a, b, c; split(root, l, a, b); split(b, r - l, b, c); root = merge(a, c); } T range_max(ll l, ll r) { pNode a,b,c; split(root,r,b,c); split(b,l,a,b); T ans = b ? b->sub_max : LLONG_MIN; root=merge(merge(a,b),c); return ans; } T range_min(ll l, ll r) { pNode a,b,c; split(root,r,b,c); split(b,l,a,b); T ans = b ? b->sub_min : LLONG_MAX; root=merge(merge(a,b),c); return ans; } vo range_mul(ll l, ll r, ll x) { pNode a,b,c; split(root,r,b,c); split(b,l,a,b); apply_mul(b,x); root=merge(merge(a,b),c); } vo range_reverse(ll l, ll r) { pNode a,b,c; split(root,r,b,c); split(b,l,a,b); apply_rev(b); root=merge(merge(a,b),c); } T range_sum(ll l, ll r) { pNode a,b,c; split(root,r,b,c); split(b,l,a,b); T ans=node_sum(b); root=merge(merge(a,b),c); return ans; } vo range_update(ll l, ll r, ll x) { pNode a,b,c; split(root,r,b,c); split(b,l,a,b); apply_set(b,x); root=merge(merge(a,b),c); } };
