treap模板
根据bzoj 1503即NOI2004 郁闷的出纳员
删除小于某个数的区间时直接修改其到根途径所有子树的size

#define MAXN 1000010
int cnt = 0;
struct Node
{
    int l, r;
    int v, s;
    int r;
}nodes[MAXN];
void Update(int k)
{
    nodes[k].s = nodes[nodes[k].l].s + nodes[nodes[k].r].s + 1;
}
void rturn(int &k)
{
    int u = nodes[k].l;
    nodes[k].l = nodes[u].r;
    nodes[u].r = k;
    nodes[u].s = nodes[k].s;
    Update(k);
    k = u;
}
void lturn(int &k)
{
    int u = nodes[k].r;
    nodes[k].r = nodes[u].l;
    nodes[u].l = k;
    nodes[u].s = nodes[k].s;
    Update(k);
    k = u;
}
void Insert(int &k, int x)
{
    if (k == 0)
    {
        cnt++;
        k = cnt;
        nodes[k].r = rand();
        nodes[k].s = 1;
        nodes[k].v = x;
        return;
    }
    nodes[k].s++;
    if (x < nodes[k].v)
    {
        Insert(nodes[k].l, x);
        if (nodes[nodes[k].l].r > nodes[k].r)
            rturn(k);
    }
    else
    {
        Insert(nodes[k].r, x);
        if (nodes[nodes[k].r].r > nodes[k].r)
            lturn(k);
    }
}
int Delete(int &k, int x)
{
    if (k == 0)
        return 0;
    if (nodes[k].v < x)
    {
        int t = nodes[nodes[k].l].s + 1;
        k = nodes[k].r;
        return t + Delete(k, x);
    }
    else
    {
        int t = Delete(nodes[k].l, x);
        nodes[k].s -= t;
        return t;
    }
}
int Find(int k, int x)
{
    int ls = nodes[nodes[k].l].s;
    if (ls + 1 == x)
        return nodes[k].v;
    if (x > ls + 1)
        return Find(nodes[k].r, x - ls - 1);
    else
        return Find(nodes[k].l, x);
}