Advertisement
konchin_shih

toxic treap

Jun 12th, 2021
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.91 KB | None | 0 0
  1. mt19937 mt;
  2. constexpr int maxn=1e5;
  3. static int k[maxn],v[maxn],l[maxn],r[maxn],top=0;
  4.  
  5. inline node(int x){
  6.     k[top]=x,v[top]=mt();
  7.     l[top]=r[top]=-1;
  8.     return top++;
  9. }
  10.  
  11. int merge(int a,int b){
  12.     int rt=-1,*cur=&rt;
  13.     while(~a&&~b){
  14.         if(v[a]<v[b])
  15.             *cur=a,cur=&r[a],a=r[a];
  16.         else
  17.             *cur=b,cur=&l[b],b=l[b];
  18.     }
  19.     *cur=~a?a:b;
  20.     return rt;
  21. }
  22.  
  23. void split(int t,int x,int *a,int *b){
  24.     while(~t){
  25.         if(k[t]<x)
  26.             t=r[*a=t],a=&r[*a];
  27.         else
  28.             t=l[*b=t],b=&l[*b];
  29.     }
  30.     *a=*b=-1;
  31. }
  32.  
  33. void insert(int& t,int x){
  34.     int l,r;
  35.     split(t,x,&l,&r);
  36.     t=merge(merge(l,node(x)),r);
  37. }
  38.  
  39. void print(int t){
  40.     if(!~t) return;
  41.     print(l[t]);
  42.     cout<<k[t]<<' ';
  43.     print(r[t]);
  44. }
  45.  
  46. inline void solve() {
  47.     int tree=-1;
  48.     for(auto i:{1,5,4,2,0,3,6,9,7,8})
  49.         insert(tree,i);
  50.     print(tree);
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement