111240 (Построение за O(N))

#include <iostream>
#include <fstream>
#include <ctime>
#include <random>
#include <tuple>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;

ifstream fin("input.txt");
ofstream fout("output.txt");

class TreapNode
{
public:
    TreapNode(int val) :
        val(val),
        size(1),
        prior(rand() | (rand() << 16)),
        minn(val),
        swapp(0),
        l(nullptr),
        r(nullptr) {}
    TreapNode(int val, int prior) :
        val(val),
        size(1),
        prior(prior),
        minn(val),
        swapp(0),
        l(nullptr),
        r(nullptr),
        p(nullptr) {}

    int get_val() { return val; }
    int get_min() { return minn; }
    int get_prior() { return prior; }
    int get_size() { return size; }
    void Swap() { swapp = !swapp; }
    TreapNode* get_l() { relax(); return l; }
    TreapNode* get_r() { relax(); return r; }
    TreapNode* get_p() { relax(); return p; }
    void set_l(TreapNode* l) {
        if (l != nullptr) l->set_p(this);
        this->l = l; relax();
    }
    void set_r(TreapNode* r) {
        if (r != nullptr) r->set_p(this);
        this->r = r; relax();
    }
    void set_p(TreapNode* p) {
        this->p = p;
    }

private:
    int val;
    int size;
    int prior;
    int minn;
    bool swapp;
    TreapNode* l;
    TreapNode* r;
    TreapNode* p;
    void relax();
};

void TreapNode::relax() {
    int size_l = (l == nullptr ? 0 : l->get_size());
    int size_r = (r == nullptr ? 0 : r->get_size());
    size = size_l + 1 + size_r;

    int min_l = (l == nullptr ? INT_MAX : l->get_min());
    int min_r = (r == nullptr ? INT_MAX : r->get_min());
    minn = min(val, min(min_l, min_r));

    if (swapp) {
        swap(l, r);
        if (l != nullptr) l->Swap();
        if (r != nullptr) r->Swap();
        Swap();
    }
}

class Treap {
public:
    Treap() : root(nullptr) {}
    Treap(vector<int> *pvec);
    int Min(int l, int r);
    void Swap(int l, int r);
    void Add(int val) {
        root = merge(root, new TreapNode(val));
    };
private:
    TreapNode* root;
    TreapNode* last;
    TreapNode* merge(TreapNode* t1, TreapNode* t2);
    TreapNode* merge(TreapNode* t1, TreapNode* t2, TreapNode* t3);
    tuple<TreapNode*, TreapNode*> split(TreapNode* t, int x);
    tuple<TreapNode*, TreapNode*, TreapNode*> split(TreapNode* t, int l, int r);
};

Treap::Treap(vector<int>* pvec) {
    auto vec = *pvec;

    root = new TreapNode(vec[0], (rand() << 16) | rand());
    last = root;
    for (int i = 1; i < vec.size(); i++) {
        int prior = (rand() << 16) | rand();
        if (last->get_prior() > prior) {
            last->set_r(new TreapNode(vec[i], prior));
            last = last->get_r();
        }
        else {
            TreapNode* cur = last;
            while (cur->get_p() != nullptr && cur->get_prior() <= prior)
                cur = cur->get_p();
            if (cur->get_prior() <= prior) {
                last = new TreapNode(vec[i], prior);
                last->set_l(cur);
            }
            else {
                last = new TreapNode(vec[i], prior);
                last->set_l(cur->get_r());
                cur->set_r(last);
            }
        }
    }
    while (last->get_p() != nullptr) last = last->get_p();
    root = last;
}

int Treap::Min(int l, int r) {
    auto sp = split(root, l, r);
    int res = get<1>(sp)->get_min();
    root = merge(get<0>(sp), get<1>(sp), get<2>(sp));
    return res;
}

void Treap::Swap(int l, int r) {
    auto sp = split(root, l, r);
    get<1>(sp)->Swap();
    root = merge(get<0>(sp), get<1>(sp), get<2>(sp));
}

TreapNode* Treap::merge(TreapNode* t1, TreapNode* t2) {
    if (t1 == nullptr) return t2;
    if (t2 == nullptr) return t1;
    if (t1->get_prior() > t2->get_prior()) {
        t1->set_r(merge(t1->get_r(), t2));
        return t1;
    }
    else {
        t2->set_l(merge(t1, t2->get_l()));
        return t2;
    }
}
TreapNode* Treap::merge(TreapNode* t1, TreapNode* t2, TreapNode* t3) {
    return merge(t1, merge(t2, t3));
}

tuple<TreapNode*, TreapNode*> Treap::split(TreapNode* t, int x) {
    if (t == nullptr) return make_tuple(nullptr, nullptr);
    int size_l = (t->get_l() == nullptr ? 0 : t->get_l()->get_size());
    if (x <= size_l) {
        auto sp = split(t->get_l(), x);
        t->set_l(get<1>(sp));
        return make_tuple(get<0>(sp), t);
    }
    else {
        auto sp = split(t->get_r(), x - size_l - 1);
        t->set_r(get<0>(sp));
        return make_tuple(t, get<1>(sp));
    }
}
tuple<TreapNode*, TreapNode*, TreapNode*> Treap::split(TreapNode* t, int l, int r) {
    auto sp1 = split(t, r + 1);
    auto sp2 = split(get<0>(sp1), l);
    return make_tuple(get<0>(sp2), get<1>(sp2), get<1>(sp1));
}



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

    int n, m;
    fin >> n >> m;
    vector<int> inp(n);
    for (int i = 0; i < n; i++) fin >> inp[i];
    Treap tr(&inp);
    for (int i = 0; i < m; i++) {
        int a; fin >> a;
        int l, r; fin >> l >> r;
        if (a == 1)
            tr.Swap(--l, --r);
        else {
            fout << tr.Min(--l, --r) << endl;
        }
    }

    fin.close();
    fout.close();
    return 0;
}