I invent method to merge two cartesian trees with maybe intersect keys. And want to know what is asymptotic of it.

method:

let's add to a standard cartesian tree field musorka

struct Node {
  Node *l = NULL, *r = NULL;
  int key, priority, cnt = 1;

  Node *musorka = NULL;
}

and when we want to merge trees A and B A->musorka = B

then write push

void push(Node *node) {
  if (!node->musorka) return;
  push(node->l);
  push(node->r);

  pair<Node*, Node*> spl = split(node->musorka, node->key);
  pair<Node*, Node*> spl2 = split(spl.second, node->key + 1);
  
  if (spl2.first) {
    node->cnt++;
  }

  node->l->musorka = spl.first;
  node->r->musorka = spl2.second;
  node->musorka = NULL;
}

then add this push to merge and split.

Maybe someone can estimate asimptotic of this or give counter test where it works n^2?