Treap 2 by frp-m.blogspot.com, old variant

treap.cpp

struct node
{
 int x, y;
 node *l, *r;
 int cnt;
 node(int _x, int _y) : x(_x), y(y), l(0), r(0), cnt(1) {}
};

// ... ... все дальнейшие функции - члены класса treap

int node_sz(node* t)
{
 return t ? t->cnt : 0;
}
void update_sz(node* t)
{
 t->cnt = node_sz(t->l) + node_sz(t->r) + 1;
}
int kth(node* t, int k)
{
 if(k == node_sz(t->l))
  return t->x;
 else if(k < node_sz(t->l))
  return kth(t->l, k);
 else
  return kth(t->r, k - node_sz(t->l) - 1);
}
int kth(int k)
{
 return kth(root, k);
}

node* merge(node* a, node* b)
{
 if(!a || !b)
  return a ? a : b;
 else if(a->y > b->y)
 {
  a->r = merge(a->r, b);
  update_sz(a); //исправляем размеры
  return a;
 }
 else
 {
  b->l = merge(a, b->l);
  update_sz(b); //исправляем размеры
  return b;
 }
}
pair<node*, node*> split(node* t, int x)
{
 if(!t)return make_pair((node*)0, (node*)0);
 if(t->x <= x)
 {
  pair<node*, node*> p = split(t->r, x);
  t->r = p.first;
  update_sz(t);
  return make_pair(t, p.second);
 }
 else
 {
  pair<node*, node*> p = split(t->l, x);
  t->l = p.second;
  update_sz(t);
  return make_pair(p.first, t);
 }
}


pair<node*, node*> split(node* t, int sz)
{
 if(!t)return make_pair((node*)0, (node*)0);
 if(node_sz(t->l) + 1 <= sz)
 {
  pair<node*, node*> p = split(t->r, sz - node_sz(t->l) - 1);
  t->r = p.first;
  update_sz(t);
  return make_pair(t, p.second);
 }
 else
 {
  pair<node*, node*> p = split(t->l, sz);
  t->l = p.second;
  update_sz(t);
  return make_pair(p.first, t);
 }
}

void insert(int x, int p)
{
 pair<node*, node*> np1 = split(root, p);
 node* m = new node(x, rand());
 root = merge(merge(np1.first, m), np1.second);
}
void remove(int p)
{
 pair<node*, node*> np1 = split(root, p - 1);
 pair<node*, node*> np2 = split(np1.second, 1);
 delete np2.first;
 root = merge(np1.first, np2.second);
}

struct node
{
 int x, y, min_val;
 node *l, *r;
 int cnt;
 node(int _x, int _y) : x(_x), y(y), l(0), r(0), cnt(1), min_val(_x) {}
};

//... ... ...

int node_min(node* t)
{
 return t ? t->min_val : 0x7fffffff;
}
void update_sz(node* t)
{
 t->cnt = node_sz(t->l) + node_sz(t->r) + 1;
 t->min_val = min(min(node_min(t->l), node_min(t->r)), t->x);
}

int rmq(int l, int r)
{
 pair<node*, node*> sp1 = split(root, l);
 pair<node*, node*> sp2 = split(sp1.second, r - l + 1);
 int rval = sp2.first->min_val;
 root = merge(sp1.first, merge(sp2.first, sp2.second));
 return rval;
}