人生第一发splay，写得巨丑，最后忘记了push_down以后要将子节点maintain
9k代码不忍直视
#define NDEBUG
#include<cstdio>
#include<cassert>
#include<climits>
#include<cstdlib>
#include<algorithm>
#ifndef NDEBUG
#define int_out(_a_) printf(#_a_"=%d\n",_a_) ;
#else
#define int_out(_a_) {}
#endif
class splay_tree {
private :
struct node ;
node * link_node ( node * const father , node * const child , const int d ) ;
mutable node * root ;
static node * const nil ;
node * kth ( const int k ) ;
node * max () ;
public :
splay_tree () ;
splay_tree ( int k , const int value ) ;
~splay_tree () ;
void add ( const int L , const int R , const int value ) ;
void reverse ( const int L , const int R ) ;
int max ( const int L , const int R ) ;
void split ( const int k , splay_tree & output ) ;
void merge ( splay_tree & input ) ;
void clear () ;
void distory () ;
} ; struct splay_tree :: node {
int value ;
int add_value , reverse , max_value ;
int size ;
node * ch [ ] ;
node * father ;
node ( const int value = INT_MIN / , const int size = ) ;
~node () ;
node * splay () ;
void rotate () ;
void push_down () ;
void maintain () ;
#ifndef NDEBUG
void dfs() ;
void _dfs( const int , const int ) ;
#endif
} ; #ifndef NDEBUG
void splay_tree :: node :: dfs () {
if ( this != nil ) this -> _dfs ( , ) ; putchar ( '\n' ) ;
} void splay_tree :: node :: _dfs ( const int addv , const int re ) {
if ( ch [ re ] != nil ) ch [ re ] -> _dfs ( addv + add_value , re ^ ( reverse ) ) ;
printf ( "%d " , value + add_value + addv ) ;
if ( ch [ re ^ ] != nil ) ch [ re ^ ] -> _dfs ( addv + add_value , re ^ reverse ) ;
}
#endif //nil声明
splay_tree :: node * const splay_tree :: nil = new node ( INT_MIN , ) ; //node构造及析构函数
splay_tree :: node :: node ( const int value , const int size ) :
value ( value ) , add_value ( ) , reverse ( ) , max_value ( value ) , size ( size ) , father ( nil ) { ch [ ] = ch [ ] = nil ; } splay_tree :: node :: ~node () {
assert ( this != nil ) ;
if ( ch [ ] != nil ) delete ch [ ] ;
if ( ch [ ] != nil ) delete ch [ ] ;
} //提供连接两个点的简单操作
//我们假设两个参数标记已被清空
inline splay_tree :: node * splay_tree :: link_node ( node * const father , node * const child , const int d ) {
father -> ch [ d ] = child ;
child -> father = father ;
return father ;
} //splay_tree构造及析构函数
splay_tree :: splay_tree () : root ( nil ) {} ; splay_tree :: splay_tree ( int k , const int value ) : root ( nil ) {
while ( k -- ) {
node * const np = new node ( value ) ;
root = link_node ( np , root , ) ;
np -> maintain () ;
}
} splay_tree :: ~splay_tree () {
if ( root != nil ) delete root ;
} //下面三个函数是要支持的三种操作
void splay_tree :: add ( const int L , const int R , const int value ) {
splay_tree mid , right ;
split ( R - , right ) ;
split ( L - , mid ) ;
#ifndef NDEBUG
printf ( "add split\n" ) ;
#endif
mid . root -> add_value += value ;
mid . root -> maintain () ;
#ifndef NDEBUG
int_out(root->size);
printf ( "size of mid = %d\n" , mid . root -> size ) ;
int_out(right.root->size);
#endif
merge ( mid ) ;
merge ( right ) ;
int_out(root->size);
#ifndef NDEBUG
root -> dfs () ;
#endif
} void splay_tree :: reverse ( const int L , const int R ) {
splay_tree mid , right ;
split ( R - , right ) ;
split ( L - , mid ) ;
mid . root -> reverse ^= ;
merge ( mid ) ;
merge ( right ) ;
int_out (root->size) ;
} int splay_tree :: max ( const int L , const int R ) {
splay_tree mid , right ;
split ( R - , right ) ;
split ( L - , mid ) ;
const int ans = mid . root -> max_value ;
#ifndef NDEBUG
int_out(root->size);
root -> dfs () ;
printf ( "size of mid = %d\n" , mid . root -> size ) ;
mid . root -> dfs () ;
int_out(right.root->size);
right . root -> dfs () ;
#endif
merge ( mid ) ;
merge ( right ) ;
int_out(root->size);
#ifndef NDEBUG
root -> dfs () ;
#endif
return ans ;
} //为splay_tree提供split和merge操作
void splay_tree :: split ( const int k , splay_tree & output ) {
int_out(k);
output . distory () ;
if ( k > this -> root -> size ) return ;
if ( k == ) {
output . root = root ;
clear () ;
#ifndef NDEBUG
printf ( "now the tree is empty\n" ) ;
#endif
} else {
kth ( k ) ;
output . root = root -> ch [ ] ;
output . root -> father = nil ;
root -> ch [ ] = nil ;
root -> maintain () ;
}
} void splay_tree :: merge ( splay_tree & input ) {
if ( root == nil ) {
root = input . root ;
} else {
max () ;
link_node ( root , input . root , ) ;
root -> maintain () ;
}
input . clear () ;
} //clear & distroy void splay_tree :: clear () {
root = nil ;
} void splay_tree :: distory () {
if ( root != nil ) root -> ~node () ;
root = nil ;
} //kth & max
splay_tree :: node * splay_tree :: kth ( int k ) {
#ifndef NDEBUG
printf ( "kth begin\n" ) ;
#endif
node * o = root ;
while ( o -> push_down () , k != o -> ch [ ] -> size + ) {
assert ( o != nil ) ;
const int d = k > o -> ch [ ] -> size + ;
if ( d != ) k -= o -> ch [ ] -> size + ;
o = o -> ch [ d ] ;
}
( root = o ) -> splay () ;
return root ;
} splay_tree :: node * splay_tree :: max () {
node * o = root ;
assert ( o != nil ) ;
while ( o -> push_down () , o -> ch [ ] != nil ) o = o -> ch [ ] ;
( root = o ) -> splay () ;
return root ;
} //rotate /*
void splay_tree :: node :: rotate () {
assert ( this != nil ) ;
node * const father = this -> father ;
father -> push_down () ;
this -> push_down () ;
const int d = father -> ch [ 1 ] == this ;
this -> father = this -> father -> father ;
if ( this -> father -> father != nil ) {
const int d2 = this -> father -> father -> ch [ 1 ] == father ;
father -> father -> ch [ d2 ] = this ;
}
father -> ch [ d ] = this -> ch [ d ^ 1 ] ;
father -> ch [ d ] -> father = father ;
this -> ch [ d ^ 1 ] = father ;
father -> father = this ;
father -> maintain () ;
this -> maintain () ;
}*/ void splay_tree :: node :: rotate () {
assert ( this != nil ) ;
node * const father = this -> father ;
assert ( father != nil ) ; father -> push_down () ;
this -> push_down () ; const int d = father -> ch [ ] == this ;
if ( this -> father -> father != nil ) {
const int d2 = this -> father -> father -> ch [ ] == this -> father ;
( this -> father = father -> father ) -> ch [ d2 ] = this ;
} else this -> father = nil ;
( father -> ch [ d ] = this -> ch [ d ^ ] ) -> father = father ;
( this -> ch [ d ^ ] = father ) -> father = this ; father -> maintain () ;
this -> maintain () ;
} splay_tree :: node * splay_tree :: node :: splay () {
assert ( this != nil ) ;
while ( this -> father != nil && this -> father -> father != nil ) {
this -> father -> father -> push_down () ;
this -> father -> push_down () ;
this -> push_down () ;
const int d1 = this -> father -> father -> ch [ ] == this -> father ;
const int d2 = this -> father -> ch [ ] == this ;
if ( d1 == d2 ) this -> father -> rotate () ;
else this -> rotate () ;
this -> rotate () ;
}
if ( this -> father != nil ) this -> rotate () ;
return this ;
} void splay_tree :: node :: push_down () {
assert ( this != nil ) ;
if ( this -> reverse ) {
std :: swap ( this -> ch [ ] , this -> ch [ ] ) ;
if ( ch [ ] != nil ) this -> ch [ ] -> reverse ^= ;
if ( ch [ ] != nil ) this -> ch [ ] -> reverse ^= ;
reverse = ;
}
if ( this -> add_value != ) {
this -> value += this -> add_value ;
if ( ch [ ] != nil ) this -> ch [ ] -> add_value += this -> add_value ;
if ( ch [ ] != nil ) this -> ch [ ] -> add_value += this -> add_value ;
add_value = ;
}
if ( ch [ ] != nil ) ch [ ] -> maintain () ;
if ( ch [ ] != nil ) ch [ ] -> maintain () ;
} void splay_tree :: node :: maintain () {
assert ( this != nil ) ;
this -> max_value = std :: max ( value , std :: max ( ch [ ] -> max_value , ch [ ] -> max_value ) ) + add_value ;
this -> size = this -> ch [ ] -> size + + this -> ch [ ] -> size ;
} int main () {
int N , M ;
scanf ( "%d%d" , & N , & M ) ;
splay_tree a ( N , ) ;
while ( M -- ) {
int opt , l , r , v ;
scanf ( "%d%d%d" , & opt , & l , & r ) ;
switch ( opt ) {
case :
scanf ( "%d" , & v ) ;
a . add ( l , r + , v ) ;
break ;
case :
a . reverse ( l , r + ) ;
break ;
case :
printf ( "%d\n" , a . max ( l , r + ) ) ;
break ;
}
}
return ;
}