Implicit Treap

#include<bits/stdc++.h>
using namespace std;

#define si(n) scanf("%d",&n)
#define f first
#define s second
#define mp(a,b) make_pair(a,b)
#define INF 1e9
#define ll long long

/*
One possible solution would be to create some binary tree representing the array.
And that is where implicite key comes into play.
Array index will be our implicite key, that is we consider one element greater if it has greater array index.
In our tree that means, if we take k smallest elements, we will get elements with indices [0..k−1]
*/

/*
features :
    1.insert an array item in log(n)
    2.delete an array item/segment in log(n)
    3.split array from 1...x and x+1...n in log(n)
    4.join two segment in log(n)
    5.find min in log(n)

*/

//Implicit Treap
struct Treap{
    int x,y;// x is the key value(value stored in array), y is priority (random value)
    Treap * left;
    Treap * right;
    int min_;//min value of the entire tree
    int sz;//size of the entire tree
    Treap(int x,int y) : x(x),y(y),left(NULL),right(NULL),min_(x),sz(1) {}

};

typedef Treap * treap;

//find minimum value starting from pointer a
int safe_min(treap a){
    if(!a)return INF;
    return a -> min_;
}

//find size under the subtree from pointer a
int safe_sz(treap a){
    if(!a)return 0;
    return a->sz;
}

// recalculate size and min value
void recalc(treap a){
    a->min_=min(a->x,min(safe_min(a->left),safe_min(a->right)));
    a->sz=1+safe_sz(a->left)+safe_sz(a->right);
}

//merge treap a and b
treap Merge(treap a,treap b){
    if(!a)return b;
    if(!b)return a;
    if(a->y > b->y){
        a->right=Merge(a->right,b);
        recalc(a);
        return a;
    }
    else{
        b->left=Merge(a,b->left);
        recalc(b);
        return b;
    }
}


//return two Treap L,R. L is from first to array index x
//and R is the rest.Here array index is used to split
//hence named Implicit Treap
pair<treap,treap> split_size(treap a,int x){
    if(!a)return mp((treap)NULL,(treap)NULL);
    int sz=safe_sz(a->left)+1;
    if(sz<=x){
        auto u=split_size(a->right,x-sz);
        a->right=u.f;
        recalc(a);
        return mp(a,u.s);
    }
    else{
        auto u=split_size(a->left,x);
        a->left=u.s;
        recalc(a);
        return mp(u.f,a);
    }
}

//find position of the min element in the treap(1-based)
int find_pos_of_min(treap a){
    if(safe_min(a->left) != a->min_){
        if(a->x != a->min_){
            return find_pos_of_min(a->right)+safe_sz(a->left)+1;
        }
        else{
            return 1+safe_sz(a->left);
        }
    }
    else{
        return find_pos_of_min(a->left);
    }
}


int main()
{
    srand(12345);
    int i,j,p,n;
    si(n);
    treap root=NULL;
    for(i=0;i<n;i++){
        si(p);
        root=Merge(root,new Treap(p,rand()));
    }
    ll ans=0;
    while(root){
        int v=find_pos_of_min(root);
        auto u=split_size(root,v-1);//splitting treap from index 1 to v-1 and v to size.
        ans+=safe_sz(u.f)+1;
        auto r=split_size(u.s,1);//splitting two parts.left part consists 1 element and right part consists rest
        root=Merge(r.s,u.f);
    }
    printf("%I64d\n",ans);

    return 0;
}
problem Link: http://codeforces.com/contest/831/problem/E