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
题解
维护序列支持序列翻转可以用$splay$和$fhq-treap$实现。
其主要思想就是就是将这棵子树打上旋转标记，并交换左右儿子。
1 Splay
1 //It is made by Awson on 2017.12.18
2 #include <set>
3 #include <map>
4 #include <cmath>
5 #include <ctime>
6 #include <queue>
7 #include <stack>
8 #include <cstdio>
9 #include <string>
10 #include <vector>
11 #include <cstdlib>
12 #include <cstring>
13 #include <iostream>
14 #include <algorithm>
15 #define LL long long
16 #define Max(a, b) ((a) > (b) ? (a) : (b))
17 #define Min(a, b) ((a) < (b) ? (a) : (b))
18 using namespace std;
19 const int N = 100000;
20
21 int n, m, l, r;
22 struct Splay_tree {
23 int pre[N+5], ch[N+5][2], key[N+5], rev[N+5], size[N+5], tot, root;
24 void newnode(int &o, int keyy, int fa) {
25 o = ++tot;
26 key[o] = keyy, pre[o] = fa; size[o] = 1;
27 ch[o][0] = ch[o][1] = rev[o] = 0;
28 }
29 void pushup(int o) {
30 size[o] = size[ch[o][0]]+size[ch[o][1]]+1;
31 }
32 void pushdown(int o) {
33 if (!o || !rev[o]) return;
34 int ls = ch[o][0], rs = ch[o][1];
35 rev[ls] ^= 1, rev[rs] ^= 1;
36 swap(ch[ls][0], ch[ls][1]);
37 swap(ch[rs][0], ch[rs][1]);
38 rev[o] = 0;
39 }
40 void device(int &o, int fa, int l, int r) {
41 if (l > r) return;
42 int mid = (l+r)>>1;
43 newnode(o, mid, fa);
44 if (l == r) return;
45 device(ch[o][0], o, l, mid-1);
46 device(ch[o][1], o, mid+1, r);
47 pushup(o);
48 }
49 void rotate(int o, int kind) {
50 int p = pre[o];
51 ch[p][!kind] = ch[o][kind], pre[ch[o][kind]] = p;
52 ch[pre[p]][ch[pre[p]][1] == p] = o, pre[o] = pre[p];
53 ch[o][kind] = p; pre[p]= o;
54 pushup(p), pushup(o);
55 }
56 void splay(int o, int goal) {
57 while (pre[o] != goal) {
58 pushdown(pre[o]), pushdown(o);
59 if (pre[pre[o]] == goal) rotate(o, ch[pre[o]][0] == o);
60 else {
61 int p = pre[o], kind = ch[pre[p]][0] == p;
62 if (ch[p][kind] == o) rotate(o, !kind), rotate(o, kind);
63 else rotate(p, kind), rotate(o, kind);
64 }
65 }
66 if (!goal) root = o;
67 }
68 int get_node(int o, int rank) {
69 pushdown(o);
70 if (size[ch[o][0]]+1 == rank) return o;
71 if (size[ch[o][0]] >= rank) return get_node(ch[o][0], rank);
72 return get_node(ch[o][1], rank-(size[ch[o][0]]+1));
73 }
74 void reser(int l, int r) {
75 int r1 = get_node(root, l), r2 = get_node(root, r);
76 splay(r1, 0), splay(r2, r1);
77 int p = ch[r2][0];
78 swap(ch[p][0], ch[p][1]); rev[p] ^= 1;
79 }
80 void print(int o) {
81 pushdown(o);
82 if (ch[o][0]) print(ch[o][0]);
83 if (key[o] != 1 && key[o] != n+2) printf("%d ", key[o]-1);
84 if (ch[o][1]) print(ch[o][1]);
85 }
86 }S;
87
88 void work() {
89 scanf("%d%d", &n, &m);
90 S.device(S.root, 0, 1, n+2);
91 while (m--) {
92 scanf("%d%d", &l, &r);
93 S.reser(l, r+2);
94 }
95 S.print(S.root); printf("\n");
96 }
97 int main() {
98 work();
99 return 0;
100 } Splay
2 fhq_Treap
对于无旋$Treap$，代码里废除了平衡参数$lev$的思想。在$merge$的时候直接随机出一个参数，来判断左接还是右接。
1 //It is made by Awson on 2017.12.19
2 #include <set>
3 #include <map>
4 #include <cmath>
5 #include <ctime>
6 #include <queue>
7 #include <stack>
8 #include <cstdio>
9 #include <string>
10 #include <vector>
11 #include <cstdlib>
12 #include <cstring>
13 #include <iostream>
14 #include <algorithm>
15 #define LL long long
16 #define Max(a, b) ((a) > (b) ? (a) : (b))
17 #define Min(a, b) ((a) < (b) ? (a) : (b))
18 using namespace std;
19 const int N = 100000;
20
21 int n, m, l, r;
22 struct fhq_Treap {
23 int ch[N+5][2], key[N+5], size[N+5], rev[N+5], tot, root;
24 void newnode(int &o, int keyy) {
25 o = ++tot;
26 ch[o][0] = ch[o][1] = rev[o] = 0;
27 key[o] = keyy, size[o] = 1;
28 }
29 void pushup(int o) {
30 size[o] = size[ch[o][0]]+size[ch[o][1]]+1;
31 }
32 void pushdown(int o) {
33 if (!o || !rev[o]) return;
34 int ls = ch[o][0], rs = ch[o][1];
35 rev[ls] ^= 1, rev[rs] ^= 1;
36 swap(ch[ls][0], ch[ls][1]);
37 swap(ch[rs][0], ch[rs][1]);
38 rev[o] = 0;
39 }
40 void device(int &o, int l, int r) {
41 if (l > r) return;
42 int mid = (l+r)>>1;
43 newnode(o, mid);
44 if (l == r) return;
45 device(ch[o][0], l, mid-1);
46 device(ch[o][1], mid+1, r);
47 pushup(o);
48 }
49 void split(int o, int k, int &x, int &y) {
50 if (!o) x = y = 0;
51 else {
52 pushdown(o);
53 if (size[ch[o][0]]+1 <= k) x = o, split(ch[o][1], k-(size[ch[o][0]]+1), ch[o][1], y);
54 else y = o, split(ch[o][0], k, x, ch[o][0]);
55 pushup(o);
56 }
57 }
58 int merge(int x, int y) {
59 if (!x || !y) return x+y;
60 pushdown(x), pushdown(y);
61 if (rand()%2) {
62 ch[x][1] = merge(ch[x][1], y);
63 pushup(x); return x;
64 }else {
65 ch[y][0] = merge(x, ch[y][0]);
66 pushup(y); return y;
67 }
68 }
69 void reser(int l, int r) {
70 int r1, r2, r3;
71 split(root, r, r2, r3);
72 split(r2, l-1, r1, r2);
73 rev[r2] ^= 1; swap(ch[r2][0], ch[r2][1]);
74 root = merge(merge(r1, r2), r3);
75 }
76 void print(int o) {
77 pushdown(o);
78 if (ch[o][0]) print(ch[o][0]);
79 printf("%d ", key[o]);
80 if (ch[o][1]) print(ch[o][1]);
81 }
82 }T;
83
84 void work() {
85 srand(time(0));
86 scanf("%d%d", &n, &m);
87 T.device(T.root, 1, n);
88 while (m--) {
89 scanf("%d%d", &l, &r);
90 T.reser(l, r);
91 }
92 T.print(T.root); printf("\n");
93 }
94 int main() {
95 work();
96 return 0;
97 } fhq_Treap
转载于:https://www.cnblogs.com/NaVi-Awson/p/8065176.html
![goalng nil interface浅析持续学习[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)