2791(построение за O(N) ? )

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

using namespace std;

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

class TreapNode
{
public:
    TreapNode(int val, int prior) : val(val), prior(prior), size(1), l(nullptr), r(nullptr) {};
    int get_size() { return size; }
    int get_val() { return val; }
    int get_prior() { return prior; }
    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; }
    void print();
private:
    int val;
    int size;
    int prior;
    TreapNode* l;
    TreapNode* r;
    TreapNode* p;
    void relax();
};

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

void TreapNode::print() {
    if (l != nullptr) l->print();
    fout << val << " ";
    if (r != nullptr) r->print();
}

class Treap
{
public:
    Treap() : root(nullptr) {}
    Treap(vector<int>* pvec);
    void Print() { root->print(); }
    /*void Add(int val) { root = merge(root, new TreapNode(val)); };*/
    void To_Begin(int l, int r) {
        auto sp = split(root, l, r);
        root = merge(get<1>(sp), get<0>(sp), get<2>(sp));
    };
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;
    /*sort(vec.begin(), vec.end(), [](int a, int b) {
        return a < b;
        });*/
    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;
}

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 = 1; i <= n; i++) inp[i-1] = i;
    Treap tr(&inp);
    for (int i = 0; i < m; i++) {
        int l, r; fin >> l >> r;
        tr.To_Begin(--l, --r);
    }

    tr.Print();

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