![]()
1 #include <bits/stdc++.h>
2 #define L(x) e[x].son[0]
3 #define R(x) e[x].son[1]
4 using namespace std;
5 const int N = 1e6 + 7;
6 const int inf = 0x3f3f3f3f;
7 int n, m, x, y;
8 struct node{
9 int son[2];
10 int father, siz, val, rev;
11 }e[N];
12 int a[N], root, cnt;
13 int identify(int x) {
14 return e[e[x].father].son[0] == x ? 0 : 1;
15 }
16 void connect(int x, int fa, int Son) {
17 e[x].father = fa;
18 e[fa].son[Son] = x;
19 }
20 void update(int x) {
21 e[x].siz = e[L(x)].siz + e[R(x)].siz + 1;
22 }
23 void pushdown(int x) {
24 if (x && e[x].rev) {
25 e[L(x)].rev ^= 1;
26 e[R(x)].rev ^= 1;
27 swap(L(x), R(x));
28 e[x].rev = 0;
29 }
30 }
31 void rotate(int x) {
32 int fa = e[x].father, fason = identify(x);
33 int gfa = e[fa].father, gfason = identify(fa);
34 int B = e[x].son[fason ^ 1];
35 connect(B, fa, fason), connect(fa, x, fason ^ 1);
36 connect(x, gfa, gfason);
37 update(fa), update(x);
38 }
39 void splay(int now, int to) {
40 int tofa = e[to].father;
41 while (e[now].father != tofa) {
42 int fa = e[now].father, gfa = e[fa].father;
43 if (gfa != tofa) {
44 rotate(identify(now) == identify(fa) ? fa : now);
45 }
46 rotate(now);
47 }
48 if (to == root) root = now;
49 }
50 int build(int l, int r, int fa) {
51 if (l > r) {
52 return 0;
53 }
54 int mid = (l + r) / 2;
55 int now = ++cnt;
56 e[now].father = fa;
57 L(now) = R(now) = 0;
58 e[now].val = a[mid];
59 e[now].siz++;
60 L(now) = build(l, mid - 1, now);
61 R(now) = build(mid + 1, r, now);
62 update(now);
63 return now;
64 }
65 int kth(int x) {
66 int now = root;
67 while (true) {
68 pushdown(now);
69 if (x <= e[L(now)].siz) {
70 now = L(now);
71 } else {
72 x -= e[L(now)].siz + 1;
73 if (!x) return now;
74 now = R(now);
75 }
76 }
77 }
78 void reverse(int x, int y) {
79 int l = x - 1, r = y + 1;
80 l = kth(l), r = kth(r);
81 splay(l, root), splay(r, R(l));
82 int now = R(root);
83 now = L(now);
84 e[now].rev ^= 1;
85 }
86 void dfs(int now) {
87 pushdown(now);
88 if (L(now)) dfs(L(now));
89 if (e[now].val != -inf && e[now].val != inf) {
90 printf("%d ", e[now].val);
91 }
92 if (R(now)) dfs(R(now));
93 }
94 int main() {
95 scanf("%d%d", &n, &m);
96 a[1] = -inf;
97 a[n + 2] = inf;
98 for (int i = 1; i <= n; i++) {
99 a[i + 1] = i;
100 }
101 root = build(1, n + 2, 0);
102 for (int i = 1; i <= m; i++) {
103 scanf("%d%d", &x, &y);
104 reverse(x + 1, y + 1);
105 }
106 dfs(root);
107 return 0;
108 }
