Sofia Autumn 2019 - diff

#include<bits/stdc++.h>
using namespace std;
const int inf=(1<<30);
mt19937 rg;
struct Treap
{
    struct Node
    {
        Node *l,*r;
        int sz,key,pr;
        //int ldif,rdif,mdif;
        Node()
        {
            l=NULL;
            r=NULL;
        }
        Node(int _key)
        {
            l=NULL;
            r=NULL;
            key=_key;
            pr=rg();
            sz=1;
        }
        void con()
        {
            sz=1;
            if(l)
            {
                sz+=l->sz;
            }
            if(r)
            {
                sz+=r->sz;
            }
        }
    };

    Node *root;
    Treap(){root=NULL;}

    void Split(Node *T,Node *&L,Node *&R,int key)
    {
        if(T==NULL)
        {
            L=NULL;
            R=NULL;
            return;
        }
        if(key >= T->key)
        {
            L=T;
            Split(T->r,L->r,R,key);
        }
        else
        {
            R=T;
            Split(T->l,L,R->l,key);
        }
        T->con();
    }

    void Merge(Node *&T,Node *L,Node *R)
    {
        if(L==NULL)
        {
            T=R;
            return;
        }
        if(R==NULL)
        {
            T=L;
            return;
        }
        if(L->pr > R->pr)
        {
            T=L;
            Merge(T->r,L->r,R);
        }
        else
        {
            T=R;
            Merge(T->l,L,R->l);
        }
        T->con();
    }

    void Split_sz(Node *T,Node *&L,Node *&R,int sz)
    {
        if(T==NULL)
        {
            L=NULL;
            R=NULL;
            return;
        }
        int tsz=1;
        if(T->l)tsz+=T->l->sz;
        if(tsz>sz)
            Split_sz(T->l,L,R->l,sz);
        else Split_sz(T->r,L->r,R,sz-tsz);
        T->con();
    }

    void Insert(int key)
    {
        Node *L,*R,*N=new Node(key);
        Split(root,L,R,key);
        Merge(L,L,N);
        Merge(root,L,R);
    }

    void Delete(int key)
    ///key is always in the tr
    {
        Node *L,*R,*N;
        Split(root,L,R,key);
        Split(L,L,N,key-1);
        delete N;
        Merge(root,L,R);
    }

    void just_split(int sz)

};
Treap T;
int main()
{
    rg.seed(time(0));

    return 0;
}
/*T.Insert(1);
    cout<<T.root->sz<<endl;
    T.Insert(2);
    cout<<T.root->sz<<endl;
    T.Insert(3);
    cout<<T.root->sz<<endl;
    T.Delete(2);
    cout<<T.root->sz<<endl;
*/