treap.cpp

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <cmath>
#include <string>

#define INF (int)(1e9 + 7)

using namespace std;


struct node {

    int cnt, prior, minn, key;

    node *l, *r;

    node (int x)
    {
        l = r = 0;
        cnt = 1;
        minn = x;
        key = x;
        prior = rand();
    }
};

typedef node* pnode;

pnode T, t1, t2, t3;
int n, x, y;
char s;

int get_cnt(pnode t)
{
    if (t == 0) return 0;
    return t -> cnt;
}
int get_minn(pnode t)
{
    if (t == 0) return INF;
    return t -> minn;
}

void update(pnode t)
{
    if (t)
    {
        t -> cnt = get_cnt(t -> l) + get_cnt(t -> r) + 1;
        t -> minn = min(min(get_minn(t -> l), get_minn(t -> r)), t -> key);
    }
}

void split(pnode t, int x, pnode &l, pnode &r)
{
    if (t == 0) l = r = 0;
    else
    {
        if (get_cnt(t -> l) < x)
        {
            split(t -> r, x - get_cnt(t -> l) - 1, t -> r, r);
            l = t;
        }
        else
        {
            split(t -> l, x, l, t -> l);
            r = t;
        }
    }
    update(l);
    update(r);
}

void gocout(pnode t)
{
    if (t == 0) return;

    gocout(t -> l);
    cout << t -> key << ' ';
    gocout(t -> r);
}
void merge(pnode &t, pnode l, pnode r)
{
    if (l == 0) t = r;
    else if (r == 0) t = l;
    else
    {
        if (l -> prior > r -> prior)
        {
            merge(l -> r, l -> r, r);
            t = l;
        }
        else
        {
            merge(r -> l, l, r -> l);
            t = r;
        }
    }
    update(t);
}

int main()
{
        srand( time (0) );

        cin >> n;

        for (int i = 1; i <= n; i++)
        {
            cin >> s >> x >> y;
            if (s == '+')
            {
                t3 = new node(y);

                split(T, x, t1, t2);
                merge(t1, t1, t3);
                merge(T, t1, t2);
            }
            else
            {
                if (x > y) swap(x, y);
                split(T, y, t1, t2);
                split(t1, x - 1, t1, t3);
                //gocout(t3);
                //cout << endl;
                cout << t3 -> minn << endl;
                merge(t1, t1, t3);
                merge(T, t1, t2);
            }
        }

    return 0;
}