Treap

#include <iostream>
#include <cstdlib>
#include <fstream>

using namespace std;

const long long INF = 1e10;

struct Treap
{
    long long x, y, mn, sz;
    bool reversed;
    Treap *l, *r;
    Treap(long long x) : x(x), y(rand()), l(NULL), r(NULL), sz(1), mn(x), reversed(false) {}
    Treap() {}
};

long long get_min(Treap *T)
{
    if (T == NULL)
        return INF;
    return T -> mn;
}

long long get_size(Treap *T)
{
    if (T == NULL)
        return 0;
    return T -> sz;
}

void recalc(Treap* T)
{
    if (T == NULL)
        return;
    T -> sz = 1 + get_size(T -> l) + get_size(T -> r);
    T -> mn = min(T -> x, min(get_min(T -> l), get_min(T -> r)));
}

void Push(Treap *T)
{
    if (T == NULL) return;
    if (T -> reversed == false) return;

    swap(T -> l, T -> r);
    T -> reversed = false;

    if (T -> l != NULL) T -> l -> reversed ^= true;
    if (T -> r != NULL) T -> r -> reversed ^= true;
}

void Merge(Treap *l, Treap *r, Treap* &T)
{
    Push(l);
    Push(r);

    if (l == NULL || r == NULL)
        T = (l == NULL) ? r : l;
    else
        if (l -> y > r -> y)
            Merge(l -> r, r, l -> r), T = l;
        else
            Merge(l, r -> l, r -> l), T = r;
    recalc(T);
}

void Split(Treap *T, long long k, Treap* &l, Treap* &r)
{
    Push(T);

    if (T == NULL){
        l = r = NULL;
        return;
    }

    else
    {
        long long sz = get_size(T -> l);
        if (k > sz)
        {
            l = T;
            Split(T -> r, k - sz - 1, l -> r, r);
        }
        else
        {
            r = T;
            Split(T -> l, k, l, r -> l);
        }
    }
    recalc(l);
    recalc(r);
}

void dfs(Treap *T)
{
    if (T != NULL)
    {
        dfs(T -> l);
        cout << T -> x << ' ';
        dfs(T -> r);
    }
}

int main()
{
    int n, m;
    cin >> n >> m;

    Treap *T = NULL;

    for (int i = 0; i < n; ++i)
    {
        int a;
        cin >> a;
        Treap *nT = new Treap(a);
        Merge(T, nT, T);
    }

    for (int i = 0; i < m; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        if (a == 1)
        {
            Treap *l, *r, *mid;
            Split(T, c, l, r);
            Split(l, b - 1, l, mid);
            mid -> reversed ^= true;
            Merge(l, mid, l);
            Merge(l, r, T);

            dfs(T);
            cout << endl;
        }
        else
        {
            Treap *l, *r, *mid;
            Split(T, c, l, r);
            Split(l, b - 1, l, mid);
            cout << mid -> mn << endl;
            Merge(l, mid, l);
            Merge(l, r, T);
        }
    }
    return 0;
}