Advertisement
konchin_shih

treap

Feb 15th, 2022
588
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.28 KB | None | 0 0
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4. #include<random>
  5. using namespace std;
  6. using ll=long long;
  7. mt19937 mt(hash<string>()(":poop:"));
  8. template<typename T>
  9. struct node{
  10.     node *l,*r;
  11.     int p,v; T val;
  12.     node(int x,T y):p(x),v(mt()),val(y){l=r=nullptr;}
  13.     void pull(){}
  14.     void push(){}
  15. };
  16. template<typename T>
  17. node<T>* merge(node<T>* a,node<T>* b){
  18.     if(!a||!b) return a?:b;
  19.     a->push(),b->push();
  20.     if(a->v<b->v)
  21.         return a->r=merge(a->r,b),a->pull(),a;
  22.     else
  23.         return b->l=merge(a,b->l),b->pull(),b;
  24. }
  25. template<typename T>
  26. void split(node<T>* rt,int k,node<T>*& a,node<T>*& b){
  27.     if(!rt){a=b=nullptr;return;}
  28.     rt->push();
  29.     if(rt->p<k)
  30.         a=rt,split(a->r,k,a->r,b),a->pull();
  31.     else
  32.         b=rt,split(b->l,k,a,b->l),b->pull();
  33. }
  34. template<typename T>
  35. T& get(node<T>* rt,int idx){
  36.     node<T> *l,*m,*r;
  37.     split(rt,idx,l,r);
  38.     split(r,idx+1,m,r);
  39.     rt=merge(l,merge(m,r));
  40.     return m->val;
  41. }
  42. inline void solve(){
  43.     node<int>* treap=nullptr;
  44.     vector<int> v{1,5,4,2,0,3,9,7,6,8};
  45.     int n=v.size();
  46.     for(int i=0;i<n;i++)
  47.         treap=merge(treap,new node(i,v[i]));
  48.     for(int i=0;i<n;i++)
  49.         cout<<get(treap,i)<<' ';
  50.     cout<<endl;
  51. }
  52. signed main(){
  53.     solve();
  54.     return 0;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement