bzoj 3223/tyvj 1729 文藝平衡樹 splay tree，bzojtyvj
原題鏈接：http://www.tyvj.cn/p/1729
這道題以前用c語言寫的splay tree水過了。。
現在接觸了c++重寫一遍。。。
只涉及區間翻轉，由於沒有刪除操作故不帶垃圾回收，具體如下：
![]()
1 #include<cstdio>
2 #include<cstdlib>
3 #include<iostream>
4 #include<algorithm>
5 const int MAX_N = 100010;
6 struct Node{
7 int v, s, rev;
8 Node *pre, *ch[2];
9 inline void set(int _v = 0, int _s = 0, Node *p = NULL){
10 v = _v, s = _s, rev = 0;
11 pre = ch[0] = ch[1] = p;
12 }
13 inline void push_up(){
14 s = ch[0]->s + ch[1]->s + 1;
15 }
16 inline void update(){
17 Node *t = ch[0];
18 rev ^= 1;
19 t = ch[0];
20 ch[0] = ch[1];
21 ch[1] = t;
22 }
23 inline void push_down(){
24 if (rev != 0){
25 rev ^= 1;
26 ch[0]->update();
27 ch[1]->update();
28 }
29 }
30 };
31 struct SplayTree{
32 Node stack[MAX_N];
33 Node *tail, *root, *null;
34 inline Node *newNode(int v){
35 Node *p = tail++;
36 p->set(v, 1, null);
37 return p;
38 }
39 void initialize(int l, int r){
40 tail = &stack[0];
41 null = tail++;
42 null->set(-1);
43 root = newNode(-1);
44 root->ch[1] = newNode(-1);
45 root->ch[1]->pre = root;
46 Node *x = built(l, r);
47 root->ch[1]->ch[0] = x;
48 x->pre = root->ch[1];
49 root->ch[1]->push_up();
50 root->push_up();
51 }
52 inline void rotate(Node *x, int c){
53 Node *y = x->pre;
54 y->push_down(), x->push_down();
55 y->ch[!c] = x->ch[c];
56 x->pre = y->pre;
57 if (x->ch[c] != null) x->ch[c]->pre = y;
58 if (y->pre != null) y->pre->ch[y->pre->ch[0] != y] = x;
59 x->ch[c] = y;
60 y->pre = x;
61 y->push_up();
62 if (y == root) root = x;
63 }
64 void splay(Node *x, Node *f){
65 if (x == root) return;
66 for (; x->pre != f; x->push_down()){
67 if (x->pre->pre == f){
68 rotate(x, x->pre->ch[0] == x);
69 } else {
70 Node *y = x->pre, *z = y->pre;
71 if (z->ch[0] == y){
72 if (y->ch[0] == x)
73 rotate(y, 1), rotate(x, 1);
74 else rotate(x, 0), rotate(x, 1);
75 } else {
76 if (y->ch[1] == x)
77 rotate(y, 0), rotate(x, 0);
78 else rotate(x, 1), rotate(x, 0);
79 }
80 }
81 }
82 x->push_up();
83 }
84 Node *built(int l, int r){
85 Node *p = null;
86 if (l > r) return null;
87 int mid = (l + r) >> 1;
88 p = newNode(mid);
89 p->ch[0] = built(l, mid - 1);
90 if (p->ch[0] != null) p->ch[0]->pre = p;
91 p->ch[1] = built(mid + 1, r);
92 if (p->ch[1] != null) p->ch[1]->pre = p;
93 p->push_up();
94 return p;
95 }
96 Node *select(Node *x, int k){
97 int t = 0;
98 Node *ret = x;
99 for (;;){
100 ret->push_down();
101 t = ret->ch[0]->s;
102 if (t == k) break;
103 if (k < t) ret = ret->ch[0];
104 else k -= t + 1, ret = ret->ch[1];
105 }
106 return ret;
107 }
108 void travel(Node *x){
109 if (x != null){
110 x->push_down();
111 travel(x->ch[0]);
112 printf("%d ", x->v);
113 travel(x->ch[1]);
114 }
115 }
116 Node *get_range(int l, int r){
117 splay(select(root, l - 1), null);
118 splay(select(root, r + 1), root);
119 return root->ch[1]->ch[0];
120 }
121 void reverse(int l, int r){
122 Node *ret = get_range(l, r);
123 ret->update();
124 }
125 void print(int n){
126 Node *ret = get_range(1, n);
127 travel(ret);
128 }
129 }Splay;
130 int main(){
131 #ifdef LOCAL
132 freopen("in.txt", "r", stdin);
133 freopen("out.txt", "w+", stdout);
134 #endif
135 int n, m, a, b;
136 while (~scanf("%d %d", &n, &m)){
137 Splay.initialize(1, n);
138 while (m--){
139 scanf("%d %d", &a, &b);
140 Splay.reverse(a, b);
141 }
142 Splay.print(n);
143 }
144 return 0;
145 }
View Code
