NaiveMartin's Blog

namespace trp{
    struct node{
        node():s(1),w(rand()){ch[0]=ch[1]=0;}
        node*ch[2];
        int s,w;
    };
    void update(node*u){
        u->s=1;
        if(u->ch[0])u->s+=u->ch[0]->s;
        if(u->ch[1])u->s+=u->ch[1]->s;
    }
    void down(node*u){} 
    node*merge(node*u,node*v){
        if(!u)return v;
        if(!v)return u;
        if(u->w<v->w){
            down(u);
            u->ch[1]=merge(u->ch[1],v);
            update(u);
            return u;
        }else{
            down(v);
            v->ch[0]=merge(u,v->ch[0]);
            update(v);
            return v;
        }
    }
    pair<node*,node*>split(node*u,int k){
		if(!u)return make_pair((node*)0,(node*)0);
		down(u);
		int t=(u->ch[0]?u->ch[0]->s:0)+1;
		if(k<t){
            pair<node*,node*>r=split(u->ch[0],k);
			u->ch[0]=r.second;
			update(u);
			return make_pair(r.first,u);
		}else{
			pair<node*,node*>r=split(u->ch[1],k-t);
			u->ch[1]=r.first;
			update(u);
			return make_pair(u,r.second);
		}
	}
};