Декартовое дерево по неявному ключу 1

struct node
{
    int value_node = NULL;
    int size       = NULL;
    node* left = nullptr;
    node* right = nullptr;

    node(int new_value)
    {
        value_node = new_value;
        size = 1;
    }
};

typedef pair<node*, node*> Pair;

void  update(node* A)
{
    A->size =1 + A->left->size + A->right->size;
}

Pair split(node* A,const int& x)
{
    if (!A) return { NULL ,NULL };
    int l = A->left->size;
    if (l >= x)
    {
        Pair q = split(A->left, x);
        A->left = q.second;
        update(A);
        return { q.first, A };
    }
    else
    {
        Pair q = split(A->right, x-l-1);
        A->right = q.first;
        update(A);
        return {A, q.second};
    }
}
node* merge(node* A,node* B)
{
    if (!A) return B;
    if (!B) return A;

    if (A->size > B->size)
    {
        A->right = merge(A->right, B);
        return A;
    }
    else
    {
        B->left = merge(A, B->left);
        return B;
    }
}