Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### bihariforces's blog

By bihariforces, history, 7 weeks ago, How would we implement a multiset data structure that allows insertion, deletion and querying GCD of values currently present in multiset?

insert(5)
GCD() -> 5
insert(10)
GCD() -> 5
remove(5)
GCD() -> 10


This question is not from some existing problem and was just wondering if it was possible to have such data structure where deletion is possible on operations like GCD. I believe this would be helpful https://cp-algorithms.com/data_structures/deleting_in_log_n.html but can't understand how we would apply this or maybe some other method which would work for large numbers upto 1e18. gcd, Comments (4)
 » Treaps. Just modify the "upd_cnt()" function to merge GCD values of the subtrees.
 » you can use dynamic segment tree, which support these operation in O(log n) (Although GCD is O(log n), but realistically, it is much faster than that, so we assume it is O(1))
 » 7 weeks ago, # | ← Rev. 2 →   Splay also works here. #include template> struct spt{ #define DATACOUT 1 bool equals(const Data& d1, const Data& d2) const{ return !Less()(d1, d2) && !Less()(d2, d1); } bool lesswrapper(const Data& d1, const Data& d2) const{ return Less()(d1, d2) > 0; } struct node{ Data d; std::map res; int cnt, sz; struct node *fa, *c; node():d(Data()), cnt(0), sz(0), fa(nullptr){ for(int i = 0; i <= 1; ++i) { c = nullptr; c = nullptr; } } ~node(){ cnt = 0; sz = 0; res.clear(); for(int i = 0; i <= 1; ++i){ if(!c[i]){ delete c[i]; c[i] = nullptr; } } } }; node* root; std::map aggs; Data power(const Data& x, long long p, Data(*agg)(Data, Data)){ if(p <= 0ll) return Data(0); if(p == 1ll) return x; Data res = power(x, p/2, agg); Data res2 = agg(res, res); if(p % 2 == 1){ return agg(res2, x); } return res2; } spt():root(nullptr){ root = nullptr; } void deleteonce(node* cur){ for(int i = 0; i <= 1; ++i) cur->c[i] = nullptr; cur->cnt = 0; cur->sz = 0; delete cur; } bool get(node* x) { return x == (x->fa->c); } void update(node* x){ if(!x) return; x->sz = x->cnt; for(auto [k, agg]: aggs){ x->res[k] = power(x->d, x->cnt, agg); } for(int i = 0; i <= 1; ++i) { if(x->c[i]) { x->sz+=x->c[i]->sz; for(auto [k, agg]: aggs){ if(agg) x->res[k] = (*agg)(x->res[k], x->c[i]->res[k]); } } } } void rotate(node* x){ node *y = x->fa; node *z = y->fa; int f = get(x); y->c[f] = x->c[!f]; if(x->c[!f]){ x->c[!f]->fa = y; } x->c[!f] = y; y->fa = x; x->fa = z; if(z){ z->c[z->c==y] = x; } update(y); update(x); } void splay(node *x){ if(!x) return; for(node* f = x->fa; f = x->fa, f; rotate(x)){ if(f->fa) rotate(get(x) == get(f)?f:x); } root = x; } void insert(const Data& val, int times=1){ if(!root){ root = new node; root->cnt = times; root->d = val; update(root); return; } node *cur = root, *f=nullptr; while(1){ if(equals(cur->d, val)){ cur->cnt+=times; update(cur); update(f); splay(cur); break; } f = cur; cur = cur->c[lesswrapper(cur->d, val)]; if(!cur){ cur = new node; cur->cnt+=times; cur->fa=f; cur->d=val; f->c[lesswrapper(f->d, val)]=cur; update(cur); update(f); splay(cur); break; } } } int rk(const Data& val){ if(!root) return -1; int res = 0; node *cur = root; while(cur){ if(lesswrapper(val, cur->d)){ cur = cur->c; }else{ res += cur->c?cur->c->sz:0; if(equals(val, cur->d)){ splay(cur); return res; } res += cur->cnt; cur = cur->c; } } return -1; } int sz(){ return root?root->sz:0; } std::pair> kth(int k){ k++; node* cur = root; std::map ans; if(!root || k <= 0 || k > sz()){ return std::make_pair(nullptr, ans); } while(1){ if(cur && cur->c && k <= cur->c->sz){ cur = cur->c; }else{ if(cur && cur->c){ for(auto [k, agg]: aggs){ if(agg) ans[k] = agg(ans[k], cur->c->res[k]); } } int tmp = k; int add = ((cur?cur->cnt:0) + ((cur&&cur->c)?cur->c->sz:0)); k -= add; if(k <= 0){ int remain = tmp - (cur&&cur->c?cur->c->sz:0); for(auto [k, agg]: aggs){ if(agg) ans[k] = agg(ans[k], power(cur->d, remain, agg)); } splay(cur); return std::make_pair(cur, ans); } if(cur) { for(auto [k, agg]: aggs){ if(agg) ans[k] = agg(ans[k], power(cur->d, cur->cnt, agg)); } cur = cur->c; } } } return std::make_pair(nullptr, ans); } std::map aggall(){ int splay_sz = sz(); if(!splay_sz) return std::map{}; const auto& [n, m] = kth(splay_sz-1); return m; } std::pair aggall(int id){ auto&& m = aggall(); return std::make_pair(m[id], m.count(id) > 0); } node* pre(){ node* cur = root->c; if(!cur) return cur; while(cur->c) cur = cur->c; splay(cur); return cur; } node* nxt(){ node* cur = root->c; if(!cur) return cur; while(cur->c) cur = cur->c; splay(cur); return cur; } node* lb(const Data& val){//lower_bound node* ans = nullptr; node* cur = root; while(cur){ if(!lesswrapper(cur->d, val)){ ans = cur; cur = cur->c; }else{ cur = cur->c; } } splay(ans); return ans; } node* ub(const Data& val){//upper_bound node* ans = nullptr; node* cur = root; while(cur){ if(lesswrapper(val, cur->d)){ ans = cur; cur = cur->c; }else{ cur = cur->c; } } splay(ans); return ans; } node* rightmost(){ node *cur = root, *f = cur; while(cur){ f = cur; cur = cur->c; } splay(f); return f; } node* pre(const Data& x){ node* p = lb(x); if(p) return pre(); return rightmost(); } node* nxt(const Data& x){ return ub(x); } void del(const Data& val, int times=1){ if(rk(val) == -1) return; if(root && root->cnt > times && times != -1){ root->cnt -= times; update(root); return; } if(!root->c && !root->c){ delete root; root = nullptr; return; } node* cur = root; if(!root->c){ root = root->c; root->fa = nullptr; deleteonce(cur); return; } if(!root->c){ root = root->c; root->fa = nullptr; deleteonce(cur); return; } cur = root; node* x = pre(); cur->c->fa = x; if(x) x->c = cur->c; deleteonce(cur); update(root); } void erase(const Data& val, int times=1){ del(val, times); } struct iter{ node* t; spt* s; iter(node* t, spt* s): t(t), s(s) {} bool operator!=(iter rhs) {return t != rhs.t;} node* operator->() {return t;} node& operator*() {return *t;} void operator++() {t = s->nxt();} void operator--() {t = s->pre();} }; iter begin(){ kth(0); return iter(root, this); } iter end(){ return iter(nullptr, this); } iter rbegin(){ kth(sz()-1); return iter(root, this); } iter rend(){ return iter(nullptr, this); } std::vector r2l(){ std::vector res(sz()); int cnt = 0; for(auto x = rbegin(); x != rend(); --x){ res[cnt] = (*x).d; cnt++; } return res; } std::vector l2r(){ std::vector res(sz()); int cnt = 0; for(auto x: *this){ res[cnt] = x.d; cnt++; } return res; } #if DATACOUT void debug(node* cur){ if(cur){ std::cout << "cur->d==" << cur->d << ", cur->cnt/sz==" << cur->cnt << "/" << cur->sz << ", cur==" << cur << ", cur->fa==" << cur->fa << ", cur->c=={" << cur->c << ", " << cur->c << "}\n"; debug(cur->c); debug(cur->c); } } void debug(){ debug(root); std::cout << "\n"; } void debugres(const std::map& f){ for(auto [k, d]: f){ std::cout << "k==" << k << ", d==" << d << "\n"; } } void debugv(const std::vector& v){ for(int i = 0; i < v.size(); ++i){ std::cout << "v[" << i << "]==" << v[i] << "\n"; } } #endif }; #define DEBUG 1 void debug(const char* p){ #if DEBUG freopen(p, "r", stdin); #else fastio; #endif } spt splay; int main(void){ debug("test1.txt"); splay.aggs = std::gcd; int q; std::cin >> q; for(int i = 0; i < q; ++i){ char ch; int x; std::cin >> ch >> x; if(ch == '+') splay.insert(x); else if(ch == '-') splay.erase(x); std::cout << std::boolalpha << splay.aggall(0).first << "\n"; } } /* 7 + 7 - 5 + 14 + 21 + 3 - 14 - 3 */ 
 » No need to use a dynamic tree, just use a large enough fixed size segment tree with GCD as the operation and a map to track where in the segtree your elements are.