Реализация

//(C) Igor Kvasov
type pnode=^node;
     node=record
       l,r,p:pnode;
       x,y:longint;
     end;

procedure split(t:pnode;x:longint;var l,r:pnode);
begin
  if t=nil then begin l:=nil; r:=nil end else
  if x<t^.x then begin split(t^.l,x,l,r); t^.l:=r; r:=t end
            else begin split(t^.r,x,l,r); t^.r:=l; l:=t end;
end;

function merge(l,r:pnode):pnode;
begin
  if l=nil then merge:=r else
  if r=nil then merge:=l else
  if l^.y>r^.y then begin l^.r:=merge(l^.r,r); merge:=l end
               else begin r^.l:=merge(l,r^.l); merge:=r end;
end;

procedure insert(var t:pnode;x,y:longint);
var
  tmp:pnode;
begin
  if (t=nil) or (y>t^.y) then begin
    new(tmp); split(t,x,tmp^.l,tmp^.r); t:=tmp; t^.x:=x; t^.y:=y
  end else if x<t^.x then insert(t^.l,x,y)
                     else insert(t^.r,x,y);
end;

procedure delete(var t:pnode;x:longint);
var
  tmp:pnode;
begin
  if t=nil then exit else
  if x<t^.x then delete(t^.l,x) else
  if x>t^.x then delete(t^.r,x) else begin
    tmp:=t; t:=merge(t^.l,t^.r); dispose(tmp);
  end;
end;

function search(var t:pnode;x:longint):pnode;
var
  tmp:pnode;
begin
  search:=nil;
  if t=nil then exit else
  if x<t^.x then search:=search(t^.l, x) else
  if x>t^.x then search:=search(t^.r, x) else
                 search:=t;
end;

function minimum(t:pnode):pnode;
begin
  while t^.l<>nil do t:=t^.l;
  minimum:=t;
end;

function maximum(t:pnode):pnode;
begin
  while t^.r<>nil do t:=t^.r;
  maximum:=t;
end;

begin
end.

#include <stdio.h>
#include <malloc.h>

#define UNIQ_KEYS 1

typedef int mvalue_t;
typedef int mkey_t;

typedef enum {
   BT_ADDED,
   BT_UPDATED,
   BT_DELETED,
   BT_FOUND,
   BT_NOTFOUND,
   BT_ERROR,
} dt_result_t;

typedef struct dt {
   mvalue_t v;
      mkey_t x;
   int y;
      struct dt *l, *r;
} dt_t;

dt_t*
dt_search(dt_t *t, mkey_t x) {
    if ( t == NULL ) return NULL;
    if ( x < t->x ) return dt_search(t->l, x);
    if ( x > t->x ) return dt_search(t->r, x);
    return t;
}

void
dt_split(dt_t *t, mkey_t x, dt_t **l, dt_t **r) {
    if(t == NULL) {
       *r = *l = NULL;
    } else {
       if(x < t->x) {
            dt_split(t->l, x, l, r);
            t->l = *r; *r = t;
       } else {
            dt_split(t->r, x, l, r);
            t->r = *l; *l = t;
       }
    }
}

dt_t*
dt_merge(dt_t *l, dt_t *r) {
    if (l == NULL) return r;
    if (r == NULL) return l;
    if (l->y > r->y) {
       l->r = dt_merge(l->r,r);
       return l;
    } else {
       r->l = dt_merge(l,r->l);
       return r;
    }
}

inline dt_t* dt_newnode(mkey_t x, int y, mvalue_t v) {
    dt_t *t = (dt_t*) malloc(sizeof(dt_t));
    t->x = x; t->y = y, t->v = v;
    return t;
}

int
dt_insert(dt_t **t, mkey_t x, int y, mvalue_t v) {
    dt_t *tmp;
#ifdef UNIQ_KEYS
    tmp = dt_search(*t, x);
    if(tmp) {
       // printf("Replaced key %d value %d changed to %d\n", x, (*t)->v, v);
       tmp->v = v;
       return BT_UPDATED;
    }
#endif
    if (*t == NULL || y > (*t)->y) {
       tmp = dt_newnode(x, y, v);
       dt_split(*t, x, &(tmp->l), &(tmp->r));
       *t    = tmp;
       return BT_ADDED;
    } else if ( x < (*t)->x) {
       return dt_insert(&((*t)->l), x, y, v);
    } else {
       return dt_insert(&((*t)->r), x, y, v);
    }
}

int
dt_delete(dt_t **t, mkey_t x) {
    if ( *t == NULL ) return BT_NOTFOUND;
    if ( x < (*t)->x ) {
       return dt_delete( &((*t)->l), x);
    } else if ( x > (*t)->x) {
       return dt_delete( &((*t)->r), x);
    } else {
       dt_t *tmp = *t;
       *t = dt_merge((*t)->l, (*t)->r);
       free(tmp);
       return BT_ADDED;
    }
}

dt_t* dt_left(dt_t *t) {
    while(t->l != NULL) t = t->l;
    return t;
}

dt_t* dt_right(dt_t *t) {
    while(t->r != NULL) t = t->r;
    return t;
}

• Вход: Число элементов n, а затем n строчек пар ( x , y ). Пары должны идти в порядке возрастания ключей x.
• Выход: Префиксное изображение декартового дерева.

Пример использования:

bash$ gcc ct.c -o ct
bash$ ./ct
7
0 5
1 3
2 2
3 9
4 11
5 4
6 6
(4,11)
   (3,9)
      (0,5)
         ( nil )
         (1,3)
            ( nil )
            (2,2)
               ( nil )
               ( nil )
      ( nil )
   (6,6)
      (5,4)
         ( nil )
         ( nil )
      ( nil )

/* file: ct.c
* Cartesian Tree
*
*/

#include <stdio.h>
#include <malloc.h>

typedef int dkey_t;

typedef struct node {
   struct node *l,*r,*p;
   dkey_t x;
   dkey_t y;
   int size;
} node_t;

int count_size(node_t *root) {
   if(root) {
      return (root->size = 1 + count_size(root->l) + count_size(root->r));
   } else {
      return 0;
   }
}

node_t*
dt_new_node(dkey_t x, dkey_t y) {
   node_t *node = (node_t*)calloc(1, sizeof(node_t));
   node->x = x; node->y = y;
   return node;
}

node_t*
dt_add_right(node_t **root, node_t *old_right, dkey_t x, dkey_t y) {
   node_t *new_right = dt_new_node(x,y);
   while( old_right != *root && old_right->y < y ) {
      old_right = old_right->p;
   }
   if(old_right && old_right->y >= y) {
      new_right->l = old_right->r;
      old_right->r = new_right;
      new_right->p = old_right;
   } else {
      new_right->l = *root;
      *root = new_right;
   }
   return new_right;
}

void
prefix_traverse(node_t *root, void f(node_t*, int), int level) {
   if(root) {
      f(root, level);
      prefix_traverse(root->l, f, level+1);
      prefix_traverse(root->r, f, level+1);
   } else {
      f(root, level);
   }
}

void print_indented(node_t *node, int level) {
   int i;
   for(i=0; i < level; i++) printf("   ");
   if(node) printf("(%d,%d)\n", node->x, node->y);
   else    printf("( nil )\n");
}

int main(int argc, char *argv[])
{
   int n, i, x, y;
   node_t *root = 0;
   node_t *left = 0;
   scanf("%d", &n);
   for(i = 0 ; i < n ; i++) {
      scanf("%d%d", &x, &y);
      left = dt_add_left( &root, left, x, y );
   }
   prefix_traverse(root, print_indented, 0);
   count_size(root);
   while(scanf("%d%d", &x, &y) == 2) {
      printf("%d\n", count_lefter_and_lower(root, x, y, 0) );
   }
   
   return 0;
}