reverseTreap.cpp

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

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

using namespace std;

struct node {
    int cnt, prior, key, minn;
    bool rev;

    node *l, *r;

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

typedef node* pnode;

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



void rever(pnode t)
{
    if (t)
    {
        if (t -> rev == false) t -> rev = true;
        else t -> rev = false;
    }
}

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 push(pnode t)
{
    if (t && t -> rev == true)
    {
            t -> rev = false;
            swap(t -> l, t -> r);
            if (t -> l) rever(t -> l);
            if (t -> r) rever(t -> r);
    }
}

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

void split(pnode t, int x, pnode &l, pnode &r)
{
    if (t == 0) l = r = 0;
    else
    {       push(t);
        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 merge(pnode &t, pnode l, pnode r)
{
    update(l);
    update(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);
}

void gocout(pnode t)
{
    if (t == 0) return;
    //push(t);
    gocout(t -> l);
    cout << t -> key << ' ';
    gocout(t -> r);
}

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

    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        cin >> x;
            t1 = new node(x);
            merge(T, T, t1);
    }

        for (int i = 1; i <= m; i++)
        {
            cin >> z >> x >> y;
            split(T, y, t1, t3);
            split(t1, x - 1, t1, t2);

            if (z == 2)
                cout << t2 -> minn << endl;
            else
                rever(t2);

            merge(t1, t1, t2);
                merge(T, t1, t3);

 //               gocout(T);
   //             cout << endl;
        }

    return 0;
}