treap

#include<iostream>
#include<algorithm>
#include<vector>
#include<random>
using namespace std;
using ll=long long;
mt19937 mt(hash<string>()(":poop:"));
template<typename T>
struct node{
    node *l,*r;
    int p,v; T val;
    node(int x,T y):p(x),v(mt()),val(y){l=r=nullptr;}
    void pull(){}
    void push(){}
};
template<typename T>
node<T>* merge(node<T>* a,node<T>* b){
    if(!a||!b) return a?:b;
    a->push(),b->push();
    if(a->v<b->v)
        return a->r=merge(a->r,b),a->pull(),a;
    else
        return b->l=merge(a,b->l),b->pull(),b;
}
template<typename T>
void split(node<T>* rt,int k,node<T>*& a,node<T>*& b){
    if(!rt){a=b=nullptr;return;}
    rt->push();
    if(rt->p<k)
        a=rt,split(a->r,k,a->r,b),a->pull();
    else
        b=rt,split(b->l,k,a,b->l),b->pull();
}
template<typename T>
T& get(node<T>* rt,int idx){
    node<T> *l,*m,*r;
    split(rt,idx,l,r);
    split(r,idx+1,m,r);
    rt=merge(l,merge(m,r));
    return m->val;
}
inline void solve(){
    node<int>* treap=nullptr;
    vector<int> v{1,5,4,2,0,3,9,7,6,8};
    int n=v.size();
    for(int i=0;i<n;i++)
        treap=merge(treap,new node(i,v[i]));
    for(int i=0;i<n;i++)
        cout<<get(treap,i)<<' ';
    cout<<endl;
}
signed main(){
    solve();
    return 0;
}