Poj Solution 2750

http://poj.org/problem?id=2750

#include "stdio.h"
#include "memory.h"


const int SIZE = ( 1<<18 );
const int LEAF = ( 1<<17) - 1;

int sum[SIZE],l_max[SIZE],r_max[SIZE],l_min[SIZE], r_min[SIZE], min_e[SIZE], 
    s_max[SIZE], s_min[SIZE], pn, n;

inline int max( int a, int b ) {
    return a>b?a:b;
}

inline int min( int a, int b ) {
    return a<b?a:b;
}

void modify( int c ) {
    int c1 = c*2+1, c2 = c*2+2;
    sum[c] = sum[c1] + sum[c2];
    l_max[c] = max( l_max[c1], sum[c1]+l_max[c2] );
    r_max[c] = max( r_max[c2], sum[c2]+r_max[c1] );
    l_min[c] = min( l_min[c1], sum[c1]+l_min[c2] );
    r_min[c] = min( r_min[c2], sum[c2]+r_min[c1] );
    s_max[c] = max( max( s_max[c1], s_max[c2] ), r_max[c1]+l_max[c2] );
    s_min[c] = min( min( s_min[c1], s_min[c2] ), r_min[c1]+l_min[c2] );
    min_e[c] = min( min_e[c1], min_e[c2] );
}

void modify_leaf( int c, int v ) {
    sum[c] = v;
    s_max[c] = l_max[c] = r_max[c] = max( 0, sum[c] );
    s_min[c] = l_min[c] = r_min[c] = min( 0, sum[c] );
    min_e[c] = ( c < LEAF+n ? sum[c] : 999999 );
}

void creat( int l, int r, int c ) {
    if( c >= LEAF ) {
        modify_leaf( c, sum[c] ); 
    }
    else {
        creat( l, (l+r)/2, c*2+1 );
        creat( (l+r)/2+1, r, c*2+2 );
        modify( c );
    }
}

int k, v;
void change( int l, int r, int c ) {
    int h = (l+r)/2;
    if( l == r ) {
        if( sum[c] > 0 && v <= 0 )
            pn--;
        else if( sum[c]<=0 && v > 0 )
            pn++;
        modify_leaf( c, v );
    }
    else if( k <= h ) {
        change( l, h, c*2+1 );
        modify( c );
    }
    else {
        change( h+1, r, c*2+2 );
        modify( c );
    }
}

void init() {
    int i;

    memset( sum, 0, sizeof sum );
    pn = 0;

    scanf( "%d", &n );
    for( i=LEAF; i<LEAF+n; i++ ) {
        scanf( "%d", sum+i );
        if( sum[i] > 0 )
            pn++;
    }
    creat( 0, LEAF, 0 );
}

int get_ans( ) {
    if( pn == n )
        return sum[0] - min_e[0];
    return max( s_max[0], sum[0]-s_min[0] );
}

int main( ) {
    int m;

    init( );
    scanf( "%d", &m );

    while( m-- ) {
        scanf( "%d %d", &k, &v );
        k--;
        change( 0, LEAF, 0 );
        printf( "%dn", get_ans( ) );
    }    

    return 0;
}