Treap

struct NODE{
    long Key, Prior, Cnt;
    NODE *l, *r;
    NODE( long Key = 0, long Prior = 0 ):Key( Key ), Prior( Prior ), Cnt(1), l( NULL ), r( NULL ){}
};

typedef NODE* P_NODE;

class TREAP{
    P_NODE Root;
    vector<NODE> Pool;
    long PoolPointer;

    P_NODE Create( long Key, long Prior = rand( ) ){
        P_NODE ret = &Pool[PoolPointer++];
        *ret = NODE( Key,Prior );
        return ret;
    }

    long Count( P_NODE t ){
        return t ? t->Cnt: 0;
    }

    void Update_Count( P_NODE t ){
        if( t ) t->Cnt = 1 + Count(t->l ) + Count(t->r );
    }

    void Split( P_NODE t, long Key, P_NODE &l, P_NODE &r ){
        if( !t ) l = r = NULL;
        else if( Key < t->Key ) Split(t->l, Key, l, t->l ), r = t;
        else Split( t->r, Key, t->r, r ), l = t;
        Update_Count( t );
    }

    void Merge( P_NODE &t, P_NODE l, P_NODE r ){
        if( !l or !r ) t = l?l:r;
        else if( l->Prior > r->Prior ) Merge(l->r, l->r, r ), t = l;
        else Merge(r->l, l, r->l ), t = r;
        Update_Count( t );
    }

    void Insert( P_NODE &t, P_NODE it ){
        if( !t ) t = it;
        else if( it->Prior > t->Prior ) Split(t, it->Key, it->l, it->r ), t = it;
        else Insert((it->Key < t->Key )?t->l:t->r, it );
        Update_Count( t );
    }

    void Erase( P_NODE &t, long Key ){
        if( !t ) return;
        if( t->Key == Key ) Merge(t, t->l, t->r );
        else Erase((Key < t->Key )?t->l:t->r, Key );
        Update_Count( t );
    }

    P_NODE Unite( P_NODE l, P_NODE r ){
        if( !l or !r ) return l?l:r;
        if( l->Prior < r->Prior ) swap( l, r );
        P_NODE lt, rt;
        Split(r, l->Key, lt, rt );
        l->l = Unite(l->l, lt );
        l->r = Unite(l->r, rt );
        Update_Count(l );
        return l;
    }

    long CountLess( P_NODE t, long Key ){
        if( !t ) return 0;
        else if( Key <= t->Key ) return CountLess(t->l,Key );
        else return 1 + Count(t->l ) + CountLess(t->r,Key );
    }

    long CountLessEqual( P_NODE t, long Key ){
        if( !t ) return 0;
        else if( Key < t->Key ) return CountLessEqual(t->l,Key );
        else return 1 + Count(t->l ) + CountLessEqual(t->r,Key );
    }

    P_NODE Get_Kth( P_NODE &t, long K ){
        if( !t or K >= Count(t ) ) return NULL;
        else if( K < Count(t->l ) ) return Get_Kth(t->l, K );
        else if( K == Count(t->l ) ) return t;
        else return Get_Kth(t->r, K-1-Count(t->l ) );
    }

public:
    TREAP( long PoolSize ) : Root( NULL ), PoolPointer( 0 ){
        srand(time(NULL ) );
        Pool.clear( );
        Pool.resize( PoolSize );
    }
    /* Count tot number of node */
    long COUNT( ){
        return Count(Root );
    }
    /* Find a key */
    bool FIND( long Key ){
        return CountLess( Root,Key ) == CountLessEqual( Root,Key );
    }
    /* Insert a key */
    void INSERT( long Key ){
        Insert( Root, Create(Key ) );
    }
    /* Insert a key if the key isnt present in tree */
    void UNIQUE_INSERT( long Key ){
        if(  CountLess( Root,Key ) == CountLessEqual( Root,Key ) ) Insert(Root, Create(Key ) );
    }
    /* Erase a key , if multiple key present then only one will be Erased */
    void ERASE( long Key ){
        Erase(Root, Key );
    }
    /* Find the kth element of the tree , if not found assert will fail */
    long operator[]( long K ){
        P_NODE e = Get_Kth( Root, K );
        assert( e!=NULL );
        return e->Key;
    }
};