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;
}