【bzoj3223】文艺平衡树

Description

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是2,4的话,结果是5 2 3 4 1

Input

第一行为n,m n表示初始序列有n个数,这个序列依次是(1,2……n-1,n) m表示翻转操作次数
接下来m行每行两个数l,r 数据保证 1<=l<=r<=n

Output

输出一行n个数字,表示原始序列经过m次变换后的结果

Sample Input

5 3

1 3

1 3

1 4

Sample Output

4 3 2 1 5

HINT

N,M<=100000

Code

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
#define reg register int
#define ll long long
#define cl(x) memset(x, 0, sizeof(x))
#define lc(x) tree[x].son[0]
#define rc(x) tree[x].son[1]
#define fa(x) tree[x].father

struct splay{
int son[2];
int father;
int v;
int siz;
bool rev;
}tree[100100];
int root = 0;
int len = 0;
int n, m;
int a[100100];

inline int read() {
char ch = getchar();
int k = 0, f = 1;
while (!isdigit(ch)) {
if (ch == '-') f = -1;
ch = getchar();
}
while (isdigit(ch)) {
k = k * 10 + ch - '0';
ch = getchar();
}
return k * f;
}

inline bool cp(int pos) {
return pos == rc(fa(pos));
}

inline void maintain(int pos) {
tree[pos].siz = tree[lc(pos)].siz + tree[rc(pos)].siz + 1;
}

inline void ins(int x, int y, bool z) {
tree[x].son[z] = y; fa(y) = x;
}

inline void pushdown(int pos) {
if (tree[pos].rev) {
tree[pos].rev = 0;
std::swap(lc(pos), rc(pos));
if (lc(pos)) tree[lc(pos)].rev ^= 1;
if (rc(pos)) tree[rc(pos)].rev ^= 1;
}
}

inline void rotate(int pos) {
int f = fa(pos);
bool flag = cp(pos);
ins(fa(f), pos, cp(f));
ins(f, tree[pos].son[flag^1], flag);
ins(pos, f, flag^1);
maintain(f);
maintain(pos);
if (!fa(pos)) root = pos;
}

void splay(int pos, int tar = 0) {
while (fa(pos) != tar) {
if (fa(fa(pos)) != tar) {
if (cp(pos) == cp(fa(pos))) rotate(fa(pos));
else rotate(pos);
}
rotate(pos);
}
}

int find(int pos, int v) {
pushdown(pos);
if (tree[lc(pos)].siz + 1 == v) return pos;
else if (tree[lc(pos)].siz >= v) return find(lc(pos), v);
else return find(rc(pos), v - tree[lc(pos)].siz - 1);
}

int insert(int v) {
int pos = root;
int lt = 0;
while (pos && tree[pos].v != v) {
lt = pos;
if (v < tree[pos].v) pos = lc(pos);
else pos = rc(pos);
}
pos = ++len;
tree[pos].v = v;
tree[pos].siz = 1;
lc(pos) = rc(pos) = 0;
tree[pos].rev = 0;
fa(pos) = lt;
tree[lt].son[v > tree[lt].v] = pos;
splay(pos);
return root;
}

void rever(int x, int y) {
int xx = find(root, x);
int yy = find(root, y + 2);
splay(xx);
splay(yy, xx);
tree[lc(yy)].rev ^= 1;
}

void dfs(int pos) {
pushdown(pos);
if (lc(pos)) dfs(lc(pos));
if (tree[pos].v >= 1 && tree[pos].v <= n) printf("%d ", tree[pos].v);
if (rc(pos)) dfs(rc(pos));
}

int main() {
n = read();
insert(0);
root = 1;
for (reg i = 1; i <= n + 1; ++i) insert(i);
m = read();
for (reg i = 1; i <= m; ++i) {
int x = read();
int y = read();
rever(x, y);
}
dfs(root);
return 0;
}