Randomized binary search tree on value

I have never wrote one to split by value, but for segments. Here's a simple problem that gave me my first chance to solve one like that.
http://zerojudge.tw/ShowProblem?problemid=d794 World Ranking
The input will give you scores, and you have to insert each of them while answering its current ranking after its insertion.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_INT = ~( 1 << 31 );

struct Rbst{
    ll val;
    int size;
    Rbst *lc, *rc;
    Rbst(ll _v): val(_v), size(1), lc(NULL), rc(NULL){}
    void pull(){
        size = 1;
        if( lc ) size += lc->size;
        if( rc ) size += rc->size;
    }
} *root;
int size(Rbst *t){ return t ? t->size : 0; }
void split(Rbst *t, ll k, Rbst *&a, Rbst *&b){
    if( !t ) a = b = NULL;
    else{
        if( t->val <= k ){ // so that at last a will have values that are <= k
            a = t;
            split( t->rc, k, a->rc, b );
            a->pull();
        } else{ // and b will have all values that > k
            b = t;
            split( t->lc, k, a, b->lc );
            b->pull();
        }
    }
}
int rnd(){
    static int rand_seed = 20160205;
    return rand_seed = ( rand_seed * 0xdefaced + 1 ) & MAX_INT;
}
Rbst* merge(Rbst *a, Rbst *b){
    if( !a || !b ) return a ? a : b;
    if( rnd() % ( a->size + b->size ) < a->size ){
        a->rc = merge( a->rc, b );
        a->pull();
        return a;
    } else{
        b->lc = merge( a, b->lc );
        b->pull();
        return b;
    }
}
void insert(ll x){
    Rbst *l, *r;
    split( root, x, l, r );
    root = merge( l, merge( new Rbst(x), r ) );
}
int find(Rbst *t, ll x){
    if( t->val == x ) return size( t->rc );
    if( t->val < x ) return find( t->rc, x );
    return size( t->rc ) + 1 + find( t->lc, x );
}

int main(){
    int n;
    while( scanf("%d", &n) == 1 ){
        root = NULL;
        for(int i = 0; i < n; ++i){
            ll x; scanf("%lld", &x);
            insert( x );
            printf("%d\n", find( root, x ) + 1); // ranking of x
        }
    }
    return 0;
}