Advertisement
Guest User

Untitled

a guest
Jun 1st, 2015
647
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. inline int myRandom() {
  2.     return (rand() << 16) ^ rand();
  3. }
  4.  
  5. const int BUF = 1005000;
  6.  
  7. struct node {
  8.     int val;
  9.     int cnt, pr;
  10.     node *lf, *rg;
  11.    
  12.     node(){
  13.         val = 0;
  14.         pr = cnt = 0;
  15.         lf = rg = 0;
  16.     }
  17. };
  18.  
  19. typedef node* tree;
  20.  
  21. int szbuf;
  22. node buf[BUF];
  23.  
  24. tree allocate(int val){
  25.     assert(szbuf < BUF);
  26.    
  27.     tree res = &buf[szbuf++];
  28.    
  29.     res->val = val;
  30.     res->pr = myRandom();
  31.     res->cnt = 1;
  32.     res->lf = 0;
  33.     res->rg = 0;
  34.    
  35.     return res;
  36. }
  37.  
  38. inline int getCnt(tree t){
  39.     return t ? (t->cnt) : 0;
  40. }
  41.  
  42. inline void update(tree t){
  43.     if(!t)
  44.         return;
  45.     t->cnt = getCnt(t->lf) + getCnt(t->rg) + 1;
  46. }
  47.  
  48. inline void push(tree t){
  49.     // push data here...
  50. }
  51.  
  52. void split(tree t, int x, tree& lf, tree& rg){
  53.     if(!t){
  54.         lf = rg = 0;
  55.         return;
  56.     }
  57.    
  58.     push(t);
  59.    
  60.     int pos = getCnt(t->lf);
  61.    
  62.     if(pos < x){
  63.         split(t->rg, x - pos - 1, t->rg, rg);
  64.         lf = t;
  65.     }else{
  66.         split(t->lf, x, lf, t->lf);
  67.         rg = t;
  68.     }
  69.    
  70.     update(lf);
  71.     update(rg);    
  72. }
  73.  
  74. tree merge(tree lf, tree rg){
  75.     if(!lf || !rg)
  76.         return lf ? lf : rg;
  77.        
  78.     push(lf);
  79.     push(rg);
  80.        
  81.     tree t;
  82.    
  83.     if(lf->pr > rg->pr){
  84.         t = lf;
  85.         lf->rg = merge(lf->rg, rg);
  86.     }else{
  87.         t = rg;
  88.         rg->lf = merge(lf, rg->lf);
  89.     }
  90.    
  91.     update(t);
  92.  
  93.     return t;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement