【SPOJ】4487 Can you answer these queries VI 【splay】

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

typedef long long LL ;

#define travel( e , H , u ) for ( Edge* e = H[u] ; e ; e = e -> next )
#define rep( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )

const int MAXN = 200005 ;
const int INF = 0x3f3f3f3f ;

struct SplayNode {
	int v ;
	int s ;
	int sum ;
	int Lmax ;
	int Rmax ;
	int maxSum ;
	SplayNode* f ;
	SplayNode* c[2] ;
	void clear () {
		v = sum = s = 0 ;
		Lmax = Rmax = maxSum = -INF ;
	}
	void up () {
		s = c[0] -> s + c[1] -> s + 1 ;
		sum = c[0] -> sum + v + c[1] -> sum ;
		Lmax = max ( c[0] -> Lmax , c[0] -> sum + v + max ( 0 , c[1] -> Lmax ) ) ;
		Rmax = max ( c[1] -> Rmax , c[1] -> sum + v + max ( 0 , c[0] -> Rmax ) ) ;
		maxSum = max ( max ( c[0] -> maxSum , c[1] -> maxSum ) , max ( 0 , c[0] -> Rmax ) + v + max ( 0 , c[1] -> Lmax ) ) ;
	}
} Tnull , *null = &Tnull ;

struct Splay {
	SplayNode node[MAXN] ;
	SplayNode* root ;
	SplayNode* cur ;
	
	Splay () : root ( null ) , cur ( node ) {}
	
	void clear () {
		null -> clear () ;
		root = null ;
		cur = node ;
	}
	
	SplayNode* newnode ( int v , SplayNode* f ) {
		cur -> v = cur -> sum = cur -> Lmax = cur -> Rmax = cur -> maxSum = v ;
		cur -> c[0] = cur -> c[1] = null ;
		cur -> s = 1 ;
		cur -> f = f ;
		return cur ++ ;
	}
	
	void build ( int n ) {
		clear () ;
		FOR ( i , 0 , n + 1 ) {
			int x = -INF ;
			if ( i >= 1 && i <= n ) scanf ( "%d" , &x ) ;
			SplayNode* o = newnode ( x , null ) ;
			o -> c[0] = root ;
			root -> f = o ;
			root = o ;
			root -> up () ;
		}
	}
	
	void rotate ( SplayNode* o , bool d ) {
		SplayNode* p = o -> f ;
		p -> c[!d] = o -> c[d] ;
		o -> c[d] -> f = p ;
		o -> f = p -> f ;
		if ( p -> f != null ) {
			if ( p == p -> f -> c[0] ) p -> f -> c[0] = o ;
			else                       p -> f -> c[1] = o ;
		}
		o -> c[d] = p ;
		p -> f = o ;
		p -> up () ;
		if ( root == p ) root = o ;
	}
	
	void splay ( SplayNode* o , SplayNode* f ) {
		while ( o -> f != f ) {
			SplayNode* p = o -> f ;
			if ( p -> f == f ) {
				if ( o == p -> c[0] ) rotate ( o , 1 ) ;
				else                  rotate ( o , 0 ) ;
			} else {
				if ( p == p -> f -> c[0] ) {
					if ( o == p -> c[0] ) rotate ( p , 1 ) , rotate ( o , 1 ) ;
					else                  rotate ( o , 0 ) , rotate ( o , 1 ) ;
				} else {
					if ( o == p -> c[1] ) rotate ( p , 0 ) , rotate ( o , 0 ) ;
					else                  rotate ( o , 1 ) , rotate ( o , 0 ) ;
				}
			}
		}
		o -> up () ;
	}
	
	void select ( int k , SplayNode* f ) {
		SplayNode* o = root ;
		++ k ;
		while ( o != null ) {
			int s = o -> c[0] -> s ;
			if ( k == s + 1 ) break ;
			if ( k <= s ) o = o -> c[0] ;
			else {
				k -= s + 1 ;
				o = o -> c[1] ;
			}
		}
		splay ( o , f ) ;
	}
	
	SplayNode* get ( int l , int r ) {
		select ( l - 1 , null ) ;
		select ( r + 1 , root ) ;
		return root -> c[1] -> c[0] ;
	}
	
	void remove ( int pos ) {
		get ( pos , pos ) ;
		root -> c[1] -> c[0] = null ;
		root -> c[1] -> up () ;
		root -> up () ;
	}
	
	void insert ( int pos , int v ) {
		get ( pos , pos - 1 ) ;//between x - 1 to x
		SplayNode* o = newnode ( v , root -> c[1] ) ;
		root -> c[1] -> c[0] = o ;
		root -> c[1] -> up () ;
		root -> up () ;
		splay ( o , null ) ;
	}
	
	void replace ( int pos , int v ) {
		select ( pos , null ) ;
		root -> v = v ;
		root -> up () ;
	}
	
	int query ( int L , int R ) {
		SplayNode* o = get ( L , R ) ;
		return o -> maxSum ;
	}
} T ;

int n , q ;

void solve () {
	char op ;
	int x , y ;
	T.build ( n ) ;
	scanf ( "%d" , &q ) ;
	while ( q -- ) {
		scanf ( " %c" , &op ) ;
		if ( op == 'I' ) {
			scanf ( "%d%d" , &x , &y ) ;
			T.insert ( x , y ) ;
		} else if ( op == 'D' ) {
			scanf ( "%d" , &x ) ;
			T.remove ( x ) ;
		} else if ( op == 'R' ) {
			scanf ( "%d%d" , &x , &y ) ;
			T.replace ( x , y ) ;
		} else {
			scanf ( "%d%d" , &x , &y ) ;
			printf ( "%d
" , T.query ( x , y ) ) ;
		}
	}
}

int main () {
	while ( ~scanf ( "%d" , &n ) ) solve () ;
	return 0 ;
}