Назад!

#include <iostream>
#include <tuple>
#include <random>

using std::pair;
using std::cin;
using std::cout;

class InsertTree {
private:
    struct Node {
        int val;
        int size = 1;
        Node *left = nullptr;
        Node *right = nullptr;

        static int Size(Node *n) {
            if (n != nullptr) {
                return n->size;
            }
            return 0;
        }

        void Update() {
            size = Size(left) + Size(right) + 1;
        }
    };

    pair<Node *, Node *> Split(Node *n, int ind) {
        if (n == nullptr) {
            return {nullptr, nullptr};
        }
        if (Node::Size(n->left) >= ind) {
            auto [left, right] = Split(n->left, ind);
            n->left = right;
            n->Update();
            return {left, n};
        }
        auto [left, right] = Split(n->right, ind - Node::Size(n->left) - 1);
        n->right = left;
        n->Update();
        return {n, right};
    }

    static Node *Merge(Node *root1, Node *root2) {
        if (root1 == nullptr) {
            return root2;
        }
        if (root2 == nullptr) {
            return root1;
        }
        static std::minstd_rand rand_gen;
        if (std::uniform_int_distribution(1, Node::Size(root1) + Node::Size(root2))(rand_gen) <= Node::Size(root1)) {
            root1->right = Merge(root1->right, root2);
            root1->Update();
            return root1;
        }
        root2->left = Merge(root1, root2->left);
        root2->Update();
        return root2;
    }

    static Node *Build(int l, int r) {
        if (l >= r) {
            return nullptr;
        }
        Node *new_node = new Node{(l + r) / 2};
        new_node->left = Build(l, (l + r) / 2);
        new_node->right = Build((l + r) / 2 + 1, r);
        new_node->Update();
        return new_node;
    }
    void PrintNodes(Node* n){
        if (n == nullptr){
            return;
        }
        PrintNodes(n->left);
        cout << n->val << " ";
        PrintNodes(n->right);
    }
public:
    explicit InsertTree(int size) : root(Build(1, size + 1)) {
    }
    void Cut(int l, int r){
        auto [less_eq_right, greater_right] = Split(root, r + 1);
        auto [less_left, between] = Split(less_eq_right, l);
//        root = Merge(Merge(between, less_left), greater_right);
        root = Merge(less_left, Merge(greater_right, between));
    }
    void PrintNodes(){
        PrintNodes(root);
    }
    Node* root = nullptr;

};

int main() {
    int n, k;
    cin >> n >> k;
    InsertTree it(n);
    for (int i = 0; i < k; ++i){
        int l, r;
        cin >> l >> r, --l, --r;
        it.Cut(l, r);
    }
    it.PrintNodes();
    return 0;
}