В начало строя!

#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <vector>
using namespace std;

struct treap {
  typedef treap* pTreap;
  int heap;
  int data;
  int branch;
  treap *left, *right;
  treap(int d) {
    heap = rand();
    data = d;
    branch = 1;
    left = right = NULL;
  }
  void split(int i, pTreap& lil, pTreap& big) {
    int myi = left == NULL ? 0 : left->branch;
    lil = big = NULL;
    if (myi < i) {
      // move right
      if (right != NULL) {
        right->split(i - (myi + 1), right, big);
      }
      lil = this;
    } else {
      // move left
      if (left != NULL) {
                left->split(i, lil, left);
            }
            big = this;
    }
    branch = (left == NULL ? 0 : left->branch) + (right == NULL ? 0 : right->branch) + 1;
  }
};

int branchOf(treap* a) { return a == NULL ? 0 : a->branch; }

treap* merge(treap* a, treap* b) {
  if (a == NULL) { return b; }
  if (b == NULL) { return a; }
  if (a->heap > b->heap) {
    a->right = merge(a->right, b);
    a->branch = branchOf(a->left) + branchOf(a->right) + 1;
    return a;
  } else {
    b->left = merge(a, b->left);
    b->branch = branchOf(b->left) + branchOf(b->right) + 1;
    return b;
  }
}

void print(treap* a) {
  if (a != NULL) {
    print(a->left);
    printf("%d ", a->data);
    print(a->right);
  }
}

int main() {
  freopen("g.in", "r", stdin);
  freopen("g.out", "w", stdout);
  srand(time(NULL)), rand();
  int n, m, i, a, b;
  treap *root = NULL, *A, *B, *C;
  scanf("%d%d", &n, &m);
  for (i = 0; i < n; root = merge(root, new treap(++i))) { }
  for (i = 0; i < m; ++i) {
    // print(root); putchar('\n');
    scanf("%d%d", &a, &b);
    root->split(b, B, C);
    if (B != NULL) {
      B->split(a - 1, A, B);
    } else {
      A = NULL;
    }
    root = merge(B, merge(A, C));
  }
  print(root);
  return 0;
}