peltorator

Декартово Дерево

Feb 22nd, 2017
181
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct Node
  2. {
  3.     int x;
  4.     ll y;
  5.     int size;
  6.     Node *left;
  7.     Node *right;
  8.     Node(int x = 0):
  9.         x(x),
  10.         y((ll)rnd()),
  11.         size(1),
  12.         left(NULL),
  13.         right(NULL) {}
  14. };
  15.  
  16. int size(Node *v)
  17. {
  18.     return (v == NULL ? 0 : v->size);
  19. }
  20.  
  21. Node* upd(Node *v)
  22. {
  23.     if (v != NULL)
  24.         v->size = 1 + size(v->left) + size(v->right);
  25.     return v;
  26. }
  27.  
  28. Node* merge(Node *l, Node *r)
  29. {
  30.     if (l == NULL)
  31.         return r;
  32.     if (r == NULL)
  33.         return l;
  34.     if (l->y < r->y)
  35.     {
  36.         l = merge(l, r->left);
  37.         r->left = l;
  38.         r = upd(r);
  39.         return r;
  40.     }
  41.     r = merge(l->right, r);
  42.     l->right = r;
  43.     l = upd(l);
  44.     return l;
  45. }
  46.  
  47. pair<Node*, Node*> keySplit(Node *v, int key) // l's keys <= key, r's keys > key
  48. {
  49.     if (v == NULL)
  50.         return {v, v};
  51.     if (v->x <= key)
  52.     {
  53.         auto a = keySplit(v->right, key);
  54.         v->right = a.first;
  55.         v = upd(v);
  56.         return {v, a.second};
  57.     }
  58.     auto a = keySplit(v->left, key);
  59.     v->left = a.second;
  60.     v = upd(v);
  61.     return {a.first, v};
  62. }
  63.  
  64. pair<Node*, Node*> sizeSplit(Node *v, int siz) // l's size is siz
  65. {
  66.     if (!v)
  67.         return {v, v};
  68.     if (size(v->left) >= siz)
  69.     {
  70.         auto a = sizeSplit(v->left, siz);
  71.         v->left = a.second;
  72.         v = upd(v);
  73.         return {a.first, v};
  74.     }
  75.     auto a = sizeSplit(v->right, siz - size(v->left) - 1);
  76.     v->right = a.first;
  77.     v = upd(v);
  78.     return {v, a.second};
  79. }
  80.  
  81. void gogo(Node *v)
  82. {
  83.     if (v == NULL)
  84.         return;
  85.     gogo(v->left);
  86.     cerr << v->x << endl;
  87.     gogo(v->right);
  88. }
RAW Paste Data