Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Jul 15th, 2012  |  syntax: C++  |  size: 4.07 KB  |  hits: 21  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <cstdio>
  2. #include <cmath>
  3. #include <cstring>
  4. #include <cstdlib>
  5. #include <ctime>
  6. #include <cassert>
  7. #include <algorithm>
  8. #include <iostream>
  9. #include <vector>
  10. #include <set>
  11. #include <map>
  12. #include <string>
  13. #include <queue>
  14.  
  15. using namespace std;
  16.  
  17. typedef long long ll;
  18. typedef unsigned int uint;
  19.  
  20. #define pb push_back
  21. #define sz(a) (int)a.size()
  22. #define zero(a) memset (a, 0, sizeof(a))
  23. #define mp make_pair
  24.  
  25. #define taskname ""
  26.  
  27. //.clear()
  28. //.begin()
  29. //
  30.  
  31. class cartesian_tree
  32. {
  33.   public:
  34.  
  35.   int key, y;
  36.   int count;
  37.  
  38.   cartesian_tree *l, *r;
  39.  
  40.   cartesian_tree (int _key)
  41.   {
  42.     count = 1;
  43.     key = _key;
  44.     y = ((rand()<<15) + rand());
  45.     l = NULL;
  46.     r = NULL;
  47.   }
  48.  
  49.   cartesian_tree (void)
  50.   {
  51.     count = 1;
  52.     key = 0;
  53.     y = 0;
  54.     l = NULL;
  55.     r = NULL;
  56.   }
  57. };
  58.  
  59. cartesian_tree* merge (cartesian_tree *u, cartesian_tree *v)
  60. {
  61.   if (u == NULL)
  62.     return v;
  63.  
  64.   if (v == NULL)
  65.     return u;
  66.  
  67.   if (u->y >= v->y)
  68.   {
  69.     u->r = merge (u->r, v);
  70.     u->count = (u->l != NULL ? u->l->count : 0) + (u->r != NULL ? u->r->count : 0) + 1;
  71.     return u;
  72.   }
  73.   else
  74.   {
  75.     v->l = merge (u, v->l);
  76.     v->count = (v->l != NULL ? v->l->count : 0) + (v->r != NULL ? v->r->count : 0) + 1;
  77.     return v;
  78.   }
  79. }
  80.  
  81. cartesian_tree split (cartesian_tree *u, int key)
  82. {
  83.   cartesian_tree res, tmp;
  84.  
  85.   res.l = res.r = NULL;
  86.  
  87.   if (u == NULL)
  88.     return res;
  89.  
  90.   if (u->key >= key)
  91.   {
  92.     tmp = split (u->l, key);
  93.     u->l = tmp.r;
  94.     u->count = (u->l != NULL ? u->l->count : 0) + (u->r != NULL ? u->r->count : 0) + 1;
  95.     res.l = tmp.l, res.r = u;
  96. //    res.l->sum = tmp.l->sum, res.r->sum = u->sum;
  97.   }
  98.   else
  99.   {
  100.     tmp = split (u->r, key);
  101.     u->r = tmp.l;
  102.     u->count = (u->l != NULL ? u->l->count : 0) + (u->r != NULL ? u->r->count : 0) + 1;
  103.     res.r = tmp.r, res.l = u;
  104. //    res.r->sum = tmp.r->sum, res.l->sum = u->sum;
  105.   }
  106.  
  107.   return res;
  108. }
  109.  
  110. cartesian_tree* del (cartesian_tree *u, cartesian_tree *p, cartesian_tree *node, int key)
  111. {
  112.   if (u == NULL)
  113.     return node;
  114.  
  115.   if (u->key == key)
  116.   {
  117.     cartesian_tree *d;
  118.     if (p == NULL)
  119.       d = node, node = merge (node->l, node->r);
  120.     else
  121.     {
  122.       if (p->r == u)
  123.         d = p->r, p->r = merge(u->l, u->r);
  124.       else
  125.         d = p->l, p->l = merge(u->l, u->r);
  126.     }
  127.     free(d);
  128.     return node;
  129.   }
  130.  
  131.   if (u->key > key)
  132.     return del(u->l, u, node, key);
  133.   else
  134.     return del(u->r, u, node, key);
  135.   u->count = (u->l != NULL ? u->l->count : 0) + (u->r != NULL ? u->r->count : 0) + 1;
  136. }
  137.  
  138. cartesian_tree* add (cartesian_tree *u, cartesian_tree *v)
  139. {
  140.   if (u == NULL)
  141.     return v;
  142.  
  143.   if (u->y > v->y)
  144.   {
  145.     if (u->key < v->key)
  146.     {
  147.       u->r = add(u->r, v);
  148.       u->count = (u->l != NULL ? u->l->count : 0ll) + (u->r != NULL ? u->r->count : 0) + 1;
  149.     }
  150.     else
  151.     {
  152.       u->l = add(u->l, v);
  153.       u->count = (u->l != NULL ? u->l->count : 0ll) + (u->r != NULL ? u->r->count : 0) + 1;
  154.     }
  155.     return u;
  156.   }
  157.   else
  158.   {
  159.     cartesian_tree tmp;
  160.     tmp = split (u, v->key);
  161.     v->l = tmp.l, v->r = tmp.r;
  162.     v->count = (v->l != NULL ? v->l->count : 0) + (v->r != NULL ? v->r->count : 0) + v->key;
  163.     return v;
  164.   }
  165.  
  166.   return NULL;
  167. }
  168.  
  169. uint greater_count (cartesian_tree* u, int key)
  170. {
  171.   if (u == NULL)
  172.     return 0;
  173.  
  174.   uint res = 0;
  175.  
  176.   if (u->key >= key)
  177.   {
  178.     if (u->r != NULL)
  179.       res += u->r->count;
  180.     return res + 1 + greater_count(u->l, key);
  181.   }
  182.   else
  183.     return greater_count(u->r, key);
  184. }
  185.  
  186. void clear (cartesian_tree *u)
  187. {
  188.   if (u == NULL)
  189.     return;
  190.   clear(u->l), clear(u->r);
  191.   free(u);
  192. }
  193.  
  194. class myset
  195. {
  196. public:
  197.   cartesian_tree *node;
  198.  
  199.   myset()
  200.   {
  201.     node = NULL;
  202.   }
  203.  
  204.   void insert (int k)
  205.   {
  206.     cartesian_tree *v = new cartesian_tree(k);
  207.     node = add (node, v);
  208.   }
  209.  
  210.   void erase (int k)
  211.   {
  212.     node = del (node, NULL, node, k);
  213.   }
  214.  
  215.   uint greater_count (int k)
  216.   {
  217.     return ::greater_count (node, k);
  218.   }
  219. };
  220.  
  221. int main (void)
  222. {
  223.   freopen (taskname".in", "r", stdin);
  224.   freopen (taskname".out", "w", stdout);
  225.  
  226.   return 0;
  227. }
create a new version of this paste RAW Paste Data