人生第一發splay，寫得巨醜，最後忘記了push_down以後要将子節點maintain
9k代碼不忍直視
1 #define NDEBUG
2 #include<cstdio>
3 #include<cassert>
4 #include<climits>
5 #include<cstdlib>
6 #include<algorithm>
7 #ifndef NDEBUG
8 #define int_out(_a_) printf(#_a_"=%d\n",_a_) ;
9 #else
10 #define int_out(_a_) {}
11 #endif
12 class splay_tree {
13 private :
14 struct node ;
15 node * link_node ( node * const father , node * const child , const int d ) ;
16 mutable node * root ;
17 static node * const nil ;
18 node * kth ( const int k ) ;
19 node * max () ;
20 public :
21 splay_tree () ;
22 splay_tree ( int k , const int value ) ;
23 ~splay_tree () ;
24 void add ( const int L , const int R , const int value ) ;
25 void reverse ( const int L , const int R ) ;
26 int max ( const int L , const int R ) ;
27 void split ( const int k , splay_tree & output ) ;
28 void merge ( splay_tree & input ) ;
29 void clear () ;
30 void distory () ;
31 } ;
32
33 struct splay_tree :: node {
34 int value ;
35 int add_value , reverse , max_value ;
36 int size ;
37 node * ch [ 2 ] ;
38 node * father ;
39 node ( const int value = INT_MIN / 2 , const int size = 1 ) ;
40 ~node () ;
41 node * splay () ;
42 void rotate () ;
43 void push_down () ;
44 void maintain () ;
45 #ifndef NDEBUG
46 void dfs() ;
47 void _dfs( const int , const int ) ;
48 #endif
49 } ;
50
51 #ifndef NDEBUG
52 void splay_tree :: node :: dfs () {
53 if ( this != nil ) this -> _dfs ( 0 , 0 ) ; putchar ( '\n' ) ;
54 }
55
56 void splay_tree :: node :: _dfs ( const int addv , const int re ) {
57 if ( ch [ re ] != nil ) ch [ re ] -> _dfs ( addv + add_value , re ^ ( reverse ) ) ;
58 printf ( "%d " , value + add_value + addv ) ;
59 if ( ch [ re ^ 1 ] != nil ) ch [ re ^ 1 ] -> _dfs ( addv + add_value , re ^ reverse ) ;
60 }
61 #endif
62
63 //nil聲明
64 splay_tree :: node * const splay_tree :: nil = new node ( INT_MIN , 0 ) ;
65
66 //node構造及析構函數
67 splay_tree :: node :: node ( const int value , const int size ) :
68 value ( value ) , add_value ( 0 ) , reverse ( 0 ) , max_value ( value ) , size ( size ) , father ( nil ) { ch [ 0 ] = ch [ 1 ] = nil ; }
69
70 splay_tree :: node :: ~node () {
71 assert ( this != nil ) ;
72 if ( ch [ 0 ] != nil ) delete ch [ 0 ] ;
73 if ( ch [ 1 ] != nil ) delete ch [ 1 ] ;
74 }
75
76 //提供連接配接兩個點的簡單操作
77 //我們假設兩個參數标記已被清空
78 inline splay_tree :: node * splay_tree :: link_node ( node * const father , node * const child , const int d ) {
79 father -> ch [ d ] = child ;
80 child -> father = father ;
81 return father ;
82 }
83
84 //splay_tree構造及析構函數
85 splay_tree :: splay_tree () : root ( nil ) {} ;
86
87 splay_tree :: splay_tree ( int k , const int value ) : root ( nil ) {
88 while ( k -- ) {
89 node * const np = new node ( value ) ;
90 root = link_node ( np , root , 1 ) ;
91 np -> maintain () ;
92 }
93 }
94
95 splay_tree :: ~splay_tree () {
96 if ( root != nil ) delete root ;
97 }
98
99 //下面三個函數是要支援的三種操作
100 void splay_tree :: add ( const int L , const int R , const int value ) {
101 splay_tree mid , right ;
102 split ( R - 1 , right ) ;
103 split ( L - 1 , mid ) ;
104 #ifndef NDEBUG
105 printf ( "add split\n" ) ;
106 #endif
107 mid . root -> add_value += value ;
108 mid . root -> maintain () ;
109 #ifndef NDEBUG
110 int_out(root->size);
111 printf ( "size of mid = %d\n" , mid . root -> size ) ;
112 int_out(right.root->size);
113 #endif
114 merge ( mid ) ;
115 merge ( right ) ;
116 int_out(root->size);
117 #ifndef NDEBUG
118 root -> dfs () ;
119 #endif
120 }
121
122 void splay_tree :: reverse ( const int L , const int R ) {
123 splay_tree mid , right ;
124 split ( R - 1 , right ) ;
125 split ( L - 1 , mid ) ;
126 mid . root -> reverse ^= 1 ;
127 merge ( mid ) ;
128 merge ( right ) ;
129 int_out (root->size) ;
130 }
131
132 int splay_tree :: max ( const int L , const int R ) {
133 splay_tree mid , right ;
134 split ( R - 1 , right ) ;
135 split ( L - 1 , mid ) ;
136 const int ans = mid . root -> max_value ;
137 #ifndef NDEBUG
138 int_out(root->size);
139 root -> dfs () ;
140 printf ( "size of mid = %d\n" , mid . root -> size ) ;
141 mid . root -> dfs () ;
142 int_out(right.root->size);
143 right . root -> dfs () ;
144 #endif
145 merge ( mid ) ;
146 merge ( right ) ;
147 int_out(root->size);
148 #ifndef NDEBUG
149 root -> dfs () ;
150 #endif
151 return ans ;
152 }
153
154 //為splay_tree提供split和merge操作
155 void splay_tree :: split ( const int k , splay_tree & output ) {
156 int_out(k);
157 output . distory () ;
158 if ( k > this -> root -> size ) return ;
159 if ( k == 0 ) {
160 output . root = root ;
161 clear () ;
162 #ifndef NDEBUG
163 printf ( "now the tree is empty\n" ) ;
164 #endif
165 } else {
166 kth ( k ) ;
167 output . root = root -> ch [ 1 ] ;
168 output . root -> father = nil ;
169 root -> ch [ 1 ] = nil ;
170 root -> maintain () ;
171 }
172 }
173
174 void splay_tree :: merge ( splay_tree & input ) {
175 if ( root == nil ) {
176 root = input . root ;
177 } else {
178 max () ;
179 link_node ( root , input . root , 1 ) ;
180 root -> maintain () ;
181 }
182 input . clear () ;
183 }
184
185 //clear & distroy
186
187 void splay_tree :: clear () {
188 root = nil ;
189 }
190
191 void splay_tree :: distory () {
192 if ( root != nil ) root -> ~node () ;
193 root = nil ;
194 }
195
196 //kth & max
197 splay_tree :: node * splay_tree :: kth ( int k ) {
198 #ifndef NDEBUG
199 printf ( "kth begin\n" ) ;
200 #endif
201 node * o = root ;
202 while ( o -> push_down () , k != o -> ch [ 0 ] -> size + 1 ) {
203 assert ( o != nil ) ;
204 const int d = k > o -> ch [ 0 ] -> size + 1 ;
205 if ( d != 0 ) k -= o -> ch [ 0 ] -> size + 1 ;
206 o = o -> ch [ d ] ;
207 }
208 ( root = o ) -> splay () ;
209 return root ;
210 }
211
212 splay_tree :: node * splay_tree :: max () {
213 node * o = root ;
214 assert ( o != nil ) ;
215 while ( o -> push_down () , o -> ch [ 1 ] != nil ) o = o -> ch [ 1 ] ;
216 ( root = o ) -> splay () ;
217 return root ;
218 }
219
220 //rotate
221
222 /*
223 void splay_tree :: node :: rotate () {
224 assert ( this != nil ) ;
225 node * const father = this -> father ;
226 father -> push_down () ;
227 this -> push_down () ;
228 const int d = father -> ch [ 1 ] == this ;
229 this -> father = this -> father -> father ;
230 if ( this -> father -> father != nil ) {
231 const int d2 = this -> father -> father -> ch [ 1 ] == father ;
232 father -> father -> ch [ d2 ] = this ;
233 }
234 father -> ch [ d ] = this -> ch [ d ^ 1 ] ;
235 father -> ch [ d ] -> father = father ;
236 this -> ch [ d ^ 1 ] = father ;
237 father -> father = this ;
238 father -> maintain () ;
239 this -> maintain () ;
240 }*/
241
242 void splay_tree :: node :: rotate () {
243 assert ( this != nil ) ;
244 node * const father = this -> father ;
245 assert ( father != nil ) ;
246
247 father -> push_down () ;
248 this -> push_down () ;
249
250 const int d = father -> ch [ 1 ] == this ;
251 if ( this -> father -> father != nil ) {
252 const int d2 = this -> father -> father -> ch [ 1 ] == this -> father ;
253 ( this -> father = father -> father ) -> ch [ d2 ] = this ;
254 } else this -> father = nil ;
255 ( father -> ch [ d ] = this -> ch [ d ^ 1 ] ) -> father = father ;
256 ( this -> ch [ d ^ 1 ] = father ) -> father = this ;
257
258 father -> maintain () ;
259 this -> maintain () ;
260 }
261
262 splay_tree :: node * splay_tree :: node :: splay () {
263 assert ( this != nil ) ;
264 while ( this -> father != nil && this -> father -> father != nil ) {
265 this -> father -> father -> push_down () ;
266 this -> father -> push_down () ;
267 this -> push_down () ;
268 const int d1 = this -> father -> father -> ch [ 1 ] == this -> father ;
269 const int d2 = this -> father -> ch [ 1 ] == this ;
270 if ( d1 == d2 ) this -> father -> rotate () ;
271 else this -> rotate () ;
272 this -> rotate () ;
273 }
274 if ( this -> father != nil ) this -> rotate () ;
275 return this ;
276 }
277
278 void splay_tree :: node :: push_down () {
279 assert ( this != nil ) ;
280 if ( this -> reverse ) {
281 std :: swap ( this -> ch [ 0 ] , this -> ch [ 1 ] ) ;
282 if ( ch [ 0 ] != nil ) this -> ch [ 0 ] -> reverse ^= 1 ;
283 if ( ch [ 1 ] != nil ) this -> ch [ 1 ] -> reverse ^= 1 ;
284 reverse = 0 ;
285 }
286 if ( this -> add_value != 0 ) {
287 this -> value += this -> add_value ;
288 if ( ch [ 0 ] != nil ) this -> ch [ 0 ] -> add_value += this -> add_value ;
289 if ( ch [ 1 ] != nil ) this -> ch [ 1 ] -> add_value += this -> add_value ;
290 add_value = 0 ;
291 }
292 if ( ch [ 0 ] != nil ) ch [ 0 ] -> maintain () ;
293 if ( ch [ 1 ] != nil ) ch [ 1 ] -> maintain () ;
294 }
295
296 void splay_tree :: node :: maintain () {
297 assert ( this != nil ) ;
298 this -> max_value = std :: max ( value , std :: max ( ch [ 0 ] -> max_value , ch [ 1 ] -> max_value ) ) + add_value ;
299 this -> size = this -> ch [ 0 ] -> size + 1 + this -> ch [ 1 ] -> size ;
300 }
301
302 int main () {
303 int N , M ;
304 scanf ( "%d%d" , & N , & M ) ;
305 splay_tree a ( N , 0 ) ;
306 while ( M -- ) {
307 int opt , l , r , v ;
308 scanf ( "%d%d%d" , & opt , & l , & r ) ;
309 switch ( opt ) {
310 case 1 :
311 scanf ( "%d" , & v ) ;
312 a . add ( l , r + 1 , v ) ;
313 break ;
314 case 2 :
315 a . reverse ( l , r + 1 ) ;
316 break ;
317 case 3 :
318 printf ( "%d\n" , a . max ( l , r + 1 ) ) ;
319 break ;
320 }
321 }
322 return 0 ;
323 } 轉載于:https://www.cnblogs.com/Christopher-Cao/p/5240574.html