学步园

传送门：【SPOJ】 1043 Can you answer these queries I

题目分析：线段树查询任意区间内的最大子区间连续和。

代码如下：

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

#define REP( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define REV( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )

#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson ls , l , m
#define rson rs , m + 1 , r
#define mid ( ( l + r ) >> 1 )
#define root 1 , 1 , n
#define rt o , l , r

const int MAXN = 50005 ;

int sum[MAXN << 2] , maxv[MAXN << 2] , lmax[MAXN << 2] , rmax[MAXN << 2] ;
int n ;

void pushup ( int o ) {
	sum[o] = sum[ls] + sum[rs] ;
	lmax[o] = max ( lmax[ls] , sum[ls] + lmax[rs] ) ;
	rmax[o] = max ( rmax[rs] , sum[rs] + rmax[ls] ) ;
	maxv[o] = max ( max ( maxv[ls] , maxv[rs] ) , rmax[ls] + lmax[rs] ) ;
}

void build ( int o , int l , int r ) {
	if ( l == r ) {
		scanf ( "%d" , &sum[o] ) ;
		lmax[o] = maxv[o] = rmax[o] = sum[o] ;
		return ;
	}
	int m = mid ;
	build ( lson ) ;
	build ( rson ) ;
	pushup ( o ) ;
}

void update ( int x , int v , int o , int l , int r ) {
	if ( l == r ) {
		sum[o] = lmax[o] = maxv[o] = rmax[o] = v ;
		return ;
	}
	int m = mid ;
	if ( x <= m ) update ( x , v , lson ) ;
	else          update ( x , v , rson ) ;
	pushup ( o ) ;
}

int query_sum ( int L , int R , int o , int l , int r ) {
	if ( L <= l && r <= R ) return sum[o] ;
	int m = mid ;
	if ( R <= m ) return query_sum ( L , R , lson ) ;
	if ( m <  L ) return query_sum ( L , R , rson ) ;
	return query_sum ( L , m , lson ) + query_sum ( m + 1 , R , rson ) ;
}

int max_prefix ( int L , int R , int o , int l , int r ) {
	if ( L <= l && r <= R ) return lmax[o] ;
	int m = mid ;
	if ( R <= m ) return max_prefix ( L , R , lson ) ;
	if ( m <  L ) return max_prefix ( L , R , rson ) ;
	return max ( max_prefix ( L , m , lson ) , max_prefix ( m + 1 , R , rson ) + query_sum ( L , m , lson ) ) ;
}

int max_suffix ( int L , int R , int o , int l , int r ) {
	if ( L <= l && r <= R ) return rmax[o] ;
	int m = mid ;
	if ( R <= m ) return max_suffix ( L , R , lson ) ;
	if ( m <  L ) return max_suffix ( L , R , rson ) ;
	return max ( max_suffix ( m + 1 , R , rson ) , max_suffix ( L , m , lson ) + query_sum ( m + 1 , R , rson ) ) ;
}

int query ( int L , int R , int o , int l , int r ) {
	if ( L <= l && r <= R ) return maxv[o] ;
	int m = mid ;
	if ( R <= m ) return query ( L , R , lson ) ;
	if ( m <  L ) return query ( L , R , rson ) ;
	return max ( max ( query ( L , m , lson ) , query ( m + 1 , R , rson ) ) , max_suffix ( L , m , lson ) + max_prefix ( m + 1 , R , rson ) ) ;
}

void solve () {
	int q , ch , x , y ;
	build ( root ) ;
	scanf ( "%d" , &q ) ;
	while ( q -- ) {
		scanf ( "%d%d" , &x , &y ) ;
		printf ( "%d\n" , query ( x , y , root ) ) ;
	}
}

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