1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int ch[N][2];
int siz[N], val[N], pri[N];
int sz;
int root;
int mark[N];
int new_node(int v){
siz[++sz] = 1;
val[sz] = v;
pri[sz] = rand();
return sz;
}
void update(int x) {
siz[x] = siz[ch[x][1]] + siz[ch[x][0]] + 1;
}
int buildtree(int l, int r) {
if(l > r) return 0;
int mid = l + r >> 1, v = mid - 1;
int now = new_node(v);
ch[now][0] = buildtree(l, mid - 1);
ch[now][1] = buildtree(mid + 1, r);
update(now);
return now;
}
void pushdown(int x) {
if(x && mark[x]) {
mark[x] = 0;
swap(ch[x][0], ch[x][1]);
if(ch[x][0])
mark[ch[x][0]] ^= 1;
if(ch[x][1])
mark[ch[x][1]] ^= 1;
}
}
void split(int now, int k, int &x, int &y) {
if(!now) x = y = 0;
else {
pushdown(now);
if(k <= siz[ch[now][0]]) {
y = now;
split(ch[now][0], k, x, ch[now][0]);
} else {
x = now;
split(ch[now][1], k - siz[ch[now][0]] - 1, ch[now][1], y);
}
update(now);
}
}
int merge(int x, int y) {
if(!x || !y)
return x + y;
pushdown(x), pushdown(y);
if(pri[x] < pri[y]) {
ch[x][1] = merge(ch[x][1], y);
update(x);
return x;
} else {
ch[y][0] = merge(x, ch[y][0]);
update(y);
return y;
}
}
void dfs(int x) {
if(!x) return;
pushdown(x);
dfs(ch[x][0]);
if(val[x] >= 1 && val[x] <= n)
printf("%d ", val[x]);
dfs(ch[x][1]);
}
void res(int l, int r) {
int a, b, c, d;
split(root, r + 1, a, b);
split(a, l, c, d);
mark[d] ^= 1;
root = merge(merge(c, d), b);
}
int main() {
scanf("%d%d", &n, &m);
root = buildtree(1, n+2);
int l, r;
for (int i = 1; i <= m; i++) {
scanf("%d%d", &l, &r);
res(l, r);
}
dfs(root);
puts("");
return 0;
}
|
