Treap

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef long long ll;
struct treap
{
    int x,y,cnt,sum,add;
    treap *l,*r;
    treap() {}
    treap(int x): x(x),y(rand()^(rand()<<15)),cnt(1),sum(x),add(0),l(0),r(0) {}
};
typedef treap* ptreap;
int psize(ptreap t)
{
    return !t?0:t->cnt;
}
int cost(ptreap t)
{
    return !t?0:t->sum+t->add*psize(t);
}
void recalc(ptreap &t)
{
    if (t)
    {
        t->cnt=psize(t->l)+psize(t->r)+1;
        t->sum=cost(t->l)+cost(t->r)+t->x;
    }
}
void push(ptreap t)
{
    if (t)
    {
        if (t->l)
            t->l->add+=t->add;
        if (t->r)
            t->r->add+=t->add;
        t->add=0;
    }
}
void merge(ptreap &t,ptreap l,ptreap r)
{
    if (!l)
    {
        push(r);
        t=r;
    } else if (!r)
    {
        push(l);
        t=l;
    }
    else if (l->y>r->y)
    {
        push(l);
        merge(l->r,l->r,r);
        t=l;
    } else
    {
        push(r);
        merge(r->l,l,r->l);
        t=r;
    }
    recalc(t);
}
void split(ptreap t,ptreap &l,ptreap &r,int x)
{
    if (!t)
    {
        l=r=0;
        return;
    }
    push(t);
    if (t->x<=x)
    {
        split(t->r,t->r,r,x);
        l=t;
        recalc(l);
    } else
    {
        split(t->l,l,t->l,x);
        r=t;
        recalc(r);
    }
}
void insert(ptreap &t,int x)
{
    ptreap l,r;
    split(t,l,r,x);
    merge(l,l,new treap(x));
    merge(t,l,r);
}
void erase(ptreap &t,int x)
{
    ptreap l,r;
    split(t,l,r,x-1);
    split(r,t,r,x);
    merge(t,l,r);
}
int sum(ptreap t,int a,int b)
{
    ptreap l,r;
    split(t,l,r,a-1);
    split(r,l,r,++b);
    return cost(l);
}
void upd(ptreap &t,int a,int b,int d)
{
    ptreap l,r;
    split(t,l,r,a-1);
    split(r,t,r,++b);
    if (t)
        t->add+=d;
    merge(t,l,t);
    merge(t,t,r);
}
ptreap t=0;
int main()
{
    srand(time(NULL));
    int n=10;
    for(int i=0;i<n;i++)
    {
        int x=rand()%200;
        cout<<x<<" ";
        insert(t,x);
    }
    cout<<endl;
    int cod,l,r,d;
    for(;;)
    {
        cin>>cod>>l;
        if (cod>=3)
            cin>>r;
        if (cod==4)
            cin>>d;
        if (cod==1)
            insert(t,l);
        else if (cod==2)
            erase(t,l);
        else if (cod==3)
            cout<<sum(t,l,r)<<endl;
        else
            upd(t,l,r,d);
    }
    return 0;
}