3223: Tyvj 1729 文藝平衡樹
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 3884 Solved: 2235
[Submit][Status][Discuss]
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
Source
平衡樹
[ Submit][ Status][ Discuss]
不是特别難，打個lazy标記就行了，詳見[Splay]
1 /**
2 * bzoj
3 * Problem#3223
4 * Accepted
5 * Time:2012ms
6 * Memory:4336k
7 */
8 #include<iostream>
9 #include<fstream>
10 #include<sstream>
11 #include<cstdio>
12 #include<cstdlib>
13 #include<cstring>
14 #include<ctime>
15 #include<cctype>
16 #include<cmath>
17 #include<algorithm>
18 #include<stack>
19 #include<queue>
20 #include<set>
21 #include<map>
22 #include<vector>
23 using namespace std;
24 typedef bool boolean;
25 #define smin(a, b) (a) = min((a), (b))
26 #define smax(a, b) (a) = max((a), (b))
27 template<typename T>
28 inline void readInteger(T& u){
29 char x;
30 int aFlag = 1;
31 while(!isdigit((x = getchar())) && x != '-' && x != -1);
32 if(x == -1) return;
33 if(x == '-'){
34 x = getchar();
35 aFlag = -1;
36 }
37 for(u = x - '0'; isdigit((x = getchar())); u = (u << 3) + (u << 1) + x - '0');
38 ungetc(x, stdin);
39 u *= aFlag;
40 }
41
42 template<typename T>
43 class SplayNode {
44 public:
45 T data;
46 int s;
47 boolean lazy;
48 SplayNode* next[2];
49 SplayNode* father;
50 SplayNode():s(1), lazy(0){
51 memset(next, 0, sizeof(next));
52 }
53 SplayNode(T data, SplayNode* father):data(data), father(father), s(1), lazy(0){
54 memset(next, 0, sizeof(next));
55 }
56 int cmp(T a){
57 if(a == data) return -1;
58 return (a > data) ? (1) : (0);
59 }
60 int getWhich(SplayNode* p){
61 return (next[0] == p) ? (0) : (1);
62 }
63 void maintain(){
64 s = 1;
65 for(int i = 0; i < 2; i++)
66 if(next[i] != NULL)
67 s += next[i]->s;
68 }
69 void pushDown(){
70 swap(next[0], next[1]);
71 for(int i = 0; i < 2; i++)
72 if(next[i] != NULL)
73 next[i]->lazy ^= 1;
74 lazy = false;
75 }
76 };
77
78 template<typename T>
79 class Splay {
80 protected:
81 inline static void rotate(SplayNode<T>*& node, int d){
82 SplayNode<T> *father = node->father;
83 SplayNode<T> *newRoot = node->next[d ^ 1];
84 if(newRoot->lazy) newRoot->pushDown();
85 node->next[d ^ 1] = newRoot->next[d];
86 node->father = newRoot;
87 newRoot->next[d] = node;
88 newRoot->father = father;
89 if(node->next[d ^ 1] != NULL) node->next[d ^ 1]->father = node;
90 if(father != NULL) father->next[father->getWhich(node)] = newRoot;
91 node->maintain();
92 node->father->maintain();
93 }
94
95 static SplayNode<T>* insert(SplayNode<T>*& node, SplayNode<T>* father, T data){
96 if(node == NULL){
97 node = new SplayNode<T>(data, father);
98 return node;
99 }
100 int d = node->cmp(data);
101 if(d == -1) return NULL;
102 SplayNode<T>* res = insert(node->next[d], node, data);
103 if(res != NULL) node->maintain();
104 return res;
105 }
106
107 static SplayNode<T>* findKth(SplayNode<T>*& node, int k){
108 if(node->lazy) node->pushDown();
109 int ls = (node->next[0] != NULL) ? (node->next[0]->s) : (0);
110 if(k >= ls + 1 && k <= ls + 1) return node;
111 if(k <= ls) return findKth(node->next[0], k);
112 return findKth(node->next[1], k - ls - 1);
113 }
114
115 public:
116 SplayNode<T> *root;
117
118 Splay(){ }
119
120 inline void splay(SplayNode<T>* node, SplayNode<T>* father){
121 if(node == father) return;
122 while(node->father != father){
123 SplayNode<T>* f = node->father;
124 int fd = f->getWhich(node);
125 SplayNode<T>* ff = f->father;
126 if(ff == father){
127 rotate(f, fd ^ 1);
128 break;
129 }
130 int ffd = ff->getWhich(f);;
131 if(ffd == fd){
132 rotate(ff, ffd ^ 1);
133 rotate(f, fd ^ 1);
134 }else{
135 rotate(f, fd ^ 1);
136 rotate(ff, ffd ^ 1);
137 }
138 }
139 if(father == NULL)
140 root = node;
141 }
142
143 inline SplayNode<T>* insert(T data){
144 SplayNode<T>* res = insert(root, NULL, data);
145 if(res != NULL) splay(res, NULL);
146 return res;
147 }
148
149 inline SplayNode<T>* findKth(int k, SplayNode<T>* father){
150 if(k <= 0 || k > root->s) return NULL;
151 SplayNode<T>* p = findKth(root, k);
152 splay(p, father);
153 return p;
154 }
155
156 SplayNode<T>* split(int from, int end){
157 if(from > end) return NULL;
158 if(from == 1 && end == root->s){
159 findKth(1, NULL);
160 return this->root;
161 }
162 if(from == 1){
163 findKth(end + 1, NULL);
164 findKth(from, root);
165 return root->next[0];
166 }
167 if(end == root->s){
168 findKth(from - 1, NULL);
169 findKth(end, root);
170 return root->next[1];
171 }
172 findKth(end + 1, NULL);
173 findKth(from - 1, root);
174 return root->next[0]->next[1];
175 }
176
177 void out(SplayNode<T>* node){
178 if(node == NULL) return;
179 if(node->lazy) node->pushDown();
180 out(node->next[0]);
181 printf("%d ", node->data);
182 out(node->next[1]);
183 }
184
185 void debugOut(SplayNode<T>* node){ //調試使用函數，列印Splay
186 if(node == NULL) return;
187 cout << node->data << "(" << node->s << "," << ((node->father == NULL) ? (-9999) : (node->father->data)) << "," << node->lazy << "){";
188 debugOut(node->next[0]);
189 cout << ",";
190 debugOut(node->next[1]);
191 cout << "}";
192 }
193 };
194
195 int n, m;
196 Splay<int> s;
197
198 int main(){
199 readInteger(n);
200 readInteger(m);
201 for(int i = 1; i <= n; i++){
202 s.insert(i);
203 }
204 for(int i = 1, a, b; i<= m; i++){
205 readInteger(a);
206 readInteger(b);
207 if(a == b) continue;
208 SplayNode<int>* p = s.split(a, b);
209 p->lazy ^= 1;
210 }
211 s.out(s.root);
212 return 0;
213 } 轉載于:https://www.cnblogs.com/yyf0309/p/6287768.html
![goalng nil interface淺析持續學習[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)