# 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;
}
```